Percolation on Sparse Networks

Brian Karrer, M. E. J. Newman, and Lenka Zdeborová
Phys. Rev. Lett. 113, 208702 – Published 12 November 2014
PDFHTMLExport Citation

Abstract

We study percolation on networks, which is used as a model of the resilience of networked systems such as the Internet to attack or failure and as a simple model of the spread of disease over human contact networks. We reformulate percolation as a message passing process and demonstrate how the resulting equations can be used to calculate, among other things, the size of the percolating cluster and the average cluster size. The calculations are exact for sparse networks when the number of short loops in the network is small, but even on networks with many short loops we find them to be highly accurate when compared with direct numerical simulations. By considering the fixed points of the message passing process, we also show that the percolation threshold on a network with few loops is given by the inverse of the leading eigenvalue of the so-called nonbacktracking matrix.

  • Figure
  • Received 12 June 2014

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

© 2014 American Physical Society

Authors & Affiliations

Brian Karrer1, M. E. J. Newman1, and Lenka Zdeborová2

  • 1Department of Physics, University of Michigan, Ann Arbor, Michigan 48109, USA
  • 2Institut de Physique Théorique, CEA Saclay and URA 2306, CNRS, 91191 Gif-sur-Yvette, France

See Also

Tight Lower Bound for Percolation Threshold on an Infinite Graph

Kathleen E. Hamilton and Leonid P. Pryadko
Phys. Rev. Lett. 113, 208701 (2014)

Article Text (Subscription Required)

Click to Expand

Supplemental Material (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand
Issue

Vol. 113, Iss. 20 — 14 November 2014

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
×