Numerical assessment of the percolation threshold using complement networks

Abstract

Models of percolation processes on networks currently assume locally tree-like structures at low densities, and are derived exactly only in the thermodynamic limit. Finite size effects and the presence of short loops in real systems however cause a deviation between the empirical percolation threshold $p_c$ and its model-predicted value ${\pi }_c$. Here we show the existence of an empirical linear relation between $p_c$ and ${\pi }_c$ across a large number of real and model networks. Such a putatively universal relation can then be used to correct the estimated value of ${\pi }_c$. We further show how to obtain a more precise relation using the concept of the complement graph, by investigating on the connection between the percolation threshold of a network, $p_c$, and that of its complement, ${\bar{p}}_c$.

References in corpus (16)

• The structure and function of complex networks
• The spread of epidemic disease on networks
• Network robustness and fragility: Percolation on random graphs
• Critical phenomena in complex networks
• Random graphs with clustering
• Efficient Monte Carlo algorithm and high-precision results for percolation
• Percolation Critical Exponents in Scale-Free Networks
• Percolation on sparse networks
• Percolation and Epidemic Thresholds in Clustered Networks
• Predicting percolation thresholds in networks
• Percolation on dense graph sequences
• Breaking of the site-bond percolation universality in networks
• Tight lower bound for percolation threshold on a quasi-regular graph
• Beyond the locally tree-like approximation for percolation on real networks
• Network synchronizability analysis: the theory of subgraphs and complementary graphs
• Nonbacktracking expansion of finite graphs