Epidemic thresholds in real networks
Epidemic thresholds in real networks
复制标题
DOI：
10.1145/1284680.1284681
复制
发表时间：
2008-01-01
影响因子：
--
通讯作者：
Faloutsos, Christos
中科院分区：
文献类型：
--
作者：
Chakrabarti, Deepayan;Wang, Yang;Faloutsos, Christos
病毒如何在真实的网络中传播？给定感染率和病毒死亡率的特定值，对网络进行消毒需要多长时间？哪一个是免疫的最佳节点？解决这些问题对于制定全网络的反病毒策略至关重要。此外，病毒式传播在原理上与谣言、信息和“时尚”的传播非常相似，这意味着病毒式传播的解决方案也将为这些其他问题提供见解。我们通过开发一个非线性动力系统（NLDS）来回答这些问题，该系统可以精确地模拟任何网络中的病毒传播，包括真实的和合成的网络图。我们提出了一个一般的NLDS系统的流行病阈值条件：我们证明了网络的流行病阈值正是其邻接矩阵的最大特征值的逆。最后，我们表明，在流行阈值以下，感染以指数速度死亡。我们的流行病阈值模型包含了许多已知的特殊情况图的阈值（例如，例如，在一个实施例中，Erdros-Renyi，BA powerlaw，homogeneous）.我们证明了我们的模型的预测能力与广泛的实验真实的和合成的图形，并表明我们的阈值条件适用于任意图形。最后，我们展示了如何利用我们的阈值条件的实际用途：它可以决定哪些节点免疫;它可以评估节流策略的影响;它可以帮助我们设计网络拓扑结构，使它们更能抵抗病毒。
How will a virus propagate in a real network? How long does it take to disinfect a network given particular values of infection rate and virus death rate? What is the single best node to immunize? Answering these questions is essential for devising network-wide strategies to counter viruses. In addition, viral propagation is very similar in principle to the spread of rumors, information, and "fads," implying that the solutions for viral propagation would also offer insights into these other problem settings. We answer these questions by developing a nonlinear dynamical system (NLDS) that accurately models viral propagation in any arbitrary network, including real and synthesized network graphs. We propose a general epidemic threshold condition for the NLDS system: we prove that the epidemic threshold for a network is exactly the inverse of the largest eigenvalue of its adjacency matrix. Finally, we show that below the epidemic threshold, infections die out at an exponential rate. Our epidemic threshold model subsumes many known thresholds for special-case graphs (e. g., Erdros-Renyi, BA powerlaw, homogeneous). We demonstrate the predictive power of our model with extensive experiments on real and synthesized graphs, and show that our threshold condition holds for arbitrary graphs. Finally, we show how to utilize our threshold condition for practical uses: It can dictate which nodes to immunize; it can assess the effects of a throttling policy; it can help us design network topologies so that they are more resistant to viruses.