%0 Journal Article %1 Hwang2015Efficient %A Hwang, S. %A Choi, S. %A Lee, Deokjae %A Kahng, B. %D 2015 %J Physical Review E %K percolation algorithms interdependent-networks %N 2 %R 10.1103/PhysRevE.91.022814 %T Efficient algorithm to compute mutually connected components in interdependent networks %U http://dx.doi.org/10.1103/PhysRevE.91.022814 %V 91 %X Mutually connected components (MCCs) play an important role as a measure of resilience in the study of interconnected networks. Despite their importance, an efficient algorithm to obtain physical properties of all MCCs during the removals of links is not available. Here, using a well-known fully-dynamic graph algorithm, we propose an efficient algorithm to accomplish this. We show that the time complexity of this algorithm is approximately \$O(N^1.2)\$, which is more efficient than the brute-force algorithm with complexity \$O(N^2)\$. We anticipate this algorithm to allow simulations with complex dynamic rules to research a size regime that was not permitted before.

@article{Hwang2015Efficient, abstract = {Mutually connected components (MCCs) play an important role as a measure of resilience in the study of interconnected networks. Despite their importance, an efficient algorithm to obtain physical properties of all MCCs during the removals of links is not available. Here, using a well-known fully-dynamic graph algorithm, we propose an efficient algorithm to accomplish this. We show that the time complexity of this algorithm is approximately \$\mathcal{O}(N^{1.2})\$, which is more efficient than the brute-force algorithm with complexity \$\mathcal{O}(N^{2})\$. We anticipate this algorithm to allow simulations with complex dynamic rules to research a size regime that was not permitted before.}, added-at = {2019-06-10T14:53:09.000+0200}, archiveprefix = {arXiv}, author = {Hwang, S. and Choi, S. and Lee, Deokjae and Kahng, B.}, biburl = {https://www.bibsonomy.org/bibtex/20eb1a38a74b9126663ce952937b69fb2/nonancourt}, citeulike-article-id = {13346477}, citeulike-linkout-0 = {http://dx.doi.org/10.1103/PhysRevE.91.022814}, citeulike-linkout-1 = {http://arxiv.org/abs/1409.1147}, citeulike-linkout-2 = {http://arxiv.org/pdf/1409.1147}, day = 23, doi = {10.1103/PhysRevE.91.022814}, eprint = {1409.1147}, interhash = {8ead824c688700484f48493b598b8272}, intrahash = {0eb1a38a74b9126663ce952937b69fb2}, issn = {1550-2376}, journal = {Physical Review E}, keywords = {percolation algorithms interdependent-networks}, month = feb, number = 2, posted-at = {2014-09-04 10:26:06}, priority = {2}, timestamp = {2019-08-01T15:38:00.000+0200}, title = {{Efficient algorithm to compute mutually connected components in interdependent networks}}, url = {http://dx.doi.org/10.1103/PhysRevE.91.022814}, volume = 91, year = 2015 }