Optimal Dismantling Algorithms for Multiplex Networks Under Layer Node-based Attacks
HAN Jihuia, ZHANG Chengyia, SHI Yuefengb, HU Yinga
a. School of Computer Science and Artificial Intelligence; b. Information Management Center, Zhengzhou University of Light Industry, Zhengzhou 450001, China
Abstract：This study focuses on the optimal dismantling problem in multiplex networks under layer node-based attacks. We propose two novel algorithms that integrate intra-layer structural features and inter-layer connections to precisely evaluate node importance, effectively identifying critical nodes essential for network structure and function. Extensive testing on both synthetic and real-world multiplex networks demonstrates that the proposed algorithms efficiently identify key layer nodes, generate smaller dismantling sets, and maintain low time complexity, making them well-suited for large-scale multiplex networks.
韩继辉, 张程义, 石月凤, 胡颖. 层节点攻击模式下的多层网络最优拆解算法[J]. 复杂系统与复杂性科学, 2026, 23(2): 19-25.
HAN Jihui, ZHANG Chengyi, SHI Yuefeng, HU Ying. Optimal Dismantling Algorithms for Multiplex Networks Under Layer Node-based Attacks[J]. Complex Systems and Complexity Science, 2026, 23(2): 19-25.
[1] ARTIME O, GRASSIA M, DE DOMENICO M, et al. Robustness and resilience of complex networks[J]. Nature Reviews Physics, 2024, 6(2): 114-131. [2] 汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京:高等教育出版社, 2012. [3] ALBERT R, JEONG H, BARABASI A L. Error and attack tolerance of complex networks[J]. Nature, 2000, 406(6794): 378-382. [4] 吴俊, 邓烨, 王志刚, 等. 复杂网络瓦解问题研究进展与展望[J]. 复杂系统与复杂性科学, 2022, 19(3): 1-13. WU J, DENG Y, WANG Z G, et al. Status and prospects on disintegration of complex networks[J]. Complex Systems and Complexity Science, 2022, 19(3): 1-13. [5] BRAUNSTEIN A, DALL’ASTA L, SEMERJIAN G, et al. Network dismantling[J]. Proceedings of the National Academy of Sciences, 2016, 113(44): 12368-73. [6] 王哲, 李建华, 康东,等. 复杂网络鲁棒性增强策略研究综述[J]. 复杂系统与复杂性科学, 2020, 17(3): 1-26. WANG Z, LI J H, KANG D, et al. Review on strategies enhancing the robustness of complex network[J]. Complex Systems and Complexity Science, 2020, 17(3): 1-26. [7] LÜ L Y, CHEN D, REN X L, et al. Vital nodes identification in complex networks[J]. Physics Reports, 2016, 650: 1-63. [8] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation[J]. Nature, 2015, 524(7563): 65-68. [9] MUGISHA S, ZHOU H J. Identifying optimal targets of network attack by belief propagation[J]. Physical Review E, 2016, 94(1): 012305. [10] ZDEBOROVÁ L, ZHANG P, ZHOU H J. Fast and simple decycling and dismantling of networks[J]. Scientific Reports,2016, 6(1): 37954. [11] CLUSELLA P, GRASSBERGER P, PÉREZ-RECHE F J, et al. Immunization and targeted destruction of networks using explosive percolation[J]. Physical Review Letters, 2016, 117(20): 208301. [12] REN X L, GLEINIG N, HELBING D, et al. Generalized network dismantling[J]. Proceedings of the National Academy of Sciences, 2019, 116(14): 6554-9. [13] HAN J H, ZHANG G, DONG G G, et al. Exact analysis of generalized degree-based percolation without memory[J]. Physica A: Statistical Mechanics and Its Applications, 2024, 642: 129776. [14] HUANG Y M, WANG H, REN X L, et al. Identifying key players in complex networks via network entanglement[J]. Communications Physics, 2024, 7(1): 19. [15] XIONG Y, HU Z, SU C, et al. Vital node identification in complex networks based on autoencoder and graph neural network[J]. Applied Soft Computing, 2024, 163: 111895. [16] GRASSIA M, DE DOMENICO M, MANGIONI G. Machine learning dismantling and early-warning signals of disintegration in complex systems[J]. Nature Communications, 2021, 12(1): 5190. [17] DE DOMENICO M. More is different in real-world multilayer networks[J]. Nature Physics, 2023, 19(9): 1247-1262. [18] BOCCALETTI S, BIANCONI G, CRIADO R, et al. The structure and dynamics of multilayer networks[J]. Physics Reports, 2014, 544(1): 1-22. [19] 董政呈, 方彦军, 田猛. 相互依存网络抗毁性研究综述[J]. 复杂系统与复杂性科学, 2017, 14(3): 30-44. DONG Z C, FANG Y J, TIAN M. Review on invulnerability of interdependent networks[J]. Complex Systems and Complexity Science, 2017, 14(3): 30-44. [20] ZHAO D W, WANG L H, ZHI Y F, et al. The robustness of multiplex networks under layer node-based attack[J]. Scientific Reports,2016, 6(1): 24304. [21] OSAT S, FAQEEH A, RADICCHI F. Optimal percolation on multiplex networks[J]. Nature Communications, 2017, 8(1): 1540. [22] BAXTER G J, TIMÁR G, MENDES J F. Targeted damage to interdependent networks[J]. Physical Review E, 2018, 98(3): 032307. [23] QI M, DENG Y, DENG H, et al. Optimal disintegration strategy in multiplex networks[J]. Chaos: an Interdisciplinary Journal of Nonlinear Science, 2018, 28(12): 121104. [24] QI M, BAI Y, LI X, et al. Optimal disintegration strategy in multiplex networks under layer node-based attack[J]. Applied Sciences, 2019, 9(19): 3968. [25] HAN J H, TANG S Y, SHI Y F, et al. An efficient layer node attack strategy to dismantle large multiplex networks[J]. The European Physical Journal B, 2021, 94(3): 74. [26] ERDÖS P, RÉNYI A, BOLLOBÁS B. Publicationes mathematicae debrecen[J]. Random Graphs I,1959, 6: 290. [27] BARABÁSI AL, ALBERT R. Emergence of scaling in random networks[J]. Science, 1999, 286(5439): 509. [28] GOH K I, KAHNG B, KIM D. Universal behavior of load distribution in scale-free networks[J]. Physical Review Letters, 2001, 87(27): 278701. [29] DE DOMENICO M, SOLÉ-RIBALTA A, GÓMEZ S, et al. Navigability of interconnected networks under random failures[J]. Proceedings of the National Academy of Sciences, 2014, 111(23): 8351. [30] CARDILLO A, GÓMEZ-GARDENES J, ZANIN M, et al. Emergence of network features from multiplexity[J]. Scientific Reports, 2013, 3(1): 1344. [31] CHEN B L, HALL D H, CHKLOVSKII D B. Wiring optimization can relate neuronal structure and function[J]. Proceedings of the National Academy of Sciences, 2006, 103(12): 4723-8. [32] DE DOMENICO M, PORTER M A, ARENAS A. MuxViz: a tool for multilayer analysis and visualization of networks[J]. Journal of Complex Networks, 2015, 3(2): 159-76. [33] STARK C, BREITKREUTZ B J, REGULY T, et al. BioGRID: a general repository for interaction datasets[J]. Nucleic Acids Research, 2006, 34(suppl_1):D535-D539. [34] DE DOMENICO M, NICOSIA V, ARENAS A, et al. Structural reducibility of multilayer networks[J]. Nature Communications, 2015, 6(1): 6864.
