Network robustness and fragility: Percolation on random graphs
Network robustness and fragility: Percolation on random graphs
复制标题
DOI：
10.1103/physrevlett.85.5468
复制
发表时间：
2000-12-18
影响因子：
8.6
通讯作者：
Watts, DJ
中科院分区：
文献类型：
--
作者：
Callaway, DS;Newman, MEJ;Watts, DJ
最近在互联网、社交网络和电网方面的研究已经解决了这些网络对随机或定向删除网络节点或链路的恢复能力。例如，这种删除包括互联网路由器或电力传输线的故障。随机图上的渗流模型提供了这一过程的简单表示，但通常仅限于顶点具有泊松度分布的图。这样的图与现实世界的网络非常不同，现实世界的网络通常具有幂定律或其他高度偏斜的度分布。本文研究了具有完全广义度分布的图的渗流问题，给出了各种情况下的精确解，包括点渗流、键渗流和占据概率依赖于顶点度的模型。我们讨论了我们的理论在理解网络弹性方面的应用。
Recent work on the Internet, social networks, and the power grid has addressed the resilience of these networks to either random or targeted deletion of network nodes or links. Such deletions include, for example, the failure of Internet routers or power transmission Lines. Percolation models on random graphs provide a simple representation of this process but have typically been limited to graphs with Poisson degree distribution at their vertices. Such graphs are quite unlike real-world networks, which often possess power-law or other highly skewed degree distributions. In this paper we study percolation on graphs with completely general degree distribution, giving exact solutions for a variety of cases, including site percolation, bond percolation, and models in which occupation probabilities depend on vertex degree. We discuss the application of our theory to the understanding of network resilience.