Efficient algorithm to study interconnected networks
arXiv:1301.2851 · doi:10.1103/PhysRevE.87.043302
Abstract
Interconnected networks have been shown to be much more vulnerable to random and targeted failures than isolated ones, raising several interesting questions regarding the identification and mitigation of their risk. The paradigm to address these questions is the percolation model, where the resilience of the system is quantified by the dependence of the size of the largest cluster on the number of failures. Numerically, the major challenge is the identification of this cluster and the calculation of its size. Here, we propose an efficient algorithm to tackle this problem. We show that the algorithm scales as O(N log N), where N is the number of nodes in the network, a significant improvement compared to O(N^2) for a greedy algorithm, what permits studying much larger networks. Our new strategy can be applied to any network topology and distribution of interdependencies, as well as any sequence of failures.
arXiv comment5 pages, 6 figures
References in corpus (19)
- Emergence of scaling in random networks
- Statistical mechanics of complex networks
- The structure and function of complex networks
- Catastrophic cascade of failures in interdependent networks
- Spatial Networks
- Attack vulnerability of complex networks
- Mitigation of Malicious Attacks on Networks
- Scale-Free Networks are Ultrasmall
- Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition
- Robustness of a Network of Networks
- Suppressing cascades of load in interdependent networks
- A fast Monte Carlo algorithm for site or bond percolation
- Efficient Monte Carlo algorithm and high-precision results for percolation
- The critical effect of dependency groups on the function of networks
- Percolation Theory on Interdependent Networks Based on Epidemic Spreading
- Suppressing Epidemics with a Limited Amount of Immunization Units
- Are Percolation Transitions always Sharpened by Making Networks Interdependent?
- Inverse targeting -- an effective immunization strategy
- Interconnecting bilayer networks
Cited by in corpus (14)
- Multilayer Networks
- Percolation on complex networks: Theory and application
- Optimal interdependence between networks for the evolution of cooperation
- Percolation in real interdependent networks
- Multilayer Networks in a Nutshell
- Self-organization towards optimally interdependent networks by means of coevolution
- Towards designing robust coupled networks
- Towards real-world complexity: an introduction to multiplex networks
- Breathing synchronization in interconnected networks
- Hybrid Phase Transition into an Absorbing State: Percolation and Avalanches
- Cavity-based robustness analysis of interdependent networks: Influences of intranetwork and internetwork degree-degree correlations
- Efficient algorithm to compute mutually connected components in interdependent networks
- Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
- Realizing interdependent couplings as thermal or higher-order interactions