Beyond the locally tree-like approximation for percolation on real networks

Abstract

Theoretical attempts proposed so far to describe ordinary percolation processes on real-world networks rely on the locally tree-like ansatz. Such an approximation, however, holds only to a limited extent, as real graphs are often characterized by high frequencies of short loops. We present here a theoretical framework able to overcome such a limitation for the case of site percolation. Our method is based on a message passing algorithm that discounts redundant paths along triangles in the graph. We systematically test the approach on 98 real-world graphs and on synthetic networks. We find excellent accuracy in the prediction of the whole percolation diagram, with significant improvement with respect to the prediction obtained under the locally tree-like approximation. Residual discrepancies between theory and simulations do not depend on clustering and can be attributed to the presence of loops longer than three edges. We present also a method to account for clustering in bond percolation, but the improvement with respect to the method based on the tree-like approximation is much less apparent.

5 pages, 3 figures. Supplemental Material available here : http://homes.soic.indiana.edu/filiradi/Mypapers/PercolationClustering/Supplemental_revised_ref.pdf

References in corpus (13)

• Finding community structure in networks using the eigenvectors of matrices
• Critical phenomena in complex networks
• Influence maximization in complex networks through optimal percolation
• Random graphs with clustering
• Percolation on sparse networks
• Percolation in real interdependent networks
• Percolation and Epidemic Thresholds in Clustered Networks
• Clustering in complex networks. II. Percolation properties
• Predicting percolation thresholds in networks
• Bond percolation on a class of clustered random networks
• Breaking of the site-bond percolation universality in networks
• Tight lower bound for percolation threshold on a quasi-regular graph
• Network cloning unfolds the effect of clustering on dynamical processes

Cited by in corpus (35)

• Robustness and resilience of complex networks
• Unification of theoretical approaches for epidemic spreading on complex networks
• Percolation on complex networks: Theory and application
• Network models of financial systemic risk: A review
• Redundant interdependencies boost the robustness of multilayer networks
• Message passing theory for percolation models on multiplex networks with link overlap
• Clustering implies geometry in networks
• Epidemic Threshold in Continuous-Time Evolving Networks
• The interdependent network of gene regulation and metabolism is robust where it needs to be
• Epidemic spreading and bond percolation in multilayer networks
• Identifying an influential spreader from a single seed in complex networks via a message-passing approach
• Accurate ranking of influential spreaders in networks based on dynamically asymmetric link-impact
• Message-passing theory for cooperative epidemics
• Percolation in real multiplex networks
• Nonbacktracking expansion of finite graphs
• Contact-based model for epidemic spreading on temporal networks
• Smeared phase transitions in percolation on real complex networks
• Random graphs with arbitrary clustering and their applications
• Percolation and the effective structure of complex networks
• A new design principle of robust onion-like networks self-organized in growth
• Percolation in random graphs with higher-order clustering
• Modelling indirect interactions during failure spreading in a project activity network
• Heterogeneous message passing for heterogeneous networks
• Fragmenting networks by targeting collective influencers at a mesoscopic level
• Self-avoiding walks and connective constants in clustered scale-free networks
• Assessing Percolation Threshold Based on High-Order Non-Backtracking Matrices
• Multiple structural transitions in interacting networks
• Centralities in complex networks
• Observability transition in real networks
• Optimizing spreading dynamics in interconnected networks
• Morphological organization of point-to-point transport in complex networks
• Critical Network Cascades with Re-excitable nodes: Why tree-like approximations usually work, when they breakdown, and how to correct them
• Numerical assessment of the percolation threshold using complement networks
• On the accuracy of message-passing approaches to percolation in complex networks
• Exact statistical mechanics of the Ising model on networks