Status and Prospects on Disintegration of Complex Networks
WU Jun1, DENG Ye1, WANG Zhigang1, TAN Suoyi2, LI Yapeng2
1. International Academic Center of Complex Systems, Beijing Normal University, Zhuhai 519087, China; 2. College of Systems Engineering, National University of Defense Technology, Changsha 410073, China
Abstract：In the majority of cases, networks are beneficial. However, many times it may also be harmful, such as terrorist networks and disease spreading networks. It has become an urgent challenging problem to disintegrate these harmful networks by various methods such as immunization, block, isolation, disturbance, and attack. The core task of network disintegration is to identify the “critical nodes (edges)”. This survey firstly gives the mathematical description of network disintegration. On this basis, this survey then reviews the status of network disintegration study in the fields of operations research, network science, and computer science based on mathematical programming, the centrality metrics, the heuristic algorithms, evolutionary computation, and machine learning, respectively. Lastly, this survey presents the prospects of network disintegration study from the aspects of the target network, disintegration model, and algorithm.
吴俊, 邓烨, 王志刚, 谭索怡, 李亚鹏. 复杂网络瓦解问题研究进展与展望[J]. 复杂系统与复杂性科学, 2022, 19(3): 1-13.
WU Jun, DENG Ye, WANG Zhigang, TAN Suoyi, LI Yapeng. Status and Prospects on Disintegration of Complex Networks. Complex Systems and Complexity Science, 2022, 19(3): 1-13.
[1] WATTS D J, STROGATZ S H. Collective dynamics of ‘small-world’ networks [J]. Nature, 1998, 393(6684): 440-442. [2] BARABÁSI A L, ALBERT R. Emergence of scaling in random networks [J]. Science, 1999, 286(5439): 509-512. [3] 方锦清, 汪小帆, 郑志刚, 等. 一门崭新的交叉科学:网络科学(上) [J]. 物理学进展, 2007, 27(3): 239-343. FANG J Q, WANG X F, ZHENG Z G, et al. New interdisciplinary science: network science(I)[J]. Prog Phys, 2007, 27(3): 239-343. [4] 方锦清, 汪小帆, 郑志刚, 等. 一门崭新的交叉科学:网络科学(下) [J]. 物理学进展, 2007, 27(4): 361-448. FANG J Q, WANG X F, ZHENG Z G, et al. New interdisciplinary science: network science(II) [J]. Prog Phys, 2007, 27(4): 361-448. [5] 汪小帆, 李翔, 陈关荣. 网络科学导论 [M]. 北京: 高等教育出版社, 2012. [6] 刘作仪. 复杂网络理论及相关管理复杂性研究的资助进展 [J]. 中国科学基金, 2008, 22(1): 13-17. LIU Z Y. Research progress on complexity network and it′s application in the area of management science[J]. Science Foundation in China, 2008, 22(1): 13-17. [7] BARABÁSI A L. Network Science [M]. Cambridge: Cambridge University Press, 2016. [8] SHARGEL B, SAYAMA H, EPSTEIN I R, et al. Optimization of robustness and connectivity in complex networks [J]. Phys Rev Lett, 2003, 90(6): 068701. [9] 谭跃进, 吕欣, 吴俊, 等. 复杂网络抗毁性研究若干问题的思考 [J]. 系统工程理论与实践, 2008, 28(S): 116-120. TAN Y J, LÜ X, WU J, et al. On the invulnerable research of complex networks [J]. System Eng Theor Prac, 2008, 28(S): 116-120. [10] 吴俊, 段东立, 赵娟, 等. 网络系统可靠性研究现状与展望 [J]. 复杂系统与复杂性科学, 2011, 8(2): 77-86. WU J, DUAN D L, ZHAO J, et al. Status and prospects on network reliability [J]. Complex System and Complexity Science, 2011, 8(2): 77-86. [11] SCHNEIDER C M, MOREIRA A A, ANDRADE J S, et al. Mitigation of malicious attacks on networks [J]. Proc Natl Acad Sci USA, 2011, 108(10): 3838-3841. [12] GOUVEIA L, LEITNER M. Design of survivable networks with vulnerability constraints [J]. Eur J Oper Res, 2016, 258(1): 89-103. [13] OUYANG M. A mathematical framework to optimize resilience of interdependent critical infrastructure systems under spatially localized attacks [J]. Eur J Oper Res, 2017, 262(3): 1072-1084. [14] PENG G S, WU J. Optimal network topology for structural robustness based on natural connectivity [J]. Physica A, 2016, 443(2): 212-220. [15] WU J, TAN S Y, LIU Z, et al. Enhancing structural robustness of scale-free networks by information disturbance [J]. Sci Rep, 2017, 7(1): 1-13. [16] 付举磊, 孙多勇, 肖进, 等. 基于社会网络分析理论的恐怖组织网络研究综述 [J]. 系统工程理论与实践, 2013, 33(9): 2177-2186. FU J L, SUN D Y, XIAO J, et al. Review of the research on the terrorist networks based on social network analysis [J]. System Eng Theor Prac, 2013, 33(9): 2177-2186. [17] CARLEY K M, REMINGA J, KAMNEVA N. Destabilizing terrorist networks[C]. Proceedings of the 8th International Command and Control Research and Technology Symposium. Washington DC: National Defense War College, 2003. [18] CHAURASIA N, TIWARI A. Efficient algorithm for destabilization of terrorist networks [J]. Int J Inf Technol Comput Sci, 2013, 12: 21-30. [19] 曹进德, 王毅. 复杂网络疾病传播动力学研究进展 [J]. 大学数学, 2016, 32(4): 1-11. CAO J D, WANG Y. Research developments of disease spread dynamics in complex networks [J]. College Math, 2016, 32(4): 1-11. [20] 孙皓宸, 徐铭达, 许小可. 基于真实人际接触数据的新冠肺炎校园传播与防控 [J]. 电子科技大学学报, 2020, 49(3): 399-407. SUN H C, XU M D, XU X K. Infection and prevention of COVID-19 in schools based on real-life interpersonal contact data [J]. J Univ Electron Sci Technol Chin, 2020, 49(3): 399-407. [21] ANGGRAINI D, MADENDA S, WIBOWO E P, et al. Network disintegration in criminal network[C]. Proceeding of the 11th International Conference on Signal-Image Technology & Internet-Based Systems. Piscataway: IEEE, 2015: 192-199. [22] BRIGHT D, GREENHILL C, BRITZ T, et al. Criminal network vulnerabilities and adaptations [J]. Global Crime, 2017, 18(4): 424-441. [23] MALAVIYA A, RAINWATER C, SHARKEY T. Multi-period network interdiction problems with applications to city-level drug enforcement [J]. IIE Trans, 2012, 44(5): 368-380. [24] MICHALOPOULOS D P, BARNES J W, MORTON D P. Prioritized interdiction of nuclear smuggling via tabu search [J]. Optim Lett, 2015, 9(8): 1477-1494. [25] QUAYLE A P, SIDDIQUI A S, JONES S J M. Preferential network perturbation [J]. Physica A, 2006, 371: 823-840. [26] TRIPATHY R M, BAGCHI A, MEHTA S. A study of rumor control strategies on social networks[C]. Proceedings of the 19th ACM International Conference on Information and Knowledge Management. New York: ACM, 2010: 1817-1820. [27] KOBAYASHI T, HASUI K. Efficient immunization strategies to prevent financial contagion [J]. Sci Rep, 2014, 4(1): 1-7. [28] 金伟新. 体系对抗复杂网络建模与仿真 [M]. 北京: 电子工业出版社, 2010. [29] TAN S Y, WU J, LU L, et al. Efficient network disintegration under incomplete information: the comic effect of link prediction [J]. Sci Rep, 2016, 6: 1-9. [30] WOOD R K. Deterministic network interdiction [J]. Math Comput Model, 1993, 17(2): 1-18. [31] PHILLIPS C A. The network inhibition problem[C]. Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing. New York: ACM, 1993: 776-785. [32] BRAUNSTEIN A, DALL′ASTA L, SEMERJIAN G, et al. Network dismantling [J]. Proc Natl Acad Sci USA, 2016, 113(44): 12368-12373. [33] CARLEY K M, LEE J S, KRACKHARDT D. Destabilizing networks [J]. Connections, 2002, 24(3): 79-92. [34] LALOU M, TAHRAOUI M A, KHEDDOUCI H. The critical node detection problem in networks: a survey [J]. Comput Sci Rev, 2018, 28: 92-117. [35] FARAMONDI L, OLIVA G, SETOLA R, et al. Performance analysis of single and multi-objective approaches for the critical node detection problem[C]. Proceedings of the International Conference on Optimization and Decision Science. Springer, Cham. Berlin: Springer, 2017: 315-324. [36] BORGATTI S P. Identifying sets of key players in a social network [J]. Comput Math Org Theor, 2006, 12(1): 21-34. [37] ZWAAN R V D, BERGER A, GRIGORIEV A. How to cut a graph into many pieces[C]. Proceedings of the International Conference on Theory and Applications of Models of Computation. Berlin Heidelberg: Springer, 2011, 184-194. [38] SHEN S, SMITH J C. Polynomial-time algorithms for solving a class of critical node problems on trees and series-parallel graphs [J]. Networks, 2012, 60(2): 103-119. [39] ALBERT R, JEONG H, BARABÁSI A L. Error and attack tolerance of complex networks [J]. Nature, 2000, 406(6794): 378-382. [40] HOLME P, KIM B J, YOON C N, et al. Attack vulnerability of complex networks [J]. Phys Rev E, 2002, 65(2): 056109. [41] COHEN R, HAVLIN S, BEN-AVRAHAM D. Efficient immunization strategies for computer networks and populations [J]. Phys Rev Lett, 2003, 91: 247901. [42] HOLME P. Efficient local strategies for vaccination and network attack [J]. Europhys Lett, 2004, 68(6): 908-914. [43] GALLOS L K, LILJEROS F, ARGYRAKIS P, et al. Improving immunization strategies [J]. Phys Rev E, 2007, 75(4): 045104. [44] PAJOUH F M, BOGINSKI V, PASILIAO E L. Minimum vertex blocker clique problem [J]. Networks, 2014, 64(1): 48-64. [45] HEWETT R. Toward identification of key breakers in social cyber-physical networks[C]. Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. Piscataway: IEEE, 2011: 2731-2736. [46] ORTIZ-ARROYO D, HUSSAIN D M. An information theory approach to identify sets of key players[C]. Proceedings of the European Conference on Intelligence and Security Informatics. Berlin, Heidelberg: Springer, 2008: 15-26. [47] ARULSELVAN A, COMMANDER C W, ELEFTERIADOU L, et al. Detecting critical nodes in sparse graphs [J]. Comput Oper Res, 2009, 36(7): 2193-2200. [48] VENTRESCA M. Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem [J]. Comput Oper Res, 2012, 39(11): 2763-2775. [49] VENTRESCA M, ALEMAN D. A derandomized approximation algorithm for the critical node detection problem [J]. Comput Oper Res, 2014, 43(4): 261-270. [50] BALL M O, GOLDEN B L, V.Vohra R. Finding the most vital arcs in a network [J]. Oper Res Lett, 1989, 8(2): 73-76. [51] ISRAELI E, WOOD R K. Shortest-path network interdiction [J]. Networks, 2002, 40(2): 97-111. [52] NARDELLI E, PROIETTI G, WIDMAYER P. Finding the most vital node of a shortest path [J]. Theor Comput Sci, 2003, 296(1): 167-177. [53] BAYRAK H, BAILEY M D. Shortest path network interdiction with asymmetric information [J]. Networks, 2008, 52(3): 133-140. [54] SEFAIR J A, SMITH J C. Dynamic shortest-path interdiction [J]. Networks, 2016, 68(4): 315-330. [55] SONG Y, SHEN S. Risk-averse shortest path interdiction [J]. Informs J Comput, 2016, 28(3): 527-539. [56] SADEGHI S, SEIFI A, AZIZI E. Trilevel shortest path network interdiction with partial fortification [J]. Comput Ind Eng, 2017, 106: 400-411. [57] HOLZMANN T, SMITH J C. Shortest path interdiction problem with arc improvement recourse: a multiobjective approach [J]. Nav Res Logist, 2019, 66(3): 230-252. [58] PAY B S, MERRICK J R W, SONG Y. Stochastic network interdiction with incomplete preference [J]. Networks, 2019, 73(1): 3-22. [59] WOLLMER R. Removing arcs from a network [J]. Oper Res, 1964, 12(6): 934-940. [60] CORLEY H W, CHANG H. Finding the n most vital nodes in a flow network [J]. Manage Sci, 1974, 21(3): 362-364. [61] RATLIFF H D, SICILIA G T, LUBORE S H. Finding the n most vital links in flow networks [J]. Manage Sci, 1975, 21(5): 531-539. [62] ROCCO S C M, RAMIREZ-MARQUEZ J E. Deterministic network interdiction optimization via an evolutionary approach [J]. Reliab Eng Syst Saf, 2009, 94(2): 568-576. [63] ALTNER D S, ERGUN O, UHAN N A. The maximum flow network interdiction problem: valid inequalities, integrality gaps, and approximability [J]. Oper Res Lett, 2010, 38(1): 33-38. [64] AKGUN I, TANSEL B C, WOOD R K. The multi-terminal maximum-flow network-interdiction problem [J]. Eur J Oper Res, 2011, 211(2): 241-251. [65] SULLIVAN K M, SMITH J C. Exact algorithms for solving a euclidean maximum flow network interdiction problem [J]. Networks, 2014, 64(2): 109-124. [66] RAD M A, KAKHKI H T. Two extended formulations for cardinality maximum flow network interdiction problem [J]. Networks, 2017, 69(4): 367-377. [67] LEI X, SHEN S, SONG Y. Stochastic maximum flow interdiction problems under heterogeneous risk preferences [J]. Comput Oper Res, 2018, 90: 97-109. [68] ZENKLUSEN R. Matching interdiction [J]. Discret Appl Math, 2010, 158(15): 1676-1690. [69] FENG P, SCHILD A. Interdiction problems on planar graphs [J]. Discret Appl Math, 2013, 198: 215-231. [70] LIN K C, CHERN M S. The most vital edges in the minimum spanning tree problem [J]. Inf Process Lett, 1993, 45(1): 25-31. [71] BAZGAN C, TOUBALINE S, VANDERPOOTEN D. Efficient determination of the k most vital edges for the minimum spanning tree problem [J]. Comput Oper Res, 2012, 39(11): 2888-2898. [72] BAZGAN C, TOUBALINE S, VANDERPOOTEN D. Critical edges/nodes for the minimum spanning tree problem: complexity and approximation [J]. J Comb Optim, 2013, 26(1): 178-189. [73] DENG Y, WU J, XIAO Y, et al. Efficient disintegration strategies with cost constraint in complex networks: the crucial role of nodes near average degree [J]. Chaos, 2018, 28(6): 061101. [74] LOZANO M, GARCIA-MARTINEZ C, RODRIGUEZ F J, et al. Optimizing network attacks by artificial bee colony [J]. Inf Sci, 2017, 377: 30-50. [75] VEREMYEV A, PROKOPYEV O A, PASILIAO E L. An integer programming framework for critical elements detection in graphs [J]. J Comb Optim, 2014, 28(1): 233-273. [76] LEWIS J M, M M Y. The node-deletion problem for hereditary properties is NP-complete [J]. J Comput Syst Sci, 1980, 20(2): 219-230. [77] YANNAKAKIS M. Node-deletion problems on bipartite graphs [J]. SIAM J Comput, 1981, 10(2): 310-327. [78] DI SUMMA M, GROSSO A, LOCATELLI M. Branch and cut algorithms for detecting critical nodes in undirected graphs [J]. Comput Optim Appl, 2012, 53(3): 649-680. [79] VEREMYEV A, BOGINSKI V, PASILIAO E L. Exact identification of critical nodes in sparse networks via new compact formulations [J]. Optim Lett, 2014, 8(4): 1245-1259. [80] VENTRESCA M, ALEMAN D. A derandomized approximation algorithm for the critical node detection problem [J]. Comput Oper Res, 2014, 43: 261-270. [81] SHEN Y, NGUYEN N P, XUAN Y, et al. On the discovery of critical links and nodes for assessing network vulnerability [J]. IEEE/ACM Trans Netw, 2013, 21(3): 963-973. [82] SHEN S, SMITH J C, GOLI R. Exact interdiction models and algorithms for disconnecting networks via node deletions [J]. Discret Optim, 2012, 9(3): 172-188. [83] FAN N, PARDALOS P M. Robust optimization of graph partitioning and critical node detection in analyzing networks[C]. Proceedings of the International Conference on Combinatorial Optimization and Applications. Berlin, Heidelberg:Springer, 2010: 170-183. [84] 刘建国, 任卓明, 郭强, 等. 复杂网络中节点重要性排序的研究进展 [J]. 物理学报, 2013, 62(17): 9-18. LIU J G, REN Z M, GUO Q, et al. Node importance ranking of complex networks [J]. Acta Phys Sin, 2013, 62(17): 9-18. [85] 任晓龙, 吕琳媛. 网络重要节点排序方法综述 [J]. 科学通报, 2014, 59(13): 1175-1197. REN X L, LÜ L Y. Review of ranking nodes in complex networks [J]. Chin Sci Bull, 2014, 59(13): 1175-1197. [86] CARMI S, HAVLIN S, KIRKPATRICK S, et al. A model of Internet topology using k-shell decomposition [J]. Proc Natl Acad Sci USA, 2007, 104(27): 11150-11154. [87] WANDELT S, SUN X, FENG D, et al. A comparative analysis of approaches to network-dismantling [J]. Sci Rep, 2018, 8(1): 1-15. [88] FREEMAN L C. A set of measures of centrality based on betweenness [J]. Sociometry, 1977: 35-41. [89] GEISBERGER R, SANDERS P, SCHULTES D. Better approximation of betweenness centrality[C]. Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments. Philadelphia:SIAM, 2008: 90-100. [90] FREEMAN L C. Centrality in social networks conceptual clarification [J]. Soc Networks, 1978, 1(3): 215-239. [91] QIN J L, XU J, HU D, et al. Analyzing terrorist networks: a case study of the global salafi jihad network[C]. Proceedings of the International Conference on Intelligence and Security Informatics. Berlin, Heidelberg: Springer, 2005: 287-304. [92] ARINGHIERI R, GROSSO A, HOSTEINS P, et al. VNS solutions for the critical node problem [J]. Electron Notes Discret Math, 2015, 47: 37-44. [93] PULLAN W. Heuristic identification of critical nodes in sparse real-world graphs [J]. J Heuristics, 2015, 21(5): 577-598. [94] CHEN W, WANG Y, YANG S. Efficient influence maximization in social networks[C]. Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. New York: ACM, 2009: 199-208. [95] CHEN W, WANG C, WANG Y. Scalable influence maximization for prevalent viral marketing in large-scale social networks[C]. Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York: ACM, 2010: 1029-1038. [96] 胡庆成, 尹龑燊, 马鹏斐, 等. 一种新的网络传播中最有影响力的节点发现方法 [J]. 物理学报, 2013, 62(14): 9-19. HU Q C, YIN Y S, MA P F, et al. A new approach to identify influential spreaders in complex networks [J]. Acta Phys Sin, 2013, 62(14): 9-19. [97] HOLME P. Efficient local strategies for vaccination and network attack [J]. Europhys Lett, 2004, 68(6): 908-914. [98] MORONE F, MAKSE H A. Influence maximization in complex networks through optimal percolation [J]. Nature, 2015, 524(7563): 65-68. [99] MUGISHA S, ZHOU H. Identifying optimal targets of network attack by belief propagation [J]. Phys Rev E, 2016, 94(1): 012305. [100] ZHOU H. Spin glass approach to the feedback vertex set problem [J]. Eur Phys J B, 2013, 86(11): 1-9. [101] QIN S M, REN X L, LÜ L Y. Efficient network dismantling via node explosive percolation [J]. Commu Theor Phys, 2019, 71(6): 764. [102] SIMON M, LUPTAKOVA I D, HURAJ L, et al. Combined heuristic attack strategy on complex networks [J]. Math Probl Eng, 2017, 2017: 1-9. [103] CHEN Y, PAUL G, HAVLIN S, et al. Finding a better immunization strategy [J]. Phys Rev Lett, 2008, 101(5): 058701. [104] REN X, GLEINIG N, HELBING D, et al. Generalized network dismantling [J]. Proc Natl Acad Sci USA, 2019, 116(14): 6554-6559. [105] DENG Y, WU J, TAN Y J. Optimal attack strategy of complex networks based on tabu search [J]. Physica A, 2016, 442(1): 74-81. [106] YU Y, DENG Y, TAN S Y, et al. Efficient disintegration strategy in directed networks based on tabu search [J]. Physica A, 2018, 507(10): 435-442. [107] QI M, DENG Y, DENG H, et al. Optimal disintegration strategy in multiplex networks [J]. Chaos, 2018, 28(12): 121104. [108] DENG Y, WU J, QI M, et al. Optimal disintegration strategy in spatial networks with disintegration circle model [J]. Chaos, 2019, 29(6): 061102. [109] DENG Y, WU J, XIAO Y, et al. Optimal disintegration strategy with heterogeneous costs in complex networks [J]. IEEE Trans Syst Man Cybern Syst, 2020, 50(8): 2905-2913. [110] ZHOU Y, HAO J, GLOVER F. Memetic search for identifying critical nodes in sparse graphs [J]. IEEE Trans Cybern, 2019, 49(10): 3699-3712. [111] LOZANO M, GARCIAMARTINEZ C, RODRIGUEZ F J, et al. Optimizing network attacks by artificial bee colony [J]. Inf Sci, 2017, 377: 30-50. [112] PUREVSUREN D, CUI G, WIN N N H, et al. Heuristic algorithm for identifying critical nodes in graphs [J]. Adv Comput Sci Int J, 2016, 5(3): 1-4. [113] FAN C, ZENG L, SUN Y, et al. Finding key players in complex networks through deep reinforcement learning [J]. Nature Mach Intell, 2020, 2(6): 317-324. [114] WANG Z G, DENG Y, WANG Z, et al. Disintegrating spatial networks based on region centrality [J]. Chaos, 2021, 31(6): 061101. [115] QI M Z, BAI Y, LI X H, et al. Optimal disintegration strategy in multiplex networks under layer node-based attack [J]. Appl Sci-Basel, 2019, 9(19): 3968. [116] 郭强, 殷冉冉, 刘建国. 基于TOPSIS的时序网络节点重要性研究 [J]. 电子科技大学学报, 2019, 48(2): 296-300. GOU Q, YIN R R, LIU J G. Node importance identification for temporal networks via the TOPSIS method [J]. J Univ Electron Sci Technol Chin, 2019, 48(2): 296-300. [117] 梁耀洲, 郭强, 殷冉冉, 等. 基于排名聚合的时序网络节点重要性研究 [J]. 电子科技大学学报, 2020, 49(4): 519-523. LIANG Y Z, GUO Q, YIN R R, et al. Node importance identification for temporal network based on ranking aggregation [J]. J Univ Electron Sci Technol Chin, 2020, 49(4): 519-523. [118] 杨剑楠, 刘建国, 郭强. 基于层间相似性的时序网络节点重要性研究 [J]. 物理学报, 2018, 67(4): 279-286. YANG J N, LIU J G, GUO Q. Node importance idenfication for temporal network based on inter-layer similarity [J]. Acta Phys Sin, 2018, 67(4): 279-286. [119] PENG R, WU D, SUN M, et al. An attack-defense game on interdependent networks [J]. J Oper Res Soc, 2020, 72(10): 1-11. [120] LI Y P, TAN S Y, DENG Y, et al. Attacker-defender game from a network science perspective [J]. Chaos, 2018, 28(5): 051102. [121] LI Y, DENG Y, XIAO Y, et al. Attack and defense strategies in complex networks based on game theory [J]. J Syst Sci Complex, 2019, 32(6): 1630-1640.
