|
|
|
| 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.
|
|
Received: 19 April 2024
Published: 19 May 2026
|
|
|
|
|
|
[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. |
|
|
|
