Network Robustness and Fragility: Percolation on Random Graphs

Duncan S. Callaway, M. E. J. Newman, Steven H. Strogatz, and Duncan J. Watts
Phys. Rev. Lett. 85, 5468 – Published 18 December 2000
PDFExport Citation

Abstract

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.

  • Received 27 July 2000

DOI:https://doi.org/10.1103/PhysRevLett.85.5468

©2000 American Physical Society

Authors & Affiliations

Duncan S. Callaway1, M. E. J. Newman2,3, Steven H. Strogatz1,2, and Duncan J. Watts3,4

  • 1Department of Theoretical and Applied Mechanics, Cornell University, Ithaca, New York 14853-1503
  • 2Center for Applied Mathematics, Cornell University, Ithaca, New York 14853-3801
  • 3Santa Fe Institute, 1399 Hyde Park Road, Santa Fe, New Mexico 87501
  • 4Department of Sociology, Columbia University, 1180 Amsterdam Avenue, New York, New York 10027

References (Subscription Required)

Click to Expand
Issue

Vol. 85, Iss. 25 — 18 December 2000

Reuse & Permissions
Access Options
Author publication services for translation and copyediting assistance advertisement

Authorization Required


×
×

Images

×

Sign up to receive regular email alerts from Physical Review Letters

Log In

Cancel
×

Search


Article Lookup

Paste a citation or DOI

Enter a citation
×