2000/07/31 by D. S. Callaway, M. E. J. Newman, S. H. Strogatz +1 · 3 citations
Computer Science · Mathematics · Physics and Astronomy · Social Sciences · #Combinatorics #Complex Network Analysis Techniques #Complex network #Computer science #Continuum percolation theory #Critical exponent #Degree distribution #Discrete mathematics #Graph #Human Mobility and Location-Based Analysis #Mathematics #Opportunistic and Delay-Tolerant Networks #Percolation critical exponents #Percolation theory #Physics #Random graph #Scaling #Statistical physics #Theoretical computer science #Topology (electrical circuits) #Vertex (graph theory) #cond-mat.dis-nn #cond-mat.stat-mech
paper · pdf · doi:10.1103/physrevlett.85.5468
published as Phys. Rev. Lett. 85, 5468-5471 (2000). · 4 pages, 2 figures
arxiv created 2000/10/19 · arxiv updated 2009/11/30
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.