Efficient algorithm to study interconnected networks

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.

5 pages, 6 figures

References in corpus (2)

• Mitigation of Malicious Attacks on Networks
• Inverse targeting -- an effective immunization strategy

Cited by in corpus (13)

• 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 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