title: 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.
authors.affiliation: Institute for Theoretical Physics, University of Cologne, 50937 Köln, Germany.|CCSS and CTP, Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea.
authors.forename: S
authors.initials: S
authors.lastname: Hwang
authors.affiliation: CCSS and CTP, Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea.
authors.forename: S
authors.initials: S
authors.lastname: Choi
authors.affiliation: CCSS and CTP, Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea.
authors.forename: Deokjae
authors.initials: D
authors.lastname: Lee
authors.affiliation: CCSS and CTP, Department of Physics and Astronomy, Seoul National University, Seoul 151-747, Korea.
authors.forename: B
authors.initials: B
authors.lastname: Kahng