Percolation and the effective structure of complex networks

Abstract

Analytical approaches to model the structure of complex networks can be distinguished into two groups according to whether they consider an intensive (e.g., fixed degree sequence and random otherwise) or an extensive (e.g., adjacency matrix) description of the network structure. While extensive approaches---such as the state-of-the-art Message Passing Approach---typically yield more accurate predictions, intensive approaches provide crucial insights on the role played by any given structural property in the outcome of dynamical processes. Here we introduce an intensive description that yields almost identical predictions to the ones obtained with MPA for bond percolation. Our approach distinguishes nodes according to two simple statistics: their degree and their position in the core-periphery organization of the network. Our near-exact predictions highlight how accurately capturing the long-range correlations in network structures allows to easily and effectively compress real complex network data.

11 pages, 4 figures

References in corpus (17)

• Uncovering the overlapping community structure of complex networks in nature and society
• Finding community structure in networks using the eigenvectors of matrices
• Community Structure in Jazz
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• What's in a crowd? Analysis of face-to-face behavioral networks
• Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems
• Layer aggregation and reducibility of multilayer interconnected networks
• Sustaining the Internet with Hyperbolic Mapping
• Self-similarity of complex networks and hidden metric spaces
• Percolation on sparse networks
• Percolation in real interdependent networks
• Spatial Growth of Real-world Networks
• Random graphs containing arbitrary distributions of subgraphs
• Curvature and temperature of complex networks
• Breaking of the site-bond percolation universality in networks
• Relevance of backtracking paths in epidemic spreading on networks
• Spectral estimation of the percolation transition in clustered networks

Cited by in corpus (6)

• Social nucleation: Group formation as a phase transition
• Smeared phase transitions in percolation on real complex networks
• Scaling of percolation transitions on Erdös-Rényi networks under centrality-based attacks
• Interplay between $k$-core and community structure in complex networks
• Heterogeneity in Outcomes of Repeated Instances of Percolation Experiments
• Network compression with configuration models and the minimum description length