Network robustness and fragility: percolation on random graphs.
By D. Callaway, Mark Newman, Steven H. Strogatz, Duncan J. Watts. Physical Review Letters, 2000
2,332 citations recorded by the source corpus.
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.
Subfields: Computer Networks and Communications, Statistical and Nonlinear Physics, Transportation
View Paper: https://www.semanticscholar.org/paper/52eb4ea8a683ac2b6ae2f61e69a68f12a14c15a4
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Networks and Communications
- Mark Newman
- Guanrong Chen
- Albert-László Barabási
- Marc Barthelemy
- Alessandro Vespignani
- José Fernando Ferreira Mendes
- Sergey N. Dorogovtsev
- Olaf Sporns
In Statistical and Nonlinear Physics
- Mark Newman
- Santo Fortunato
- Albert-László Barabási
- Marc Barthelemy
- Olaf Sporns
- Alex Arenas
- Alessandro Vespignani
- M. A. Porter
In Transportation
- Marc Barthelemy
- Mark Newman
- Albert-László Barabási
- Marta C. González
- Alessandro Vespignani
- Nicola Perra
- Reza Olfati-Saber
- Arthur Campbell
Citations in the corpus
- Bipartite Graphs as Models of Complex Networks (2003, methodology): “…by the model generally used before this discovery, although they play a central role in many contexts like the robustness of the Internet [6, 15, 19, 20, 49], the spread of viruses or rumors over the Internet, the Web or other social networks [48, 52, 58], the performance of protocols and…”
- Systemic Risk in Financial Networks: A Survey (2020, neutral): “25See also Callaway et al. (2000) for an earlier discussion of percolation on graphs and such a tradeoff. interdependencies can transmit the shock more widely and more extensively.”
- Network resilience (2020, background): “Here we trace back to their original lucid definitions on resilience and stability that were first proposed in ecology [4], and the robustness in complex networks [770].”
- The “New” Science of Networks (2004, background): “The topic of network motifs, which is gaining attention in the biological sciences (Milo et al. 2002, Shen-Orr et al. 2002), is, in principle, identical to the triad census approach of Holland & Leinhardt (1981). into a long line of work in organizational sociology starting with Burns & Stalker’s (1”
- Spatial Networks (2010, methodology): “In [72, 236], the authors use a generating function formalism in order to compute various quantities and we briefly recall this derivation for the one-dimensional WS network where each site is connected to its k nearest neighbors and where additional shortcuts are added between randomly chosen pairs”
- Robustness and Vulnerability of Scale-Free Random Graphs (2004, methodology): “These were considered experimentally in [Albert et al. 00] and heuristically in [Callaway et al. 00, Cohen et al. 00, Cohen et al. 01].”
- Random Walks on Simplicial Complexes and the normalized Hodge Laplacian (2018, background): “nd applications in a plethora of dierent domains outside social network analysis. For instance, centrality measures have been used to identify pivotal elements in (models of) infrastructure networks [3,20], or to target critical nodes in epidemic spreading processes on networks [43,61]. Conceptually”
- Spread of epidemic disease on networks. (2002, background): “This distribution has been studied before by various authors [7, 36, 37, 40].”
- Assortative mixing in networks. (2002, background): “Assortative mixing also has implications for questions of network resilience, the subject of much discussion in the recent literature [28, 29, 30, 31, 32].”
- Contagion in financial networks (2010, background): “2Other strands of the literature on nancial contagion have focused on the role of liquidity constraints (Kodres and Pritsker (2002)), information asymmetries (Calvo and Mendoza (2000)), and wealth constraints (Kyle and Xiong (2001)).”
- Recent advances in percolation theory and its applications (2015, background): “The study of percolation on graphs with completely general degree distribution is, however, presented in [23], giving exact solutions for a variety of cases, including site percolation, bond percolation, and models in which occupation probabilities depend on vertex degree.”
- The role of venture capital firms in Silicon Valley's complex innovation network (2009, background): “A system is robust when it is able to reconfigure itself to face external shocks (Callaway, Newman, Strogatz & Watts, 2000 ).”
- Evolution and Structure of the Internet: Index (2004, background): “29) it is possible to compute the threshold as a function of the undamaged cut-off kc, for different values of the degree exponent (Callaway et al., 2000).”
- Analysis of a large-scale weighted network of one-to-one human communication (2007, background): “We now turn to an examination of the implications of link removal on the global properties of networks, which has many precedents in the complex network literature [16, 37, 39, 40, 41, 42, 43, 44, 45].”