Universität zu Köln

Hwang, S., Choi, S., Lee, Deokjae and Kahng, B. (2015). Efficient algorithm to compute mutually connected components in interdependent networks. Phys. Rev. E, 91 (2). COLLEGE PK: AMER PHYSICAL SOC. ISSN 1550-2376

Full text not available from this repository.

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.

Item Type:	Journal Article
Creators:	Creators Email ORCID ORCID Put Code Hwang, S. UNSPECIFIED UNSPECIFIED UNSPECIFIED Choi, S. UNSPECIFIED UNSPECIFIED UNSPECIFIED Lee, Deokjae UNSPECIFIED UNSPECIFIED UNSPECIFIED Kahng, B. UNSPECIFIED UNSPECIFIED UNSPECIFIED
URN:	urn:nbn:de:hbz:38-412174
DOI:	10.1103/PhysRevE.91.022814
Journal or Publication Title:	Phys. Rev. E
Volume:	91
Number:	2
Date:	2015
Publisher:	AMER PHYSICAL SOC
Place of Publication:	COLLEGE PK
ISSN:	1550-2376
Language:	English
Faculty:	Unspecified
Divisions:	Unspecified
Subjects:	no entry
Uncontrolled Keywords:	Keywords Language Physics, Fluids & Plasmas; Physics, Mathematical Multiple languages
URI:	http://kups.ub.uni-koeln.de/id/eprint/41217