Heterogeneous micro-structure of percolation in sparse networks

Abstract

We examine the heterogeneous responses of individual nodes in sparse networks to the random removal of a fraction of edges. Using the message-passing formulation of percolation, we discover considerable variation across the network in the probability of a particular node to remain part of the giant component, and in the expected size of small clusters containing that node. In the vicinity of the percolation threshold, weakly non-linear analysis reveals that node-to-node heterogeneity is captured by the recently introduced notion of non-backtracking centrality. We supplement these results for fixed finite networks by a population dynamics approach to analyse random graph models in the infinite system size limit, also providing closed-form approximations for the large mean degree limit of Erdős-Rényi random graphs. Interpreted in terms of the application of percolation to real-world processes, our results shed light on the heterogeneous exposure of different nodes to cascading failures, epidemic spread, and information flow.

7 pages, 6 figures

References in corpus (5)

• A message passing approach for general epidemic models
• Percolation on sparse networks
• Tight lower bound for percolation threshold on a quasi-regular graph
• Nonbacktracking expansion of finite graphs
• Assessing node risk and vulnerability in epidemics on networks

Cited by in corpus (15)

• Predicting the speed of epidemics spreading on networks
• Stability of a Giant Connected Component in a Complex Network
• Spectral Theory of Sparse Non-Hermitian Random Matrices
• Revealing the Micro-Structure of the Giant Component in Random Graph Ensembles
• Smeared phase transitions in percolation on real complex networks
• Impact of presymptomatic transmission on epidemic spreading in contact networks: A dynamic message-passing analysis
• The Fate of Articulation Points and Bredges in Percolation
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments
• On the accuracy of message-passing approaches to percolation in complex networks
• Localization of nonbacktracking centrality on dense subgraphs of sparse networks
• Vaccination with partial transmission and social distancing on contact networks
• Top eigenpair statistics of diluted Wishart matrices
• Overcoming the complexity barrier of the dynamic message-passing method in networks with fat-tailed degree distributions
• Resistance distance distribution in large sparse random graphs
• Uncovering the non-equilibrium stationary properties in sparse Boolean networks