Percolation on sparse networks

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 non-backtracking matrix.

6 pages, 1 figure, 1 table. This version includes a Supplemental Information section and some changes to the proofs and results in the main paper

References in corpus (3)

• A message passing approach for general epidemic models
• Percolation on correlated networks
• Tight lower bound for percolation threshold on a quasi-regular graph

Cited by in corpus (21)

• Unification of theoretical approaches for epidemic spreading on complex networks
• Percolation in real interdependent networks
• Redundant interdependencies boost the robustness of multilayer networks
• Articulation Points in Complex Networks
• Predicting percolation thresholds in networks
• Breaking of the site-bond percolation universality in networks
• Epidemic spreading and bond percolation in multilayer networks
• Mapping the Structure of Directed Networks: Beyond the "Bow-tie" Diagram
• Tight lower bound for percolation threshold on a quasi-regular graph
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• Network cloning unfolds the effect of clustering on dynamical processes
• Percolation in real multiplex networks
• Assessing node risk and vulnerability in epidemics on networks
• Equitable random graphs
• Dynamic range maximization in excitable networks
• Spectral estimation of the percolation transition in clustered networks
• A network approach for power grid robustness against cascading failures
• Observability transition in real networks
• On the accuracy of message-passing approaches to percolation in complex networks
• Nonbacktracking Bounds on the Influence in Independent Cascade Models
• Spectral bounds for percolation on directed and undirected graphs