Abstract
Developing accurate metrics to evaluate the resilience of large-scale networks, e.g., critical infrastructures, plays a pivotal role in secure operation of these networks. In this paper, we propose a novel framework to study the resilience of a network. To this end, we leverage the tools from Topological Data Analysis (TDA) and Persistent Homology (PH). The combined deployment of TDA and PH tools provides us with a solid understanding of network topology only based on the underlying weighted graph and comparing it with the base network, e.g., fully connected network as the most resilient structure. By utilizing an abstract network to build our arguments and results, we present a step-by-step method to leverage the fundamental theories of TDA to study and improve a network’s resilience. By creating a weighted graph, where weights represent a meaningful attribute to the underlying network, we utilize Vietori–Rips complex and filtration to create persistent diagrams. This allows us to extract topological information to study network resilience. Further, we show how the use of Wasserstein distances can provide detailed information about the critical edges (e.g., roads in transportation networks, or power distribution lines in power networks) in the network, and how adding or removing certain edges affect the level of resilience of the network by presenting a novel metric to quantify the resilience of a network. We evaluate the effectiveness of the proposed method using a case study that compares a base network with networks that include different edges using our resilience metric.
Similar content being viewed by others
Data Availability
In our study we generated our own networks as we were unable to obtain data related to critical infrastructures. This type of information is usually protected as they pertain to national security or are owned and protected by institutions (i.e., overhead power line architectures). The design and steps on how to reproduce the graphs used in this study are explained in detail throughout the sections above.
References
Berizzi A (2004) The italian 2003 blackout. In IEEE Power Engineering Society General Meeting, 2004. IEEE, pp. 1673–1679
Little RG (2002) Controlling cascading failure: Understanding the vulnerabilities of interconnected infrastructures. J Urban Tech 9(1):109–123
Van Eeten M, Nieuwenhuijs A, Luiijf E, Klaver M, Cruz E (2011) The state and the threat of cascading failure across critical infrastructures: the implications of empirical evidence from media incident reports. Publ Admin 89(2):381–400
Gao J, Barzel B, Barabási A-L (2016) Universal resilience patterns in complex networks. Nature 530(7590):307–312
Han SY, DeLaurentis D (2013) Development interdependency modeling for system-of-systems (sos) using bayesian networks: Sos management strategy planning. Proc Comp Sci 16:698–707
Reggiani A (2013) Network resilience for transport security: Some methodological considerations. Trans Pol 28:63–68
Li MZ, Ryerson MS, Balakrishnan H (2019) Topological data analysis for aviation applications. Trans Res Part E: Logistics Trans Rev 128:149–174
Cang Z, Munch E, Wei GW (2020) Evolutionary homology on coupled dynamical systems with applications to protein flexibility analysis. J Appl Comput Topol 4(4):481–507
Nicolau M, Levine AJ, Carlsson G (2011) Topology based data analysis identifies a subgroup of breast cancers with a unique mutational profile and excellent survival. Proc Natl Acad Sci 108(17):7265–7270
Saggar M, Sporns O, Gonzalez-Castillo J, Bandettini PA, Carlsson G, Glover G, Reiss AL (2018) Towards a new approach to reveal dynamical organization of the brain using topological data analysis. Nat Comm 9(1):1–14
Mileyko Y, Mukherjee S, Harer J (2011) Probability measures on the space of persistence diagrams. Inv Prob 27(12):124007
Dufresne E, Edwards P, Harrington H, Hauenstein J (2019) Sampling real algebraic varieties for topological data analysis. 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA)
Chazal F, Glisse M, Labruére C, Michel B (2013) Optimal rates of convergence for persistence diagrams in topological data analysis. arXiv preprint arXiv:1305.6239
Islambekov U, Dey AK, Gel YR, Poor HV (2018) Role of local geometry in robustness of power grid networks. In 2018 IEEE Global Conference on Signal and Information Processing (GlobalSIP), IEEE, pp. 885–889
Edelsbrunner H, Harer JL (2010) Computational topology: An introduction. American Mathematical Soc, Providence, RI, p xii+241
Zomorodian AJ (2005) Topology for computing, vol. 16. Cambridge University Press, Cambridge, p xiv+243
Chazal F, Michel B (2017) An introduction to topological data analysis: fundamental and practical aspects for data scientists
Zomorodian A (2010) Fast construction of the vietoris-rips complex. Comp Graph 34(3):263–271
Acknowledgements
This material is based upon Luiz Manella Pereira’s work supported by the U.S. Department of Homeland Security under Grant Award Number, 2017-ST-062-000002. The views and conclusions contained in this document are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the U.S. Department of Homeland Security.
Funding
Author Luiz Manella Pereira received funding for this study from the U.S. Department of Homeland Security via Grant Award Number 2017-ST-062-000002.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of Interest
The authors declare that they have no conflict of interest.
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
This article is part of the Topical collection on Optimization, Control, and Machine Learning for Interdependent Networks.
Rights and permissions
About this article
Cite this article
Pereira, L.M., Torres, L.C. & Amini, M.H. Topological Data Analysis for Network Resilience Quantification. SN Oper. Res. Forum 2, 29 (2021). https://doi.org/10.1007/s43069-021-00070-3
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s43069-021-00070-3