Predicting percolation thresholds in networks

Abstract

We consider different methods, that do not rely on numerical simulations of the percolation process, to approximate percolation thresholds in networks. We perform a systematic analysis on synthetic graphs and a collection of 109 real networks to quantify their effectiveness and reliability as prediction tools. Our study reveals that the inverse of the largest eigenvalue of the non-backtracking matrix of the graph often provides a tight lower bound for true percolation threshold. However, in more than 40% of the cases, this indicator is less predictive than the naive expectation value based solely on the moments of the degree distribution. We find that the performance of all indicators becomes worse as the value of the true percolation threshold grows. Thus, none of them represents a good proxy for robustness of extremely fragile networks.

5 pages, 4 figures. Supplemental Material available at http://homes.soic.indiana.edu/filiradi/Mypapers/percolation_arxiv_SI.pdf

References in corpus (18)

• Statistical mechanics of complex networks
• Error and attack tolerance of complex networks
• Epidemic spreading in scale-free networks
• Cooperative Game Theory Approaches for Network Partitioning
• Network robustness and fragility: Percolation on random graphs
• Resilience of the Internet to random breakdowns
• Critical phenomena in complex networks
• Attack vulnerability of complex networks
• Generation of uncorrelated random scale-free networks
• Spectral redemption: clustering sparse networks
• Efficient Monte Carlo algorithm and high-precision results for percolation
• Localization and Spreading of Diseases in Complex Networks
• Localization and centrality in networks
• Cut-offs and finite size effects in scale-free networks
• Percolation on sparse networks
• Percolation on dense graph sequences
• Tight lower bound for percolation threshold on a quasi-regular graph
• Underestimating extreme events in power-law behavior due to machine-dependent cutoffs

Cited by in corpus (35)

• Influence maximization in complex networks through optimal percolation
• Robustness and resilience of complex networks
• Statistical physics of inference: Thresholds and algorithms
• Percolation on complex networks: Theory and application
• Explosive Percolation: Novel critical and supercritical phenomena
• Breaking of the site-bond percolation universality in networks
• The interdependent network of gene regulation and metabolism is robust where it needs to be
• Beyond the locally tree-like approximation for percolation on real networks
• Predicting the epidemic threshold of the susceptible-infected-recovered model
• The localization of non-backtracking centrality in networks and its physical consequences
• Systematic comparison between methods for the detection of influential spreaders in complex networks
• Percolation in real multiplex networks
• Evaluating the Planning and Operational Resilience of Electrical Distribution Systems with Distributed Energy Resources using Complex Network Theory
• Spectral properties and the accuracy of mean-field approaches for epidemics on correlated networks
• Smeared phase transitions in percolation on real complex networks
• Relevance of backtracking paths in epidemic spreading on networks
• Neighborhood Information-based Probabilistic Algorithm for Network Disintegration
• High prevalence regimes in the pair quenched mean-field theory for the susceptible-infected-susceptible model on networks
• Message-Passing Methods for Complex Contagions
• On the numerical study of percolation and epidemic critical properties in networks
• Classes of critical avalanche dynamics in complex networks
• Bond and site color-avoiding percolation in scale free networks
• Heterogeneous message passing for heterogeneous networks
• Explosive percolation in thresholded networks
• Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
• Scaling relations and finite-size scaling in gravitationally correlated lattice percolation models
• Observability transition in real networks
• Influence Maximization: Divide and Conquer
• A sampling-guided unsupervised learning method to capture percolation in complex networks
• Numerical assessment of the percolation threshold using complement networks
• Approximating nonbacktracking centrality and localization phenomena in large networks
• Network-ensemble comparisons with stochastic rewiring and von Neumann entropy
• Exact statistical mechanics of the Ising model on networks
• Quantifying Dismantlement in Disconnected Networks
• Nucleation transitions in polycontextural networks toward consensus