Critical node identification in network cascading failure based on load percolation

Hangyu Hu; Fan Wu; Xiaowei Xie; Qiang Wei; Xuemeng Zhai; Guangmin Hu; Hangyu Hu; Fan Wu; Xiaowei Xie; Qiang Wei; Xuemeng Zhai; Guangmin Hu

doi:10.3934/era.2023077

Electronic Research Archive

2023, Volume 31, Issue 3: 1524-1542. doi: 10.3934/era.2023077

Previous Article Next Article

Research article Special Issues

Critical node identification in network cascading failure based on load percolation

School of Information and Communication Engineering, University of Electronic Science and Technology of China, Chengdu 611731, China

Received: 13 September 2022 Revised: 26 December 2022 Accepted: 03 January 2023 Published: 17 January 2023

Identification of network vulnerability is one of the important means of cyberspace operation, management and security. As a typical case of network vulnerability, network cascading failures are often found in infrastructure networks such as the power grid system, communication network and road traffic, where the failure of a few nodes may cause devastating disasters to the whole complex system. Therefore, it is very important to identify the critical nodes in the network cascading failure and understand the internal laws of cascading failure in complex systems so as to fully grasp the vulnerability of complex systems and develop a network management strategy. The existing models for cascading failure analysis mainly evaluate the criticality of nodes by quantifying their importance in the network structure. However, they ignore the important load, node capacity and other attributes in the cascading failure model. In order to address those limitations, this paper proposes a novel critical node identification method in the load network from the perspective of a network adversarial attack. On the basis of obtaining a relatively complete topology, first, the network attack can be modeled as a cascading failure problem for the load network. Then, the concept of load percolation is proposed according to the percolation theory, which is used to construct the load percolation model in the cascading failure problem. After that, the identification method of critical nodes is developed based on the load percolation, which accurately identifies the vulnerable nodes. The experimental results show that the load percolation parameter can discover the affected nodes more accurately, and the final effect is better than those of the existing methods.
- network vulnerability identification,
- network cascading failure,
- critical node identification,
- percolation theory,
- network management
Citation: Hangyu Hu, Fan Wu, Xiaowei Xie, Qiang Wei, Xuemeng Zhai, Guangmin Hu. Critical node identification in network cascading failure based on load percolation[J]. Electronic Research Archive, 2023, 31(3): 1524-1542. doi: 10.3934/era.2023077

Related Papers:

Abstract

Identification of network vulnerability is one of the important means of cyberspace operation, management and security. As a typical case of network vulnerability, network cascading failures are often found in infrastructure networks such as the power grid system, communication network and road traffic, where the failure of a few nodes may cause devastating disasters to the whole complex system. Therefore, it is very important to identify the critical nodes in the network cascading failure and understand the internal laws of cascading failure in complex systems so as to fully grasp the vulnerability of complex systems and develop a network management strategy. The existing models for cascading failure analysis mainly evaluate the criticality of nodes by quantifying their importance in the network structure. However, they ignore the important load, node capacity and other attributes in the cascading failure model. In order to address those limitations, this paper proposes a novel critical node identification method in the load network from the perspective of a network adversarial attack. On the basis of obtaining a relatively complete topology, first, the network attack can be modeled as a cascading failure problem for the load network. Then, the concept of load percolation is proposed according to the percolation theory, which is used to construct the load percolation model in the cascading failure problem. After that, the identification method of critical nodes is developed based on the load percolation, which accurately identifies the vulnerable nodes. The experimental results show that the load percolation parameter can discover the affected nodes more accurately, and the final effect is better than those of the existing methods.

References

[1]	D. J. Watts, A simple model of global cascades on random networks, Proc. Natl. Acad. Sci. U.S.A., 99 (2002), 5766–5771. https://doi.org/10.1073/pnas.082090499 doi: 10.1073/pnas.082090499
[2]	A. E. Motter, Y. C. Lai, Cascade-based attacks on complex networks, Phys. Rev. E: Stat. Phys. Plasmas Fluids Relat. Interdiscip. Top., 66 (2002), 065102. https://doi.org/10.1103/PhysRevE.66.065102 doi: 10.1103/PhysRevE.66.065102
[3]	L. Lü, D. Chen, X. L. Ren, Q. M. Zhang, Y. C. Zhang, T. Zhou, Vital nodes identification in complex networks, Phys. Rep., 650 (2016), 1–63. https://doi.org/10.1016/j.physrep.2016.06.007 doi: 10.1016/j.physrep.2016.06.007
[4]	R. Albert, H. Jeong, A. L. Barabási, Error and attack tolerance of complex networks, Nature, 406 (2000), 378–382. https://doi.org/10.1038/35019019 doi: 10.1038/35019019
[5]	L. D. F. Costa, F. A. Rodrigues, G. Travieso, P. R. Villas Boas, Characterization of complex networks: A survey of measurements, Adv. Phys., 56 (2007), 167–242. https://doi.org/10.1080/00018730601170527 doi: 10.1080/00018730601170527
[6]	H. W. Corley, D. Y. Sha, Most vital links and nodes in weighted networks, Oper. Res. Lett., 1 (1982), 157–160. https://doi.org/10.1016/0167-6377(82)90020-7 doi: 10.1016/0167-6377(82)90020-7
[7]	D. Kempe, J. Kleinberg, É. Tardos, Maximizing the spread of influence through a social network, in Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2003), 137–146. https://doi.org/10.1145/956750.956769
[8]	Y. Chen, G. Paul, S. Havlin, F. Liljeros, H. E. Stanley, Finding a better immunization strategy, Phys. Rev. Lett., 101 (2008), 058701. https://doi.org/10.1103/PhysRevLett.101.058701 doi: 10.1103/PhysRevLett.101.058701
[9]	X. Y. Zhao, B. Huang, M. Tang, H. F. Zhang, D. B. Chen, Identifying effective multiple spreaders by coloring complex networks, Europhys. Lett., 108 (2014), 68005. https://doi.org/10.1209/0295-5075/108/68005 doi: 10.1209/0295-5075/108/68005
[10]	X. Zhang, J. Zhu, Q. Wang, H. Zhao, Identifying influential nodes in complex networks with community structure, Knowledge-Based Syst., 42 (2013), 74–84. https://doi.org/10.1016/j.knosys.2013.01.017 doi: 10.1016/j.knosys.2013.01.017
[11]	F. Morone, H. A. Makse, Influence maximization in complex networks through optimal percolation, Nature, 524 (2015), 65–68. https://doi.org/10.1038/nature14604 doi: 10.1038/nature14604
[12]	P. Panigrahi, S. Maity, Structural vulnerability analysis in small-world power grid networks based on weighted topological model, Int. Trans. Electr. Energy Syst., 30 (2020), e12401. https://doi.org/10.1002/2050-7038.12401 doi: 10.1002/2050-7038.12401
[13]	J. Beyza, J. M. Yusta, G. J. Correa, H. F. Ruiz, Vulnerability assessment of a large electrical grid by new graph theory approach, IEEE Lat. Am. Trans., 16 (2018), 527–535. https://doi.org/10.1109/TLA.2018.8327409 doi: 10.1109/TLA.2018.8327409
[14]	J. Fang, C. Su, Z. Chen, H. Sun, P. Lund, Power system structural vulnerability assessment based on an improved maximum flow approach, IEEE Trans. Smart Grid, 9 (2018), 777–785. https://doi.org/10.1109/TSG.2016.2565619 doi: 10.1109/TSG.2016.2565619
[15]	J. Zhang, F. Hu, S. Wang, Y. Dai, Y. Wang, Structural vulnerability and intervention of high speed railway networks, Physica A, 462 (2016), 743–751. https://doi.org/10.1016/j.physa.2016.06.132 doi: 10.1016/j.physa.2016.06.132
[16]	J. J. Wu, H. J. Sun, Z. Y. Gao, Cascading failures on weighted urban traffic equilibrium networks, Physica A, 386 (2007), 407–413. https://doi.org/10.1016/j.physa.2007.08.034 doi: 10.1016/j.physa.2007.08.034
[17]	J. Wang, L. Rong, L. Zhang, Z. Zhang, Attack vulnerability of scale-free networks due to cascading failures, Physica A, 387 (2008), 6671–6678. https://doi.org/10.1016/j.physa.2008.08.037 doi: 10.1016/j.physa.2008.08.037
[18]	Y. Yang, T. Nishikawa, A. E. Motter, Small vulnerable sets determine large network cascades in power grids, Science, 358 (2017), eaan3184. https://doi.org/10.1126/science.aan3184 doi: 10.1126/science.aan3184
[19]	P. Holme, B. J. Kim, C. N. Yoon, S. K. Han, Attack vulnerability of complex networks, Phys. Rev. E, 65 (2002), 056109. https://doi.org/10.1103/PhysRevE.65.056109 doi: 10.1103/PhysRevE.65.056109
[20]	P. Holme, Edge overload breakdown in evolving networks, Phys. Rev. E, 66 (2002), 036119. https://doi.org/10.1103/PhysRevE.66.036119 doi: 10.1103/PhysRevE.66.036119
[21]	L. Huang, L. Yang, K. Q. Yang, Geographical effects on cascading breakdowns of scale-free networks, Phys. Rev. E, 73 (2006), 036102. https://doi.org/10.1103/PhysRevE.73.036102 doi: 10.1103/PhysRevE.73.036102
[22]	L. Dobson, B. A. Carreras, V. E. Lynch, D. E. Newman, An initial model for complex dynamics in electric power system blackouts, in 34th Hawaii International Conference on System Sciences (HICSS), IEEE, Maui, USA, (2001), 710–718. https://doi.org/10.1109/HICSS.2001.926274
[23]	I. Dobson, B. A. Carreras, D. E. Newman, A probabilistic loading-dependent model of cascading failure and possible implications for blackouts, in 36th Hawaii International Conference on System Sciences (HICSS), IEEE, Big Island, USA, (2003), 10. https://doi.org/10.1109/HICSS.2003.1173909
[24]	L. D. Valdez, L. Shekhtman, C. E. L. Rocca, X. Zhang, S. V. Buldyrev, P. A. Trunfio, et al., Cascading failures in complex networks, J. Complex Networks, 8 (2020), cnaa013. https://doi.org/10.1093/comnet/cnaa022 doi: 10.1093/comnet/cnaa022
[25]	R. Parshani, S. V. Buldyrev, S. Havlin, Critical effect of dependency groups on the function of networks, Proc. Natl. Acad. Sci. U.S.A., 108 (2011), 1007–1010. https://doi.org/10.1073/pnas.10084041 doi: 10.1073/pnas.10084041
[26]	B. A. Carreras, D. E. Newman, I. Dobson, North American blackout time series statistics and implications for blackout risk, IEEE Trans. Power Syst., 31 (2016), 4406–4414. https://doi.org/10.1109/TPWRS.2015.2510627 doi: 10.1109/TPWRS.2015.2510627
[27]	J. W. Wang, L. L. Rong, D. Wang, Model for cascading failures on complex networks based on local characteristics of nodes, J. Manage. Sci. China, 13 (2010), 42–50.
[28]	D. H. Kim, A. E. Motter, Resource allocation pattern in infrastructure networks, J. Phys. A: Math. Theor., 41 (2008), 224019. https://doi.org/10.1088/1751-8113/41/22/224019 doi: 10.1088/1751-8113/41/22/224019
[29]	M. Li, R. R. Liu, L. Lü, M. B. Hu, S. Xu, Y. C. Zhang, Percolation on complex networks: theory and application, Phys. Rep., 907 (2021), 1–68. https://doi.org/10.1016/j.physrep.2020.12.003 doi: 10.1016/j.physrep.2020.12.003
[30]	S. Boccaletti, G. Bianconi, R. Criado, C. I. Del Genio, J. Gómez-Gardenes, M. Romance, et al., The structure and dynamics of multilayer networks, Phys. Rep., 544 (2014), 1–122. https://doi.org/10.1016/j.physrep.2014.07.001 doi: 10.1016/j.physrep.2014.07.001
[31]	Y. Y. Cao, R. R. Liu, C. X. Jia, B. H. Wang, Percolation in multilayer complex networks with connectivity and interdependency topological structures, Commun. Nonlinear Sci., 92 (2021), 105492. https://doi.org/10.1016/j.cnsns.2020.105492 doi: 10.1016/j.cnsns.2020.105492
[32]	R. R. Liu, D. A. Eisenberg, T. P. Seager, Y. C. Lai, The "weak" interdependence of infrastructure systems produces mixed percolation transitions in multilayer networks, Sci. Rep., 8 (2018), 1–13. https://doi.org/10.1038/s41598-018-20019-7 doi: 10.1038/s41598-018-20019-7
[33]	L. Zhang, J. Ren, Inhomogeneous percolation on multilayer networks, J. Stat. Mech: Theory Exp., 3 (2019), 033204. https://doi.org/10.1088/1742-5468/ab02ea doi: 10.1088/1742-5468/ab02ea
[34]	C. Yang, Z. Chen, Percolation on multi-layer network with joint storage and processing capacities, in 13th International Conference on Computer Modeling and Simulation (ICCMS), ACM, Melbourne, Australia, (2021), 114–120. https://doi.org/10.1145/3474963.3474979
[35]	B. Mirzasoleiman, M. Babaei, M. Jalili, M. Safari, Cascaded failures in weighted networks, Phys. Rev. E, 84 (2011), 046114. https://doi.org/10.1103/PhysRevE.84.046114 doi: 10.1103/PhysRevE.84.046114
[36]	T. Xu, A. B. Birchfield, K. M. Gegner, K. S. Shetye, T. J. Overbye, Application of large-scale synthetic power system models for energy economic studies, in 50th Hawaii International Conference on System Sciences (HICSS), IEEE, Waikoloa Village, USA, (2017), 3123–3129.
[37]	J. Quirós-Tortós, R. Sánchez-García, J. Brodzki, J. Bialek, V. Terzija, Constrained spectral clustering-based methodology for intentional controlled islanding of large-scale power systems, IET. Gener. Transm. Distrib., 9 (2015), 31–42. https://doi.org/10.1049/iet-gtd.2014.0228 doi: 10.1049/iet-gtd.2014.0228
[38]	V. Latora, M. Marchiori, Efficient behavior of small-world networks, Phys. Rev. Lett., 87 (2001), 198701. https://doi.org/10.1103/PhysRevLett.87.198701 doi: 10.1103/PhysRevLett.87.198701

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)