Emergence of coexisting percolating clusters in networks
arXiv:1508.05590 · doi:10.1103/PhysRevE.93.062308
Abstract
It is commonly assumed in percolation theories that at most one percolating cluster can exist in a network. We introduce sausage-like networks (SLNs), an ensemble of synthetic modular networks in which more than one percolating cluster can appear. We show that coexisting percolating clusters (CPCs) emerge in such networks due to limited mixing, i.e., a small number of interlinks between pairs of modules. We develop an approach called modular message passing (MMP) to describe and verify these observations. We demonstrate that the appearance of CPCs is an important source of inaccuracy in the previously introduced percolation theories, such as the message passing (MP) approach. Moreover, we show that the MMP theory improves significantly over the predictions of MP for percolation on synthetic networks with limited mixing and also on several real-world networks. These findings have important implications for understanding the robustness of networks and in quantifying epidemic outbreaks in the susceptible-infected-recovered (SIR) model of disease spread.
arXiv comment5 pages, 3 figures
References in corpus (26)
- Fast unfolding of communities in large networks
- The structure and function of complex networks
- Finding and evaluating community structure in networks
- Finding community structure in networks using the eigenvectors of matrices
- Maps of random walks on complex networks reveal community structure
- The spread of epidemic disease on networks
- Benchmark graphs for testing community detection algorithms
- Network robustness and fragility: Percolation on random graphs
- A fast Monte Carlo algorithm for site or bond percolation
- Recent advances in percolation theory and its applications
- A message passing approach for general epidemic models
- Percolation on sparse networks
- Resilience to damage of graphs with degree correlations
- Multiresolution community detection for megascale networks by information-based replica correlations
- Robust network community detection using balanced propagation
- Griffiths phases on complex networks
- Accuracy of Mean-Field Theory for Dynamics on Real-World Networks
- Recent advances and open challenges in percolation
- The unreasonable effectiveness of tree-based theory for networks with clustering
- Complex networks vulnerability to module-based attacks
- Deciphering the global organization of clustering in real complex networks
- Breaking of the site-bond percolation universality in networks
- Dynamics on Modular Networks with Heterogeneous Correlations
- Network cloning unfolds the effect of clustering on dynamical processes
- Dynamical Instability in Boolean Networks as a Percolation Problem
- Community detection based on "clumpiness" matrix in complex networks