網絡瓦解的最新進展：全面綜述和對未來工作的建議清單

導語

在數字化時代，網絡無處不在，從有益的互聯網、電網，到有害的恐怖組織、病毒傳播鏈。如何精準瓦解這些有害網絡？網絡瓦解（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.