网络瓦解的最新进展：全面综述和对未来工作的建议清单

导语

在数字化时代，网络无处不在，从有益的互联网、电网，到有害的恐怖组织、病毒传播链。如何精准瓦解这些有害网络？网络瓦解（Network Dismantling）研究正通过机器学习、复杂网络理论给出答案。本文基于Wandelt等（2025）的综述《Recent advances in network dismantling: A comprehensive review and list of recommendations for future work》脉络，结合相关研究综述，深度解析该领域的最新进展、核心算法、网络类型演变及未来挑战。

关键词：复杂网络，瓦解策略，瓦解目标，韧性，综述

张鹏丨译者

论文题目：Recent advances in network dismantling: A comprehensive review and list of recommendations for future work 论文链接：https://www.sciencedirect.com/science/article/abs/pii/S0960077925006861 论文来源：Chaos, Solitons & Fractals

图1 基于论文[1]的网络拆除研究的综述大纲

1. 网络瓦解的重要性与演进历程

网络瓦解旨在通过移除关键节点或边，破坏网络结构、削弱其功能，从而应对安全、卫生、金融等领域的威胁。自20世纪60年代运筹学中的数学规划起步，随着研究网络规模的增大逐渐演进到基于中心性指标的各类启发式方法，并正被机器学习所变革[1]。随着网络规模扩大和复杂性增加，瓦解策略需更加智能、高效。复杂网络拆解不仅是学术热点，更在反恐、公共卫生、网络安全中有直接应用[2]。例如，在疫情防控中，通过识别并隔离超级传播者节点，可有效阻断病毒传播链；在反恐行动中，通过瓦解恐怖组织网络的关键连接，能破坏其运作能力。

2. 网络瓦解策略与效应

综述论文系统分析了网络瓦解的三大策略，每种策略各有其独特的方法论与应用场景。

图2三种网络拆解策略的示意图[1]

2.1 节点攻击：精准打击网络核心

节点攻击研究大多依赖数学规划（如整数线性规划）、中心性指标以及各类启发式方法[3]：

• 数学规划：早期研究主要依赖数学规划方法，如整数线性规划[4]和动态规划[5]。这些方法能获得最优解，但计算复杂度高，难以应用于大规模网络。

• 中心性指标：启发式方法如基于度、介数、接近度等中心性指标的节点移除策略[6]因其简单高效而被广泛使用。现有研究仍在探索各类启发式中心性指标对网络鲁棒性的影响，如基于节点传播能力的方法CI[7]，基于权衡节点局部信息与中尺度信息的方法DomiRank[8]等。

• 贪心算法：逐步移除当前最重要的节点，但可能陷入局部最优[9]。

• 进化计算：如遗传算法、禁忌搜索，处理复杂约束但计算成本高[10]。

• 渗流理论与消息传递理论：渗流理论为网络拆解提供了核心数学框架，通过将节点或链接移除建模为渗流过程，揭示了网络在攻击下的相变行为；通过生成函数和消息传递方法 可精确计算巨组件大小和临界点，而网络拓扑特征（如度异质性和相关性）显著影响拆解效率，导致连续或不连续相变；这一理论不仅预测了系统崩溃的阈值，还指导了高效拆解算法的设计，例如CI、BPD[11]、Min-Sum[12]等高效算法，这些算法在复杂网络上取得了不错的网络拆解效果，为理解网络鲁棒性和韧性奠定了理论基础[7,12]。

这些方法在中小规模网络上有效，但难以应对大规模或动态网络。而机器学习通过数据驱动方式，实现了更精准、自适应的拆解，成为近年来的研究热点。算法从监督学习到强化学习，涵盖了多种范式：

• FINDER算法[13]：采用深度强化学习，从小规模合成网络（如BA网络）训练智能体，学习节点重要性模式，然后迁移到真实网络（如社交网络、基础设施网络）。在巴西腐败网络（309节点）上，仅移除20个节点即可瓦解网络，优于传统方法[11]。

• GDM算法[14]：使用监督学习，在合成网络上通过暴力搜索生成训练数据，学习节点移除策略。适用于大规模网络，且可通过再插入阶段优化解[12]。

• 基于解环的机器学习拆解策略：结合核心分解与机器学习，先使用各类机器学习策略来解环网络（2-core），再用树破坏-重插策略进行细化拆解，其代表算法如CoreDQN[13],CoreGDM[15]。

• 基于嵌入辅助的网络拆解算法[16]：利用几何嵌入技术将网络节点映射到低维空间（如双曲或欧几里得空间），其中节点间的几何距离捕获拓扑相似性，从而指导高效拆解。拆解阶段采用迭代二分法——递归地将最大连通组件几何分割（如用直线切割双曲盘或k-means聚类），识别并移除边界节点或边（解决最小顶点覆盖问题）以断开组件，直至网络完全瓦解，最后通过贪婪后处理优化移除集（移除冗余元素）。

最新研究进展：北京化工大学谷伟伟副教授团队提出了“MultiDismantler”多层网络瓦解算法[17]，融合图神经网络与深度强化学习，能有效编码中层内与层间节点的耦合关系，自动识别对多层网络结构影响最大的关键节点，拆除效率提升超过8%。

2.2 边攻击：切断网络连接脉络

边攻击专注于移除网络中的连接而非节点，主要包括三种方法[1]：

• 基于度的边攻击（DE）：攻击高度数节点间的连接

• 基于介数的边攻击（BE）：移除最多最短路径经过的边

• 基于权重的边攻击（WE）：针对加权网络中高权重连接

最新研究突破：FIGHTER框架通过线图转换技术，将原始图中的边攻击问题转化为线图中的节点攻击问题，结合图神经网络与深度强化学习，在合成与真实网络中平均性能提升19.28%-20.45%。这一突破解决了边攻击序列识别的NP难问题，为网络防御和流行病控制提供了更高效的解决方案[18]。

2.3 级联故障：理解网络崩溃的连锁反应

当前关于级联失效（Cascading Failures）的研究方法呈现出多维度、多模型交叉融合的特点。级联失效区别于简单的节点或边攻击，其核心在于初始局部故障会通过节点与边之间的依赖关系引发连锁反应，最终导致全局性系统崩溃。主要研究方法包括三大类：一是基于相互依赖关系的模型，通常采用多层网络或“网络中的网络”框架来描述系统间故障传播的动力学过程；二是阈值模型，源于社会行为学，节点状态改变依赖于其邻居节点中故障数量的比例是否超过特定阈值，适用于社交网络和谣言传播等场景；三是过载模型，节点或边负载超过容量上限时触发负载重分配，广泛应用于电力系统、交通网络等基础设施的级联失效分析[2]。具体策略上，除了传统的随机攻击（RN）和基于中心性（如度中心性DN、介数中心性BN、接近中心性CloN等）的攻击外，还发展了基于特征向量的边攻击（EE）、LocalRank节点攻击（LRN）以及基于强化学习的级联失效攻击策略（ToupleGDD）[19]等更精细的方法。这些方法不仅关注静态拓扑特征，也逐步引入了动态更新、成本约束以及时空维度的影响，致力于在理论可解性与实际应用复杂度之间寻求平衡，从而提高对关键基础设施和复杂系统稳健性的评估与设计能力。

3. 网络瓦解对象：从理论模型到现实复杂结构

早期研究多集中于简单网络模型（如ER随机网络、BA无标度网络），但这些模型难以捕捉现实网络的复杂性。近年来，研究拓展到多样化的网络类型，以更贴近实际应用[1]。

3.1 合成网络模型

• 随机网络（ER网络）：节点随机连接，对针对性攻击鲁棒，拆解策略效果有限[20]。

• 无标度网络（BA网络）：度分布服从幂律，对随机故障鲁棒但对针对性攻击（如移除高度数节点）脆弱。Albert等人的开创性工作展示了这一点[21]。

• 小世界网络（WS网络）：高聚类系数和短平均路径长度，拆解需考虑局部社区结构[22]。

3.2 复杂网络结构

随着应用需求增长，研究覆盖了更复杂的网络类型：

• 相互依赖网络（Interdependent Networks）：如电网与通信网耦合，拆解需考虑层间依赖关系，否则易引发级联失效。Buldyrev等人指出，这类网络的拆解常导致不连续相变[24]，难以预警。Wandelt等人指出，优化互依赖网络的拆解策略需集成多层信息[1]。

• 多层网络（Multiplex Networks）：不同层代表不同关系类型（如社交层、信息层），拆解策略需跨层优化。例如，在社交-通信多层网络中，移除关键层间节点可有效破坏整体功能[25]。

• 高阶网络（Higher-order Networks）：超越成对交互，包含群体动力学（如Simplicial Complexes），拆解需处理高阶结构。Battiston等（2021）的工作展示了高阶交互对拆解策略的影响[26]。

• 动态网络（Dynamic Networks）：结构随时间变化，如社交网络中的关系演化，要求实时自适应拆解[27,28]。

• 空间嵌入网络（Spatially Embedded Networks）：节点具地理坐标，如交通网、物流网，拆解需考虑空间约束（如距离成本）。Dong等（2020）研究了空间网络中的最优拆解路径[29]。

3.3 现实网络结构

如表中各类研究所示，网络瓦解策略（如节点攻击中的度、介数、特征向量中心性，或级联故障中的过载模型）需根据网络类型的特点定制。例如，在基础设施网络中（如电力和供水），级联故障模型尤为重要；而在信息网络（如社交和通信）中，节点中心性攻击更直接有效[1]。未来工作需进一步结合真实网络的多层性、动态性和成本约束，以提升拆解策略的实际应用价值。

表1 鲁棒性研究中常用的现实网络类型概述[1]

4. 未来方向：挑战与机遇

本文将针对网络瓦解的未来研究方向，系统分析各方向的现有研究基础、面临的核心挑战及潜在发展机遇。基于综述文献的内容，主要聚焦以下六个关键方向[1]：

4.1 节点/边成本的广泛纳入

• 现有研究情况：当前大多数网络拆解研究假设攻击成本均匀分布，仅有少数研究开始探索成本异质性。Ren等人在2019年提出的广义网络拆解框架是这一方向的先驱工作，他们首次系统性地考虑了节点移除成本的差异性[31]。近年来，Ding等研究者开始研究成本约束下的级联攻击策略，进一步推动了这一方向的发展[32]。

• 挑战：如何准确评估不同节点和边的攻击成本，并将其纳入模型中，以制定更有效的攻击策略。而且需要同时优化拆解效果和成本效率，增加问题复杂度。

• 机遇：发展综合模型可以提升对网络攻击策略的理解，优化脆弱节点的识别和攻击选择。可借鉴多目标进化算法解决成本-效果权衡问题，结合机器学习方法从有限数据中学习成本分布模式。

• 现有研究情况：现有研究大多集中在小规模网络，缺乏对数百万或数十亿节点的大规模网络进行算法开发。

• 挑战：在大规模网络中，传统方法面临高计算复杂度和内存消耗的问题。而且随着网络规模增大，如何在保证算法效率的同时维持拆解效果的竞争性，也是一个非常值得研究的问题。

• 机遇：开发新的启发式算法和并行计算技术可提高大规模网络分析的效率，推动算法在实际应用中的可行性。

• 现有研究情况：该领域目前缺乏标准化的基准测试网络和评估框架。大多数研究使用BA、WS等标准随机网络或有限的真实网络进行评估，缺乏系统性的比较基准。Cai等人在多部网络方面的研究为特定网络类型提供了分析框架[33-35]，但覆盖面有限。

• 挑战：由于真实网络具有高度多样性，难以用有限基准代表，如何构建理想化的基准模型，并确保其准确反映真实网络的行为特征。且如何建立统一的评估指标体系，促进系统化的比较基准。

• 机遇：构建涵盖不同领域、不同特征的网络基准数据集。且通过人工基准网络，可以更有效地评估网络的韧性，比较不同的攻击策略，从而推动研究的进展。

• 现有研究情况：时序维度研究目前处于起步阶段。Xie等人研究了具有时变延迟的复杂动态网络鲁棒性[28]，Engsig等人探索了使用空闲网络评估复杂网络鲁棒性的方法[27]。这些研究为理解时间维度的影响提供了初步见解，但系统性研究仍然缺乏。

• 挑战：时变网络的建模和分析比静态网络复杂得多，且需要大量时间序列数据支持动态分析。如何捕捉网络在不同时间点的动态特征，以制定时机优化的攻击策略，是一个值得思考的问题。

• 机遇：将网络拆解视为动态控制问题，设计预测性攻击序列。这不仅有助于理解网络的动态行为，还能为防御机制的开发提供理论支持。

• 现有研究情况：Wandelt等人证明了社区检测技术如何促进真实世界网络的拆解[36]。Musciatto等人研究了基于社区结构的拆解策略 [37]。Wang和Liu探索了相互依赖网络中的社区鲁棒性及其增强方法[38]。这些研究显示了模块化结构分析的重要性。

• 挑战：社区检测算法本身的准确性和稳定性影响拆解效果，且真实网络往往具有多层次、嵌套的模块结构。如何有效地设计考虑模块性和异质性的算法，以适应复杂网络的特性。

• 机遇：开发多尺度网络分析方法识别不同层次的关键结构，将模块性与异质性纳入考虑，可以显著提升拆解算法的效果，特别是在大规模网络中。

• 现有研究情况：这一方向的研究尚处于概念阶段，实证研究和理论框架都相对缺乏。大多数现有工作将攻击和恢复视为独立过程，忽略了二者之间的动态相互作用。在攻防博弈框架[39-41]下, 原来看起来非常重要的关键节点(边)因为考虑防御策略很可能不再被移除。

• 挑战：需要同时建模攻击者、防御者和网络动力学，建模十分复杂。且现实场景中各方往往具有不完全信息。如何构建动态博弈模型，以描述攻击者与防御者之间的博弈关系。在不同的网络结构中什么是攻击者和防御者的均衡策略？这是一个十分有趣而又非常复杂的问题.

• 机遇：将博弈论框架引入网络拆解研究，利用强化学习解决动态决策问题以达到共同优化攻击和恢复策略的目的，提供新的韧性视角。

参考文献

1. Wandelt, S., et al. (2025). Recent advances in network dismantling. Chaos, Solitons and Fractals, 199, 116673.

2. Artime, O., et al. (2024). Robustness and resilience of complex networks. Nature Reviews Physics, 6, 114–131.

3. 吴俊, 邓烨, 王志刚, 谭索怡, 李亚鹏. (2022). 复杂网络瓦解问题研究进展与展望. 复杂系统与复杂性科学.

4. Arulselvan, A., et al. (2009). Detecting critical nodes in sparse graphs. Computers & Operations Research, 36(7), 2193-2200.

5. 5.Shen, S., et al. (2012). Exact interdiction models and algorithms for disconnecting networks via node deletions. Discrete Optimization, 9(3), 172-188.

6. Albert, R., Jeong, H., & Barabási, A.-L. (2000). Error and attack tolerance of complex networks. Nature, 406(6794), 378-382.

7. Morone F, Makse H A. Influence maximization in complex networks through optimal percolation [J]. Nature, 2015, 524(7563): 65-68.

8. M. Engsig, A. Tejedor, Y. Moreno, E. Foufoula-Georgiou, and C. Kasmi, DomiRank Centrality reveals structural fragility of complex networks via node dominance, Nat Commun, vol. 15, no. 1, p. 56, Jan. 2024.

9. Holme, P., et al. (2002). Attack vulnerability of complex networks. Physical Review E, 65(5), 056109.

10. Ventresca, M. (2012). Global search algorithms using a combinatorial unranking-based problem representation for the critical node detection problem. Computers & Operations Research, 39(11), 2763-2775.

11. Mugisha, S. & Zhou, H.-J. Identifying optimal targets of network attack by belief propagation. Phys. Rev. E 94, 012305 (2016).

12. Braunstein, A., Dall’Asta, L., Semerjian, G. & Zdeborová, L. Network Dismantling. Proc. Natl. Acad. Sci. U.S.A. 113, 12368–12373 (2016).

13. Fan, C., et al. (2020). Finding key players in complex networks through deep reinforcement learning. Nature Machine Intelligence, 2(6), 317-324.

14. Grassia, M., et al. (2021). Machine learning dismantling and early-warning signals of disintegration in complex systems. Nature Communications, 12, 5190.

15. Grassia, M., & Mangioni, G. (2023, March). Coregdm: Geometric deep learning network decycling and dismantling. In International Workshop on Complex Networks (pp. 86-94). Cham: Springer Nature Switzerland.

16. Osat, S., Papadopoulos, F., Teixeira, A. S. & Radicchi, F. Embedding-aided network dismantling. Phys. Rev. Res. 5, 013076 (2023)

17. Gu, W., Yang, C., Li, L., Hou, J., & Radicchi, F. (2025). Deep-learning-aided dismantling of interdependent networks. Nature Machine Intelligence, 1-12.

18. Guo, F. et al. Finding key edges in complex network through line graph transformation and deep reinforcement learning. Expert Systems with Applications 289, 128121 (2025).

19. Chen, T., Yan, S., Guo, J. & Wu, W. ToupleGDD: A Fine-Designed Solution of Influence Maximization by Deep Reinforcement Learning. IEEE Transactions on Computational Social Systems 11, 2210–2221 (2024).

20. Erdős, P., & Rényi, A. (1960). On the evolution of random graphs. Publications of the Mathematical Institute of the Hungarian Academy of Sciences, 5, 17-61.

21. Barabási, A.-L., & Albert, R. (1999). Emergence of scaling in random networks. Science, 286(5439), 509-512.

22. Watts, D. J., & Strogatz, S. H. (1998). Collective dynamics of 'small-world' networks. Nature, 393(6684), 440-442.

23. Buldyrev, S. V., et al. (2010). Catastrophic cascade of failures in interdependent networks. Nature, 464(7291), 1025-1028.

24. Buldyrev, S. V., et al. (2010). Catastrophic cascade of failures in interdependent networks. Nature, 464(7291), 1025-1028.

25. De Domenico, M., et al. (2013). Mathematical formulation of multilayer networks. Physical Review X, 3(4), 04102.

26. Battiston, F., et al. (2021). The physics of higher-order interactions in complex systems. Nature Physics, 17(10), 1093-1098.

27. Engsig M, Tejedor A, Moreno Y. Robustness assessment of complex networks using the idle network. Phys Rev Res 2022;4:L042050.

28. Xie T, Zhang Q, Xiong X. Robustness analysis of exponential synchronization in complex dynamic networks with time-varying delays and random disturbances.Symmetry 2023;15:1510.

29. Dong, S., et al. (2020). Measuring the topological robustness of transportation networks to disaster-induced failures: A percolation approach. Journal of Infrastructure Systems, 26(2), 04020009.

30. Zitnik, M., et al. (2019). Evolution of resilience in protein interactomes across the tree of life. Proceedings of the National Academy of Sciences, 116(10), 4426-4433.

31. Ren, X.-L., Gleinig, N., Helbing, D. & Antulov-Fantulin, N. Generalized Network Dismantling. Proc. Natl. Acad. Sci. U.S.A. 116, 6554–6559 (2019).

32. Ding L, Xie L, Wen J, Tan M. Robustness of complex networks under cost-constrained cascaded attack strategies. Modern Phys Lett B 2024;38:2450148.

33. Cai Q, Pratama M, Alam S, Ma C, Liu J. Breakup of directed multipartite networks. IEEE Trans Netw Sci Eng 2019;7:947–60.

34. Cai Q, Alam S, Pratama M, Wang Z. Percolation theories for multipartite networked systems under random failures. Complexity 2020;2020:3974503.

35. Cai Q, Alam S, Pratama M, Liu J. Robustness evaluation of multipartite complex networks based on percolation theory. IEEE Trans Syst Man Cybern: Syst 2020;51:6244–57.

36. Wandelt S, Shi X, Sun X, Zanin M. Community detection boosts network dismantling on real-world networks. IEEE Access 2020;8:111954–65.

37. Musciotto F, Miccichè S. Exploring the landscape of dismantling strategies based on the community structure of networks. Sci Rep 2023;13:14448.

38. Wang S, Liu J. Community robustness and its enhancement in interdependent networks. Appl Soft Comput 2019;77:665–77.

39. Peng R, Wu D, Sun M, et al. An attack-defense game on interdependent networks [J]. J Oper Res Soc, 2020: 1-11.

40. Li Y-P, Tan S-Y, Deng Y, et al. Attacker-defender game from a network science perspective [J]. Chaos, 2018, 28(5): 051102.

41. 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.

参考文献可上下滑动查看

复杂网络瓦解读书会

从复杂网络的构建到智能优化的演化，理解网络的鲁棒性与瓦解机制始终是一个深刻的挑战。更值得深思的是，网络的结构和算法设计如何决定了网络在遭遇局部攻击时的脆弱性，及其整体瓦解的速度与范围。动态演化过程中的节点和边的变化，也会影响系统如何在瓦解中保持部分功能，或如何适应新的结构。因此，网络瓦解研究聚焦于一个核心问题：在不同类型的网络结构（如高阶网络、空间网络、时序网络）中，局部的破坏如何引发整体功能的丧失？在面对网络的异质性和约束条件下，不同的优化算法如何有效识别并摧毁关键节点与连接，从而最大化网络的瓦解效应，进而影响系统的整体稳定性与韧性？

集智俱乐部联合北京师范大学教授吴俊、国防科技大学副研究员谭索怡、北京化工大学副教授谷伟伟、中国科学技术大学博士后范天龙、国防科技大学在读博士卿枫共同发起，跨越网络结构、算法模型与应用场景的视角，探索复杂网络瓦解的前沿进展。重点探讨不同算法与优化框架如何帮助我们认识网络的脆弱性，并在现实约束下推动网络系统的智能演化与应用发展。

详情请见：

1.

2.

3.

4.

5.

6.