Evaluating the Cascade Effect in Interdependent Networks via Algebraic Connectivity
Main Article Content
Keywords
Interconnected networks, Network robustness, Topopogical matrics, Algebraic connectivity, Average node degree, Cascade effects
Abstract
Understanding how the underlying network structure and interconnectivity impact on the robustness of the interdependent networks is a major challenge in complex networks studies. There are some existing metrics that can be used to measure network robustness. However, different metrics such as the average node degree interprets different characteristic of network topological structure, especially less metrics have been identified to effectively evaluate the cascade performance in interdependent networks. In this paper, we propose to use a combined Laplacian matrix to model the interdependent networks and their interconnectivity, and then use its algebraic connectivity metric as a measure to evaluate its cascading behavior. Moreover, we have conducted extensive comparative studies among different metrics such as the average node degree, and the proposed algebraic connectivity. We have found that the algebraic connectivity metric can describe more accurate and finer characteristics on topological structure of the interdependent networks than other metrics widely adapted by the existing research studies for evaluating the cascading performance in interdependent networks.
References
Andersson, G., et al. "Causes of the 2003 Major Grid Blackouts in North America and Europe, and Recommended Means to Improve System Dynamic Performance." IEEE Transactions on Power Systems 20.4 (2005): 1922-1928.
Bak, Per, Chao Tang, and Kurt Wiesenfeld. "Self-Organized Criticality." Physical review A 38.1 (1988): 364-374.
Bak, Per, Chao Tang, and Kurt Wiesenfeld. "Self-Organized Criticality: An Explanation of the 1/F Noise." Physical review letters 59.4 (1987): 381-384.
Banerjee, Anirban, and Jürgen Jost. "Graph Spectra as a Systematic Tool in Computational Biology." Discrete Applied Mathematics 157.10 (2009): 2425-2431.
Brummitt, Charles D, Raissa M D’Souza, and EA Leicht. "Suppressing Cascades of Load in Interdependent Networks." Proceedings of the National Academy of Sciences 109.12 (2012): E680-E689.
Buldyrev, Sergey V., et al. "Catastrophic Cascade of Failures in Interdependent Networks." Nature 464.7291 (2010): 1025-1028.
Buldyrev, Sergey V., Nathaniel W. Shere, and Gabriel A. Cwilich. "Interdependent Networks with Identical Degrees of Mutually Dependent Nodes." Physical Review E 83.1 (2011): 016112(1)-016112(8).
Dobson, Ian, et al. "Complex Systems Analysis of Series of Blackouts: Cascading Failure, Critical Points, and Self-Organization." Chaos: An Interdisciplinary Journal of Nonlinear Science 17.2 (2007): 026103(03)-026103(13).
Ellens, Wendy, and Robert E Kooij. "Graph Measures and Network Robustness." arXiv preprint arXiv:1311.5064 (2013): 1-12.
Estrada, Ernesto, and Naomichi Hatano. "Communicability Graph and Community Structures in Complex Networks." Applied Mathematics and Computation 214.2 (2009): 500-511.
Fiedler, Miroslav. "Algebraic Connectivity of Graphs." Czechoslovak Mathematical Journal 23.2 (1973): 298-305.
Fiedler, Miroslav. "A Property of Eigenvectors of Nonnegative Symmetric Matrices and Its Application to Graph Theory." Czechoslovak Mathematical Journal 25.4 (1975): 619-633.
Gao, Jianxi, et al. "Networks Formed from Interdependent Networks." Nature Physics 8.1 (2012): 40-48.
Github. "Networkx." 2014. Web. 29 December 2014.
Huang, Xuqing, et al. "Robustness of Interdependent Networks under Targeted Attack." Physical Review E 83.6 (2011): 065101(1)-065101(4).
Liu, W., et al. "Utility of Algebraic Connectivity Metric in Topology Design of Survivable Networks." The 7th International Workshop on Design of Reliable Communication Networks. (2009): 131-138.
Mahadevan, Priya, et al. "The Internet as-Level Topology: Three Data Sources and One Definitive Metric." ACM SIGCOMM Computer Communication Review 36.1 (2006): 17-26.
Parshani, Roni, Sergey V. Buldyrev, and Shlomo Havlin. "Interdependent Networks: Reducing the Coupling Strength Leads to a Change from a First to Second Order Percolation Transition." Physical Review Letters 105.4 (2010): 048701(1)-048701(4).
Schneider, Christian M., et al. "Towards Designing Robust Coupled Networks." Sci. Rep. 3 (2013): 1-8.
Shao, Jia, et al. "Cascade of Failures in Coupled Network Systems with Multiple Support-Dependence Relations." Physical Review E 83.3 (2011): 036116(1)-036116(9).
Sydney, Ali, Caterina Scoglio, and Don Gruenbacher. "Optimizing Algebraic Connectivity by Edge Rewiring." Applied Mathematics and computation 219.10 (2013): 5465-5479.
Tan, Hu, and Minfang Peng. "Minimization of Ambiguity in Parametric Fault Diagnosis of Analog Circuits: A Complex Network Approach." Applied Mathematics and Computation 219.1 (2012): 408-415.
Van Mieghem, Piet. Graph Spectra for Complex Networks. Cambridge University Press, 2011.
Yagan, O., et al. "Optimal Allocation of Interconnecting Links in Cyber-Physical Systems: Interdependence, Cascading Failures, and Robustness." IEEE Transactions on Parallel and Distributed Systems 23.9 (2012): 1708-1720.
Yan, Ye, et al. "A Survey on Smart Grid Communication Infrastructures: Motivations, Requirements and Challenges." IEEE Communications Surveys & Tutorials 15.1 (2013): 5-20.
Yizheng, Fan. "On Spectral Integral Variations of Graphs." Linear and Multilinear Algebra 50.2 (2002): 133-42.
Zhang, Ju-ping, and Zhen Jin. "Epidemic Spreading on Complex Networks with Community Structure." Applied Mathematics and Computation 219.6 (2012): 2829-2838.
Bak, Per, Chao Tang, and Kurt Wiesenfeld. "Self-Organized Criticality." Physical review A 38.1 (1988): 364-374.
Bak, Per, Chao Tang, and Kurt Wiesenfeld. "Self-Organized Criticality: An Explanation of the 1/F Noise." Physical review letters 59.4 (1987): 381-384.
Banerjee, Anirban, and Jürgen Jost. "Graph Spectra as a Systematic Tool in Computational Biology." Discrete Applied Mathematics 157.10 (2009): 2425-2431.
Brummitt, Charles D, Raissa M D’Souza, and EA Leicht. "Suppressing Cascades of Load in Interdependent Networks." Proceedings of the National Academy of Sciences 109.12 (2012): E680-E689.
Buldyrev, Sergey V., et al. "Catastrophic Cascade of Failures in Interdependent Networks." Nature 464.7291 (2010): 1025-1028.
Buldyrev, Sergey V., Nathaniel W. Shere, and Gabriel A. Cwilich. "Interdependent Networks with Identical Degrees of Mutually Dependent Nodes." Physical Review E 83.1 (2011): 016112(1)-016112(8).
Dobson, Ian, et al. "Complex Systems Analysis of Series of Blackouts: Cascading Failure, Critical Points, and Self-Organization." Chaos: An Interdisciplinary Journal of Nonlinear Science 17.2 (2007): 026103(03)-026103(13).
Ellens, Wendy, and Robert E Kooij. "Graph Measures and Network Robustness." arXiv preprint arXiv:1311.5064 (2013): 1-12.
Estrada, Ernesto, and Naomichi Hatano. "Communicability Graph and Community Structures in Complex Networks." Applied Mathematics and Computation 214.2 (2009): 500-511.
Fiedler, Miroslav. "Algebraic Connectivity of Graphs." Czechoslovak Mathematical Journal 23.2 (1973): 298-305.
Fiedler, Miroslav. "A Property of Eigenvectors of Nonnegative Symmetric Matrices and Its Application to Graph Theory." Czechoslovak Mathematical Journal 25.4 (1975): 619-633.
Gao, Jianxi, et al. "Networks Formed from Interdependent Networks." Nature Physics 8.1 (2012): 40-48.
Github. "Networkx." 2014. Web. 29 December 2014.
Huang, Xuqing, et al. "Robustness of Interdependent Networks under Targeted Attack." Physical Review E 83.6 (2011): 065101(1)-065101(4).
Liu, W., et al. "Utility of Algebraic Connectivity Metric in Topology Design of Survivable Networks." The 7th International Workshop on Design of Reliable Communication Networks. (2009): 131-138.
Mahadevan, Priya, et al. "The Internet as-Level Topology: Three Data Sources and One Definitive Metric." ACM SIGCOMM Computer Communication Review 36.1 (2006): 17-26.
Parshani, Roni, Sergey V. Buldyrev, and Shlomo Havlin. "Interdependent Networks: Reducing the Coupling Strength Leads to a Change from a First to Second Order Percolation Transition." Physical Review Letters 105.4 (2010): 048701(1)-048701(4).
Schneider, Christian M., et al. "Towards Designing Robust Coupled Networks." Sci. Rep. 3 (2013): 1-8.
Shao, Jia, et al. "Cascade of Failures in Coupled Network Systems with Multiple Support-Dependence Relations." Physical Review E 83.3 (2011): 036116(1)-036116(9).
Sydney, Ali, Caterina Scoglio, and Don Gruenbacher. "Optimizing Algebraic Connectivity by Edge Rewiring." Applied Mathematics and computation 219.10 (2013): 5465-5479.
Tan, Hu, and Minfang Peng. "Minimization of Ambiguity in Parametric Fault Diagnosis of Analog Circuits: A Complex Network Approach." Applied Mathematics and Computation 219.1 (2012): 408-415.
Van Mieghem, Piet. Graph Spectra for Complex Networks. Cambridge University Press, 2011.
Yagan, O., et al. "Optimal Allocation of Interconnecting Links in Cyber-Physical Systems: Interdependence, Cascading Failures, and Robustness." IEEE Transactions on Parallel and Distributed Systems 23.9 (2012): 1708-1720.
Yan, Ye, et al. "A Survey on Smart Grid Communication Infrastructures: Motivations, Requirements and Challenges." IEEE Communications Surveys & Tutorials 15.1 (2013): 5-20.
Yizheng, Fan. "On Spectral Integral Variations of Graphs." Linear and Multilinear Algebra 50.2 (2002): 133-42.
Zhang, Ju-ping, and Zhen Jin. "Epidemic Spreading on Complex Networks with Community Structure." Applied Mathematics and Computation 219.6 (2012): 2829-2838.
Article Sidebar
Published
Mar 9, 2015
Article Details
How to Cite
Evaluating the Cascade Effect in Interdependent Networks via Algebraic Connectivity. (2015). International Journal of Information, Communication Technology and Applications, 1(1), 55-68. https://doi.org/10.17972/ajicta2015115
Issue
Section
Articles
Copyright © Australasian Association for Information and Communication Technology General permission to republish, but not for profit, all or part of this material is granted, under the Creative Commons Australian Attribution-NonCommercial-NoDerivs 4.0 Licence, provided that the copyright notice is given and that reference is made to the publication, to its date of issue, and to the fact that reprinting privileges were granted by permission of the Copyright holder.
Author Biography