Learning Influence Adoption in Heterogeneous Networks
Learning Influence Adoption in Heterogeneous Networks
复制标题
DOI：
10.1609/aaai.v36i6.20592
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Vincent Conitzer;Debmalya Panigrahi;Hanrui Zhang
中科院分区：
文献类型：
--
作者：
Vincent Conitzer;Debmalya Panigrahi;Hanrui Zhang
我们研究了网络中的学习影响采纳问题。在这个问题中，传染性实体（如传染病、计算机病毒或社交媒体模因）通过网络传播，目标是通过只采样少量节点并观察/测试它们的状态来学习每个单独节点的状态。我们在异构网络中研究这个问题，在异构网络中，每个单独的节点都有一组不同的特征，这些特征决定了它如何受到传播实体的影响。针对该学习问题的两种变体，对应于有症状和无症状传播，我们给出了一种具有接近最优样本复杂度的有效算法。在每种情况下，最优样本复杂度自然概括了学习节点在孤立情况下如何受到影响的复杂性，以及学习的复杂性影响同质网络中的采用。
We study the problem of learning influence adoption in networks. In this problem, a communicable entity (such as an infectious disease, a computer virus, or a social media meme) propagates through a network, and the goal is to learn the state of each individual node by sampling only a small number of nodes and observing/testing their states. We study this problem in heterogeneous networks, in which each individual node has a set of distinct features that determine how it is affected by the propagating entity. We give an efficient algorithm with nearly optimal sample complexity for two variants of this learning problem, corresponding to symptomatic and asymptomatic spread. In each case, the optimal sample complexity naturally generalizes the complexity of learning how nodes are affected in isolation, and the complexity of learning influence adoption in a homogeneous network.