How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks
How Complex Contagions Spread Quickly in the Preferential Attachment Model and Other Time-Evolving Networks
复制标题
复杂的传染病如何在优先依恋模型和其他随时间演化的网络中快速传播
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Grant Schoenbeck
中科院分区：
文献类型：
--
作者：
Roozbeh Ebrahimi;Jie Gao;Golnaz Ghasemiesfeh;Grant Schoenbeck
本文研究了复杂传染病在社会网络中的传播速度。$k$ -复杂的传染从一组最初被感染的种子开始，这样任何至少有$k$感染邻居的节点都会被感染。简单的传染，例如$k=1$，在小世界图中迅速传播到整个网络。然而，复杂传染病的快速传播似乎不太可能发生，而且更加微妙；成功的案例主要取决于网络结构\cite{G08,Ghasemiesfeh:2013:CCW}。
我们的主要结果表明，复杂的传染可以在包括优先依恋模型\cite{barabasi99emergence}在内的时间进化网络的一般家族中快速传播。我们证明，如果选择初始种子作为该家族网络中最古老的节点，则$k$ -复杂传染将在$O(\log n)$步中覆盖整个$n$节点网络。我们证明了初始种子的选择是至关重要的。如果初始种子在PA模型中均匀随机选择，即使它们的数量是多项式，复杂的传染也会过早停止。优先依恋模型中最老的节点可能具有较高的度。然而，我们注意到，实际上并不是幂律度分布本身促进了复杂传染病的快速传播，而是这些模型的进化图结构。上述家族的一些成员甚至没有幂律分布。
我们还证明了复杂传染在复制模型\cite{KumarRaRa00}中是快速的，这是优先依恋家族的一种变体。
最后，我们证明了当一个复杂的传染从一般图上的任意一组初始种子开始时，确定感染顶点的数量是否超过给定阈值是$\mathbf{P}$ -完全的。因此，人们不可能希望在一个图中对所有复杂传染渗透的环境进行分类。
In this paper, we study the spreading speed of complex contagions in a social network. A $k$-complex contagion starts from a set of initially infected seeds such that any node with at least $k$ infected neighbors gets infected. Simple contagions, i.e., $k=1$, quickly spread to the entire network in small world graphs. However, fast spreading of complex contagions appears to be less likely and more delicate; the successful cases depend crucially on the network structure~\cite{G08,Ghasemiesfeh:2013:CCW}.
Our main result shows that complex contagions can spread fast in a general family of time-evolving networks that includes the preferential attachment model~\cite{barabasi99emergence}. We prove that if the initial seeds are chosen as the oldest nodes in a network of this family, a $k$-complex contagion covers the entire network of $n$ nodes in $O(\log n)$ steps. We show that the choice of the initial seeds is crucial. If the initial seeds are uniformly randomly chosen in the PA model, even with a polynomial number of them, a complex contagion would stop prematurely. The oldest nodes in a preferential attachment model are likely to have high degrees. However, we remark that it is actually not the power law degree distribution per se that facilitates fast spreading of complex contagions, but rather the evolutionary graph structure of such models. Some members of the said family do not even have a power-law distribution.
We also prove that complex contagions are fast in the copy model~\cite{KumarRaRa00}, a variant of the preferential attachment family.
Finally, we prove that when a complex contagion starts from an arbitrary set of initial seeds on a general graph, determining if the number of infected vertices is above a given threshold is $\mathbf{P}$-complete. Thus, one cannot hope to categorize all the settings in which complex contagions percolate in a graph.