Percolation and the effective structure of complex networks
arXiv:1804.09633 · doi:10.1103/PhysRevX.9.011023
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.
arXiv comment11 pages, 4 figures
References in corpus (43)
- Uncovering the overlapping community structure of complex networks in nature and society
- Finding community structure in networks using the eigenvectors of matrices
- The structure of scientific collaboration networks
- The spread of epidemic disease on networks
- Self-similarity of complex networks
- Community Structure in Jazz
- The complex network of global cargo ship movements
- Structural Properties of the Caenorhabditis elegans Neuronal Network
- Reaction-diffusion processes and metapopulation models in heterogeneous networks
- What's in a crowd? Analysis of face-to-face behavioral networks
- Social Structure of Facebook Networks
- k-core organization of complex networks
- Nonoptimal Component Placement, but Short Processing Paths, due to Long-Distance Projections in Neural Systems
- Layer aggregation and reducibility of multilayer interconnected networks
- Popularity versus Similarity in Growing Networks
- Sustaining the Internet with Hyperbolic Mapping
- Self-similarity of complex networks and hidden metric spaces
- Percolation on sparse networks
- Resilience to damage of graphs with degree correlations
- Efficient Monte Carlo and greedy heuristic for the inference of stochastic block models
- Percolation in real interdependent networks
- Spatial Growth of Real-world Networks
- Random graphs containing arbitrary distributions of subgraphs
- Machine learning meets network science: dimensionality reduction for fast and efficient embedding of networks in the hyperbolic space
- Quantifying randomness in real networks
- Robust classification of salient links in complex networks
- The unreasonable effectiveness of tree-based theory for networks with clustering
- Curvature and temperature of complex networks
- The hidden geometry of weighted complex networks
- Network Geometry Inference using Common Neighbors
- A message-passing approach for recurrent-state epidemic models on networks
- Wiring cost in the organization of a biological network
- Deciphering the global organization of clustering in real complex networks
- Breaking of the site-bond percolation universality in networks
- Multi-scale structure and topological anomaly detection via a new network statistic: The onion decomposition
- Beyond the locally tree-like approximation for percolation on real networks
- Trust transitivity in social networks
- Constrained Markovian dynamics of random graphs
- The Evolution of Wikipedia's Norm Network
- General and exact approach to percolation on random graphs
- Percolation on random networks with arbitrary k-core structure
- 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 -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