Efficient algorithm to compute mutually connected components in interdependent networks

Abstract

Mutually connected components (MCCs) play an important role as a measure of resilience in the study of interdependent networks. Despite their importance, an efficient algorithm to obtain the statistics of all MCCs during the removal of links has thus far been absent. Here, using a well-known fully dynamic graph algorithm, we propose an efficient algorithm to accomplish this task. We show that the time complexity of this algorithm is approximately $O(N^{1.2})$ for random graphs, which is more efficient than $O(N^2)$ of the brute-force algorithm. We confirm the correctness of our algorithm by comparing the behavior of the order parameter as links are removed with existing results for three types of double-layer multiplex networks. We anticipate that this algorithm will be used for simulations of large-size systems that have been previously inaccessible.

6 pages 5 figures

References in corpus (17)

• Emergence of scaling in random networks
• Catastrophic cascade of failures in interdependent networks
• Temporal Networks
• Universal Behavior of Load Distribution in Scale-free Networks
• Interdependent networks: Reducing the coupling strength leads to a change from a first to second order percolation transition
• Robustness of a Network of Networks
• Robustness of interdependent networks under targeted attack
• The critical effect of dependency groups on the function of networks
• Network robustness of multiplex networks with interlayer degree correlations
• Percolation Theory on Interdependent Networks Based on Epidemic Spreading
• Interdependent networks with correlated degrees of mutually dependent nodes
• Percolation in Interdependent and Interconnected Networks: Abrupt Change from Second to First Order Transition
• Percolation of Partially Interdependent Scale-free Networks
• Are Percolation Transitions always Sharpened by Making Networks Interdependent?
• Mutually connected component of network of networks with replica nodes
• Cavity-based robustness analysis of interdependent networks: Influences of intranetwork and internetwork degree-degree correlations
• Efficient algorithm to study interconnected networks

Cited by in corpus (11)

• Percolation on complex networks: Theory and application
• Percolation in real interdependent networks
• Multilayer Networks in a Nutshell
• Hybrid Phase Transition into an Absorbing State: Percolation and Avalanches
• Multiplex networks with heterogeneous activities of the nodes
• Percolation transitions in the survival of interdependent agents on multiplex networks, catastrophic cascades, and SOS
• Optimal percolation in correlated multilayer networks with overlap
• Universality and scaling laws in the cascading failure model with healing
• Link overlap influences opinion dynamics on multiplex networks: spin model approach
• Realizing interdependent couplings as thermal or higher-order interactions
• Multiplexity amplifies geometry in networks