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 (12)

• The spread of epidemic disease on networks
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Attack vulnerability of complex networks
• Spectral redemption: clustering sparse networks
• A message passing approach for general epidemic models
• Percolation on correlated networks
• Non-backtracking random walks mix faster
• Percolation on dense graph sequences
• Tight lower bound for percolation threshold on a quasi-regular graph
• Critical Behaviour of Superfluid ${}^4$He in Aerogel
• Granular Collapse as a Percolation Transition

Cited by in corpus (122)

• Epidemic processes in complex networks
• Influence maximization in complex networks through optimal percolation
• Random walks and diffusion on networks
• Robustness and resilience of complex networks
• Statistical physics of inference: Thresholds and algorithms
• Unification of theoretical approaches for epidemic spreading on complex networks
• Percolation on complex networks: Theory and application
• Percolation in real interdependent networks
• The synchronized dynamics of time-varying networks
• Explosive Percolation: Novel critical and supercritical phenomena
• Redundant interdependencies boost the robustness of multilayer networks
• Suppressing disease spreading by using information diffusion on multiplex networks
• Distinct types of eigenvector localization in networks
• Message passing on networks with loops
• Articulation Points in Complex Networks
• Predicting percolation thresholds in networks
• Message passing theory for percolation models on multiplex networks with link overlap
• Network science based quantification of resilience demonstrated on the Indian Railways Network
• A message-passing approach for recurrent-state epidemic models on networks
• Predicting the speed of epidemics spreading on networks
• Leveraging percolation theory to single out influential spreaders in networks
• Relating Topological Determinants of Complex Networks to Their Spectral Properties: Structural and Dynamical Effects
• Eigenvector localization in real networks and its implications for epidemic spreading
• Breaking of the site-bond percolation universality in networks
• Mutually connected component of network of networks with replica nodes
• Epidemic spreading and bond percolation in multilayer networks
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Rare events and discontinuous percolation transitions
• Mapping the Structure of Directed Networks: Beyond the "Bow-tie" Diagram
• Tight lower bound for percolation threshold on a quasi-regular graph
• Beyond the locally tree-like approximation for percolation on real networks
• Predicting the epidemic threshold of the susceptible-infected-recovered model
• Time-series thresholding and the definition of avalanche size
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• Belief propagation for networks with loops
• Spectra of networks containing short loops
• Spectra of random networks with arbitrary degrees
• Fluctuations in percolation of sparse complex networks
• Controlling the uncertain response of real multiplex networks to random damage
• The localization of non-backtracking centrality in networks and its physical consequences
• Dynamics of social contagions with limited contact capacity
• A message-passing approach to epidemic tracing and mitigation with apps
• Message-passing theory for cooperative epidemics
• Network cloning unfolds the effect of clustering on dynamical processes
• Message passing methods on complex networks
• Percolation in real multiplex networks
• Nonbacktracking expansion of finite graphs
• Contact-based model for epidemic spreading on temporal networks
• Assessing node risk and vulnerability in epidemics on networks
• Smeared phase transitions in percolation on real complex networks
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Hypergraph assortativity: a dynamical systems perspective
• Relevance of backtracking paths in epidemic spreading on networks
• Degree Correlations Amplify the Growth of Cascades in Networks
• Heterogeneous micro-structure of percolation in sparse networks
• Equitable random graphs
• Message-Passing Methods for Complex Contagions
• Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
• Percolation and the effective structure of complex networks
• Targeted influence maximization in complex networks
• Block belief propagation algorithm for two-dimensional tensor networks
• Dynamic range maximization in excitable networks
• Classes of critical avalanche dynamics in complex networks
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Percolation in random graphs with higher-order clustering
• Node Immunization with Non-backtracking Eigenvalues
• Emergence of Robustness in Network of Networks
• Extended-range percolation in complex networks
• Heterogeneous message passing for heterogeneous networks
• Moving the epidemic tipping point through topologically targeted social distancing
• Dismantling Complex Networks by a Neural Model Trained from Tiny Networks
• Spectral estimation of the percolation transition in clustered networks
• Explosive percolation in thresholded networks
• Effect of network clustering on mutually cooperative coinfections
• Fragmenting networks by targeting collective influencers at a mesoscopic level
• Dismantling Efficiency and Network Fractality
• Emergence of coexisting percolating clusters in networks
• General theory for extended-range percolation on simple and multiplex networks
• Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
• Statistical mechanics of bipartite $z$-matchings
• Scaling relations and finite-size scaling in gravitationally correlated lattice percolation models
• A network approach for power grid robustness against cascading failures
• Communities in C.elegans connectome through the prism of non-backtracking walks
• Fragility and anomalous susceptibility of weakly interacting networks
• Loop Series Expansions for Tensor Networks
• Belief propagation on networks with cliques and chordless cycles
• The Fate of Articulation Points and Bredges in Percolation
• Observability transition in real networks
• A sampling-guided unsupervised learning method to capture percolation in complex networks
• Scaling and universality for percolation in random networks: A unified view
• Analysis of the susceptible-infected-susceptible epidemic dynamics in networks via the non-backtracking matrix
• Modeling resource consumption in the US air transportation system via minimum-cost percolation
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments
• Characterizing spatial point processes by percolation transitions
• Cumulative Merging Percolation: A long-range percolation process in networks
• Backtracking activation impacts the criticality of excitable networks
• Generating functions for message-passing on weighted networks: directed bond percolation and SIR epidemics
• Numerical assessment of the percolation threshold using complement networks
• On the accuracy of message-passing approaches to percolation in complex networks
• Localization of nonbacktracking centrality on dense subgraphs of sparse networks
• Pandemic Spread in Communities via Random Graphs
• Exact analytical solution of irreversible binary dynamics on networks
• Multivariate Generating Functions for Information Spread on Multi-Type Random Graphs
• Identifying influential subpopulations in metapopulation epidemic models using message-passing theory
• Combinatorial approach to spreading processes on networks
• Vaccination with partial transmission and social distancing on contact networks
• Systematic assessment of the quality of fit of the stochastic block model for empirical networks
• Nonbacktracking Bounds on the Influence in Independent Cascade Models
• Network compression with configuration models and the minimum description length
• Janus Percolation in Anisotropic Limited-Degree Networks
• Collective Influence of Multiple Spreaders Evaluated by Tracing Real Information Flow in Large-Scale Social Networks
• Fault Tolerance of Random Graphs with respect to Connectivity: Mean-field Approximation for Semi-dense Random Graphs
• Core Influence Mechanism on Vertex-Cover Problem through Leaf-Removal-Core Breaking
• Spectral bounds for percolation on directed and undirected graphs
• Non-Backtracking Centrality Based Random Walk on Networks
• Analytical results for the distribution of first return times of non-backtracking random walks on configuration model networks
• Nonreciprocal random networks and their percolation properties
• Large Fixed-Diameter Graphs are Good Expanders
• A hybrid multiscale coarse-grained method for dynamics on complex networks
• The Perron non-backtracking eigenvalue after node addition
• Approximating nonbacktracking centrality and localization phenomena in large networks
• Globalization emergence in the European Patent Office (EPO) patent network