General and exact approach to percolation on random graphs
arXiv:1509.01207 · doi:10.1103/PhysRevE.92.062807
Abstract
We present a comprehensive and versatile theoretical framework to study site and bond percolation on clustered and correlated random graphs. Our contribution can be summarized in three main points. (i) We introduce a set of iterative equations that solve the exact distribution of the size and composition of components in finite size quenched or random multitype graphs. (ii) We define a very general random graph ensemble that encompasses most of the models published to this day, and also that permits to model structural properties not yet included in a theoretical framework. Site and bond percolation on this ensemble is solved exactly in the infinite size limit using probability generating functions [i.e., the percolation threshold, the size and the composition of the giant (extensive) and small components]. Several examples and applications are also provided. (iii) Our approach can be adapted to model interdependent graphs---whose most striking feature is the emergence of an extensive component via a discontinuous phase transition---in an equally general fashion. We show how a graph can successively undergo a continuous then a discontinuous phase transition, and preliminary results suggest that clustering increases the amplitude of the discontinuity at the transition.
16 pages, 5 figures
References in corpus (13)
- Critical phenomena in complex networks
- Random graphs with clustering
- Random hypergraphs and their applications
- Random graphs containing arbitrary distributions of subgraphs
- Percolation and Epidemic Thresholds in Clustered Networks
- Multiple percolation transitions in a configuration model of network of networks
- Clustering in complex networks. II. Percolation properties
- Percolation on interacting networks
- Bond percolation on a class of clustered random networks
- Network Observability Transitions
- Spreading of infectious diseases on heterogeneous populations: multi-type network approach
- Critical surfaces for general bond percolation problems
- Multiple Hybrid Phase Transition: Bootstrap Percolation on Complex Networks with Communities
Cited by in corpus (18)
- Networks beyond pairwise interactions: structure and dynamics
- Percolation on complex networks: Theory and application
- Fundamental properties of cooperative contagion processes
- How does bond percolation happen in coloured networks?
- Asymmetric percolation drives a double transition in sexual contact networks
- Age-Stratified COVID-19 Spread Analysis and Vaccination: A Multitype Random Network Approach
- 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
- Percolation in random graphs with higher-order clustering
- Exotic phase transitions of k-cores in clustered networks
- Predicting the diversity of early epidemic spread on networks
- Degree correlations in graphs with clique clustering
- An exact formula for percolation on higher-order cycles
- Exact analytical solution of irreversible binary dynamics on networks
- Network compression with configuration models and the minimum description length
- How universal is the mean-field universality class for percolation in complex networks?
- Nonreciprocal random networks and their percolation properties