摘要

一般情況下, 我們面對的網(wǎng)絡(luò)都是“有益的”, 但是有時候我們面對的網(wǎng)絡(luò)也可能是“有害的”, 例如恐怖組織網(wǎng)絡(luò)、疾病傳播網(wǎng)絡(luò)等。如何通過阻斷、干擾、免疫、封鎖、隔離等手段有效瓦解這些有害網(wǎng)絡(luò)成為一個亟待解決的挑戰(zhàn)性問題, 其核心是找到網(wǎng)絡(luò)系統(tǒng)的“關(guān)鍵節(jié)點(邊)”。吳俊團(tuán)隊發(fā)表綜述首先給出了網(wǎng)絡(luò)瓦解問題的數(shù)學(xué)描述, 在此基礎(chǔ)上從基于數(shù)學(xué)規(guī)劃、基于中心性指標(biāo)、基于啟發(fā)式算法、基于進(jìn)化計算、基于機(jī)器學(xué)習(xí)等幾個方面系統(tǒng)總結(jié)了運(yùn)籌學(xué)、網(wǎng)絡(luò)科學(xué)、計算機(jī)科學(xué)等領(lǐng)域關(guān)于復(fù)雜網(wǎng)絡(luò)瓦解問題的研究進(jìn)展, 最后分別從目標(biāo)網(wǎng)絡(luò)維度、瓦解模型維度、瓦解算法維度對復(fù)雜網(wǎng)絡(luò)瓦解問題未來發(fā)展進(jìn)行了展望。

集智俱樂部聯(lián)合北京師范大學(xué)教授吳俊、國防科技大學(xué)副研究員譚索怡、北京化工大學(xué)副教授谷偉偉、中國科學(xué)技術(shù)大學(xué)博士后范天龍、國防科技大學(xué)在讀博士卿楓共同發(fā)起「復(fù)雜網(wǎng)絡(luò)瓦解讀書會」，跨越網(wǎng)絡(luò)結(jié)構(gòu)、算法模型與應(yīng)用場景的視角，探索復(fù)雜網(wǎng)絡(luò)瓦解的前沿進(jìn)展。重點探討不同算法與優(yōu)化框架如何幫助我們認(rèn)識網(wǎng)絡(luò)的脆弱性，并在現(xiàn)實約束下推動網(wǎng)絡(luò)系統(tǒng)的智能演化與應(yīng)用發(fā)展。掃描下方海報二維碼即可加入！

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)、瓦解、關(guān)鍵節(jié)點、免疫、反恐、體系對抗

吳俊等丨作者

張俊麗｜編譯

目錄

1. 引言

2. 網(wǎng)絡(luò)瓦解問題的數(shù)學(xué)描述

3. 基于數(shù)學(xué)規(guī)劃的網(wǎng)絡(luò)瓦解方法

4. 基于中心性指標(biāo)的復(fù)雜網(wǎng)絡(luò)瓦解方法

5. 基于啟發(fā)式算法的復(fù)雜網(wǎng)絡(luò)瓦解方法

6. 基于進(jìn)化算法的復(fù)雜網(wǎng)絡(luò)瓦解方法

7. 基于機(jī)器學(xué)習(xí)的復(fù)雜網(wǎng)絡(luò)瓦解方法

8. 結(jié)論與展望

1. 引言

伴隨著現(xiàn)代信息技術(shù)的不斷發(fā)展, 人類社會已經(jīng)進(jìn)入網(wǎng)絡(luò)化時代。萬維網(wǎng)、社交網(wǎng)、物聯(lián)網(wǎng)、電力網(wǎng)、貿(mào)易網(wǎng)……可以說, 我們生活在一個被網(wǎng)絡(luò)包圍的世界。這些網(wǎng)絡(luò)規(guī)模龐大、結(jié)構(gòu)多變, 既不是規(guī)則網(wǎng)絡(luò), 也不是隨機(jī)網(wǎng)絡(luò)，而且具有復(fù)雜的動力學(xué)行為, 因此被稱之為“復(fù)雜網(wǎng)絡(luò)”。自從現(xiàn)實世界中網(wǎng)絡(luò)的小世界效應(yīng)[1]和無標(biāo)度特性[2]被揭示以來, 復(fù)雜網(wǎng)絡(luò)研究在過去二十年里迅猛發(fā)展, 受到數(shù)學(xué)、物理、計算機(jī)、管理學(xué)、社會學(xué)、生物學(xué)等不同領(lǐng)域?qū)W者的共同關(guān)注，一門研究復(fù)雜網(wǎng)絡(luò)共性規(guī)律和普適方法的交叉學(xué)科——網(wǎng)絡(luò)科學(xué)迅速崛起，成為研究復(fù)雜系統(tǒng)的新范式[3-7]。

一般情況下, 我們面對的網(wǎng)絡(luò)都是“有益的”。例如, 交通網(wǎng)絡(luò)、電力網(wǎng)絡(luò)、物流網(wǎng)絡(luò)等。對于這些有益的網(wǎng)絡(luò), 我們希望通過規(guī)劃設(shè)計、優(yōu)化控制、防御保護(hù)等各種手段來保障它們持續(xù)、穩(wěn)定、有效地維持功能。目前, 針對這些有益網(wǎng)絡(luò)的設(shè)計、優(yōu)化、控制與管理研究已經(jīng)取得了豐富成果, 一直是管理科學(xué)、信息科學(xué)等多個學(xué)科領(lǐng)域共同關(guān)注的焦點[8-15]。但是, 很多時候我們面對的網(wǎng)絡(luò)也可能是“有害的”。最典型的例子就是恐怖組織網(wǎng)絡(luò)[16-18]。上個世紀(jì)60年代以來, 國際恐怖主義活動日益猖獗, 恐怖組織已經(jīng)從傳統(tǒng)的等級層次結(jié)構(gòu)演化為網(wǎng)絡(luò)化結(jié)構(gòu), 如何有效瓦解恐怖組織網(wǎng)絡(luò)成為世界各國面臨的共同難題。另外一個典型例子就是疾病傳播網(wǎng)絡(luò)[19, 20]。近年來, COVID-2019、SARS、埃博拉、瘋牛病、禽流感等傳染病接踵而至, 給人類社會造成巨大損失。如何有效阻斷疾病在人群或動物之間擴(kuò)散是全球公共衛(wèi)生領(lǐng)域面臨的艱巨任務(wù)。其中, 免疫是一種關(guān)鍵手段, 而免疫本質(zhì)上就是通過注射疫苗從疾病傳播網(wǎng)絡(luò)中“移除”部分節(jié)點(人或動物)從而瓦解整個網(wǎng)絡(luò), 達(dá)到控制疾病擴(kuò)散的目的。此外, 犯罪分子網(wǎng)絡(luò)[21, 22]、毒品走私網(wǎng)絡(luò)[23]、核材料走私網(wǎng)絡(luò)[24]、癌細(xì)胞擴(kuò)散網(wǎng)絡(luò)[25]、謠言傳播網(wǎng)絡(luò)[26]、金融危機(jī)網(wǎng)絡(luò)[27]以及軍事對抗中的敵方網(wǎng)絡(luò)[28]等都屬于這類有害網(wǎng)絡(luò)。如何通過阻斷、干擾、免疫、封鎖、隔離等手段有效瓦解這些有害網(wǎng)絡(luò)成為一個亟待解決的問題。

伴隨著網(wǎng)絡(luò)科學(xué)的興起,復(fù)雜網(wǎng)絡(luò)瓦解問題也受到越來越多的關(guān)注,并取得了可喜進(jìn)展。本文首先給出網(wǎng)絡(luò)瓦解問題的數(shù)學(xué)描述, 在此基礎(chǔ)上從基于數(shù)學(xué)規(guī)劃、基于中心性指標(biāo)、基于啟發(fā)式算法、基于進(jìn)化計算、基于機(jī)器學(xué)習(xí)等幾個方面系統(tǒng)總結(jié)目前復(fù)雜網(wǎng)絡(luò)瓦解問題的研究進(jìn)展, 并對未來發(fā)展進(jìn)行展望。

2. 網(wǎng)絡(luò)瓦解問題的數(shù)學(xué)描述

所謂網(wǎng)絡(luò)瓦解 (network disintegration[29], network interdiction[30], network inhibition[31], network dismantling[32], network destabilization[33]), 就是通過移除部分節(jié)點或邊來破壞網(wǎng)絡(luò)的結(jié)構(gòu)、削弱網(wǎng)絡(luò)的功能、干擾網(wǎng)絡(luò)的行為。其問題的核心是如何在特定約束條件和各種瓦解目標(biāo)下確定要移除的節(jié)點(邊)集合, 也就是找到網(wǎng)絡(luò)系統(tǒng)的“要害”, 其數(shù)學(xué)本質(zhì)是一個組合優(yōu)化問題。

令 G = (V, E) 表示目標(biāo)網(wǎng)絡(luò), 其中 V={v1,v2,...,vN} 表示節(jié)點集合, 表示邊的集合, N = |V|表示節(jié)點數(shù)量, W = |E|表示邊數(shù)量。網(wǎng)絡(luò)瓦解包括節(jié)點移除和邊移除兩種方式。令表示要移除的節(jié)點集合, 表示要移除的邊集合, 表示瓦解之后的網(wǎng)絡(luò)。通常, 我們假設(shè)節(jié)點移除后與之相關(guān)聯(lián)的所有邊都會隨之移除。令 X={x1,x2,...,xN}表示節(jié)點瓦解策略, 其中若 則xi = 1則, 否則xi = 0; 令Y = {y1, y2, …, yW}表示邊瓦解策略, 其中若則yi = 1, 否則yi = 0。令I(lǐng) = (X, Y) ∈Ω表示一個網(wǎng)絡(luò)瓦解方案, 其中Ω表示約束條件, 例如移除節(jié)點的數(shù)量不超過K, 即。令Φ(I)表示網(wǎng)絡(luò)瓦解的目標(biāo)函數(shù), 則網(wǎng)絡(luò)瓦解問題可以描述為如下的一般數(shù)學(xué)模型：

目標(biāo)函數(shù)對于網(wǎng)絡(luò)瓦解問題至關(guān)重要, 瓦解目標(biāo)不同, 最優(yōu)的網(wǎng)絡(luò)瓦解方案就不一樣[34, 35]。此外, 目標(biāo)函數(shù)的選擇還直接決定了網(wǎng)絡(luò)瓦解問題的計算復(fù)雜性。網(wǎng)絡(luò)被瓦解后通常會形成若干子圖，若子圖上任意兩個節(jié)點間均存在一條鏈路, 則該子圖可以稱為連通片。令L表示網(wǎng)絡(luò)瓦解后連通片的數(shù)量，nl (1 ≤ l ≤ L) 表示網(wǎng)絡(luò)瓦解后每個連通片中包含節(jié)點的數(shù)量，dij表示節(jié)點vi和vj之間的最短路徑長度。目前, 常用的網(wǎng)絡(luò)瓦解目標(biāo)函數(shù)Φ(I)主要包括：網(wǎng)絡(luò)瓦解后連通片的數(shù)量[36-38]；網(wǎng)絡(luò)瓦解后最大連通片的規(guī)模[39-43]，在加權(quán)網(wǎng)絡(luò)中, 最大連通片也可以被定義為節(jié)點權(quán)重之和最大的連通片, 而不是包含節(jié)點數(shù)目最多的連通片[44]；網(wǎng)絡(luò)瓦解后的赫芬達(dá)爾-赫希曼指數(shù) (Herfindahl-hirschman index) [36]；網(wǎng)絡(luò)瓦解后的信息熵[36, 45, 46]；網(wǎng)絡(luò)瓦解后連通節(jié)點對的數(shù)量[36, 47-49]；網(wǎng)絡(luò)瓦解后源節(jié)點和匯節(jié)點之間的最短路徑長度[50-58]；網(wǎng)絡(luò)瓦解后節(jié)點對之間的平均最短路徑長度[40]；網(wǎng)絡(luò)瓦解后節(jié)點對之間的效率[40]；網(wǎng)絡(luò)瓦解后的源節(jié)點和匯節(jié)點之間的最大流[31, 59-67]；網(wǎng)絡(luò)瓦解后的最大匹配[68, 69]；網(wǎng)絡(luò)瓦解后的最小支撐樹[70-72]；網(wǎng)絡(luò)瓦解后的自然連通度[73]；網(wǎng)絡(luò)瓦解后的最大介數(shù)[74]等。

無論節(jié)點瓦解方式還是邊瓦解方式, 無論采用哪種瓦解目標(biāo)函數(shù), 除了少數(shù)特定網(wǎng)絡(luò), 網(wǎng)絡(luò)瓦解問題都已經(jīng)被證明是NP-complete問題[30, 31, 37, 38, 47, 50, 76, 77]。關(guān)于網(wǎng)絡(luò)瓦解問題的計算復(fù)雜性, 可參見Lalou等撰寫的綜述[34]。

網(wǎng)絡(luò)瓦解并不是一項簡單的任務(wù)，由于其重要性和挑戰(zhàn)性, 從上個世紀(jì)中期開始受到運(yùn)籌學(xué)、網(wǎng)絡(luò)科學(xué)、計算機(jī)科學(xué)等多個學(xué)科領(lǐng)域的廣泛關(guān)注，取得了重要進(jìn)展。早期的網(wǎng)絡(luò)瓦解研究主要是從求解數(shù)學(xué)規(guī)劃模型視角入手。從上個世紀(jì)末開始，伴隨著復(fù)雜網(wǎng)絡(luò)研究的興起，基于中心性指標(biāo)和啟發(fā)式算法的網(wǎng)絡(luò)瓦解方法開始興起。近年來，進(jìn)化算法以及機(jī)器學(xué)習(xí)的最新成果開始被應(yīng)用到網(wǎng)絡(luò)瓦解研究。下面，本文將分別從數(shù)學(xué)規(guī)劃、中心性指標(biāo)、啟發(fā)式算法、進(jìn)化計算、機(jī)器學(xué)習(xí)等幾個方面總結(jié)復(fù)雜網(wǎng)絡(luò)瓦解問題的研究進(jìn)展。各個階段的典型方法以及優(yōu)缺點如表1所示。

表1 網(wǎng)絡(luò)瓦解方法的分類及其典型方法

分類

典型方法

優(yōu)缺點討論

基于數(shù)學(xué)規(guī)劃的網(wǎng)絡(luò)瓦解方法

分支定界法；隨機(jī)舍入法；混合迭代舍入法；單變量分解法；動態(tài)規(guī)劃法

能得到最優(yōu)的網(wǎng)絡(luò)瓦解方案； 對目標(biāo)函數(shù)和約束條件有較高要求, 且不適用于大規(guī)模網(wǎng)絡(luò)

基于中心性指標(biāo)的網(wǎng)絡(luò)瓦解方法

度中心性、K-核中心性、

介數(shù)中心性、接近中心性

簡單易實現(xiàn)；但單個指標(biāo)下的重要節(jié)點集合不一定是最優(yōu)的節(jié)點移除集合

基于啟發(fā)式算法的網(wǎng)絡(luò)瓦解方法

貪心算法、熟人免疫法、影響力擴(kuò)散算法、

置信傳播分解算法、分支移除法、

反向排序法、鄰居信息概率算法、

子圖度中心算法、等量圖分割法、

最小和算法、譜分割算法

瓦解效果一般優(yōu)于基于中心性指標(biāo)的網(wǎng)絡(luò)瓦解方法且具有較高的靈活性；但不一定能得到最優(yōu)的網(wǎng)絡(luò)瓦解方案

基于進(jìn)化算法的網(wǎng)絡(luò)瓦解方法

禁忌搜索算法、人工蜂群算法、遺傳算法、模擬退火算法、種群增量學(xué)習(xí)算法、

路徑再鏈接的隨機(jī)貪婪自適應(yīng)搜索算法

能得到較好的網(wǎng)絡(luò)瓦解方案, 具有高魯棒性和廣泛適用性；時間復(fù)雜度比較高

基于機(jī)器學(xué)習(xí)的網(wǎng)絡(luò)瓦解方法

FINDER算法

與具體知識、規(guī)則無關(guān), 適用于各類問題；不具有可解釋性

3. 基于數(shù)學(xué)規(guī)劃的網(wǎng)絡(luò)瓦解方法

由于網(wǎng)絡(luò)瓦解問題的本質(zhì)是一個組合優(yōu)化問題, 因此, 我們可以直接通過求解數(shù)學(xué)規(guī)劃模型來尋找最優(yōu)的網(wǎng)絡(luò)瓦解方案。從上個世紀(jì)六十年代開始[59], 主要來自于運(yùn)籌學(xué)領(lǐng)域的學(xué)者們提出了很多解決網(wǎng)絡(luò)瓦解問題的數(shù)學(xué)規(guī)劃模型和求解算法。下面, 我們簡要介紹這個領(lǐng)域的研究成果。

3.1 目標(biāo)函數(shù)為連通節(jié)點對數(shù)量

Arulselvan等[47]以連通節(jié)點對數(shù)量為目標(biāo)函數(shù), 提出了解決網(wǎng)絡(luò)瓦解問題的線性整數(shù)規(guī)劃 (integer linear programming, ILP) 模型。Di Summa等[78]在上述線性整數(shù)規(guī)劃模型基礎(chǔ)上, 通過改變約束條件和加入松弛變量, 使用分支定界方法使得模型可以在多項式時間內(nèi)求解。值得指出的是, 上述整數(shù)規(guī)劃模型中三角不等式約束的復(fù)雜度為O(n3), 從而限制了上述方法只能在小規(guī)模網(wǎng)絡(luò)上使用(一般要求N<150)。為了克服這種限制, Veremyev等[79]提出了一種緊湊約束形式, 將復(fù)雜度從O(n3)降低到O(n2), 可以應(yīng)用到中等規(guī)模網(wǎng)絡(luò)中(N=1500)。Ventresca等[80]基于隨機(jī)舍入 (randomized rounding) 方法給出了求解上述整數(shù)規(guī)劃模型的近似算法, Shen等 [81]基于混合迭代舍入 (hybrid iterative rounding) 給出了求解上述整數(shù)規(guī)劃模型的近似算法。

3.2 目標(biāo)函數(shù)為連通片數(shù)量

Shen等[82]以連通片數(shù)量為目標(biāo)函數(shù), 提出了解決網(wǎng)絡(luò)瓦解問題的混合整數(shù)規(guī)劃 (mixed integer programming, MLP) 模型。Shen等[82]提出了當(dāng)目標(biāo)函數(shù)為最大化連通片數(shù)量、最小化最大連通片規(guī)模和最大化重構(gòu)網(wǎng)絡(luò)成本情況下的整數(shù)規(guī)劃模型，并給出了針對前兩個模型的動態(tài)規(guī)劃求解算法。Veremyev等[75]提出了同時考慮移除節(jié)點和邊的混合整數(shù)規(guī)劃模型。Fan和Pardalos[83]考慮了網(wǎng)絡(luò)中邊上的權(quán)重不確定的情況, 提出了一種魯棒優(yōu)化模型 (robust optimization model)，并使用單變量分解法 (algorithm based on a decomposition on one variable)進(jìn)行求解, 實驗結(jié)果表明這一方法比直接使用分支定界的方法更有效。

4. 基于中心性指標(biāo)的復(fù)雜網(wǎng)絡(luò)瓦解方法

直接求解數(shù)學(xué)規(guī)劃雖然能夠給出最優(yōu)的網(wǎng)絡(luò)瓦解方案, 但是對目標(biāo)函數(shù)和約束條件的數(shù)學(xué)形式有很高要求, 而且由于計算復(fù)雜性的原因無法應(yīng)用于大規(guī)模網(wǎng)絡(luò)。因此, 當(dāng)面對大規(guī)模復(fù)雜網(wǎng)絡(luò)時, 研究者開始嘗試通過計算節(jié)點(邊)的中心性指標(biāo), 也可以理解為重要性指標(biāo), 按照中心性指標(biāo)的降序逐個進(jìn)行節(jié)點(邊)移除, 從而得到復(fù)雜網(wǎng)絡(luò)瓦解策略?；谥行男灾笜?biāo)的網(wǎng)絡(luò)瓦解方法的本質(zhì)是將網(wǎng)絡(luò)瓦解問題簡化為單個節(jié)點(邊)的重要性排序問題[84, 85]。

4.1 基于度中心性的復(fù)雜網(wǎng)絡(luò)瓦解方法

節(jié)點的度 (degree)，即和該節(jié)點直接相連的鄰居節(jié)點數(shù)量, 是節(jié)點最基本也是最重要的屬性之一。通常認(rèn)為, 節(jié)點的度越大意味著該節(jié)點在網(wǎng)絡(luò)中的重要性越高, 所以度中心性 (degree centrality) 是最直接也是最常用的中心性指標(biāo)。Albert等[39]研究發(fā)現(xiàn)無標(biāo)度 (scale-free) 網(wǎng)絡(luò)對于“隨機(jī)失效 (random failure) ”很健壯, 但是對于基于度中心性的“故意攻擊 (intentional attack) ”非常脆弱, 移除少量度很大的核心節(jié)點后，無標(biāo)度網(wǎng)絡(luò)就會崩潰。Petter等[40]進(jìn)一步研究了基于“重計算度中心性 (recalculated degree centrality) ”的網(wǎng)絡(luò)瓦解方法, 即每次移除網(wǎng)絡(luò)中度值最大的節(jié)點, 然后重新計算節(jié)點的度中心性。研究表明, 基于“重計算度中心性 (recalculated degree centrality) ”的網(wǎng)絡(luò)瓦解效果要優(yōu)于基于“初始度中心性 (initial degree centrality) ”的網(wǎng)絡(luò)瓦解效果。

4.2 基于K-核中心性的復(fù)雜網(wǎng)絡(luò)瓦解方法

度中心性作為一個局域信息的指標(biāo)只度量了節(jié)點的鄰居節(jié)點數(shù)目, 判定度數(shù)值相同則重要性也相同。但是, 相關(guān)研究結(jié)果表明在度量節(jié)點重要性的時候節(jié)點在網(wǎng)絡(luò)中分布的位置也是關(guān)鍵因素。在網(wǎng)絡(luò)中, 假如某個節(jié)點位于網(wǎng)絡(luò)的關(guān)鍵位置, 盡管其度值較小, 通常也有較高的節(jié)點重要性; 而位于網(wǎng)絡(luò)邊緣的高度值節(jié)點其影響力通常有限。因此, Carmi[86]等人利用K-核分解算法 (k-shell decomposition) 來度量網(wǎng)絡(luò)中節(jié)點的位置, 將網(wǎng)絡(luò)邊緣的節(jié)點逐層剝離, 位于網(wǎng)絡(luò)內(nèi)部層次的節(jié)點擁有更大的影響力。K-核分解可以看作是度中心性的一種擴(kuò)展形式, Sebastian[87]等通過引入K-核分解研究了網(wǎng)絡(luò)瓦解問題。

節(jié)點的K-核分解步驟如下：

Step1. 把度為1的節(jié)點及其所連接的邊都去掉;

Step 2. 余下的網(wǎng)絡(luò)中會重新產(chǎn)生一批度值為1的節(jié)點, 然后把上述度值為1的節(jié)點移除, 不斷迭代, 直至當(dāng)前網(wǎng)絡(luò)中不存在度值為 1 的節(jié)點。此時, 所有被移除的節(jié)點就會形成一個層, 稱作1-殼(記作Ks=1);

Step 3. 針對某個特定節(jié)點而言, 剝離一層后在余下的網(wǎng)絡(luò)中節(jié)點的度值就稱作該節(jié)點的剩余度值。根據(jù)Step 2的方法, 移除網(wǎng)絡(luò)中所有剩余度值為2的節(jié)點，不斷迭代直至移除網(wǎng)絡(luò)中的所有節(jié)點。通過實驗可以發(fā)現(xiàn)[40]，基于K-核分解的網(wǎng)絡(luò)瓦解效果要明顯低于度中心性與介數(shù)中心性策略及其衍生策略所對應(yīng)的網(wǎng)絡(luò)瓦解效果。

4.3 基于介數(shù)中心性的復(fù)雜網(wǎng)絡(luò)瓦解方法

節(jié)點的介數(shù)中心性[88] (betweenness centrality, BC) 是度量節(jié)點重要性的全局靜態(tài)特征指標(biāo), 可以刻畫某個節(jié)點在整個網(wǎng)絡(luò)中的流量負(fù)載和重要性。一般提到的介數(shù)中心性指的是最短路徑介數(shù)中心性 (Shortest Path BC), 該指標(biāo)的核心是計算網(wǎng)絡(luò)中所有節(jié)點對的最短路徑, 如果眾多節(jié)點對的最短路徑都經(jīng)過某一節(jié)點, 那么這個節(jié)點就越重要。介數(shù)中心性度量的是節(jié)點對網(wǎng)絡(luò)中按照最短路徑擴(kuò)散的信息流量的控制能力。節(jié)點vi的介數(shù)定義為

其中，gst為從節(jié)點vs到vt的所有最短路徑的數(shù)目，為從節(jié)點vs到vt的gst條最短路徑中經(jīng)過vi的最短路徑的數(shù)目?；诮閿?shù)中心性的復(fù)雜網(wǎng)絡(luò)瓦解算法其最大的弊端在于計算整個網(wǎng)絡(luò)節(jié)點對之間的最短路徑開銷較大, 當(dāng)網(wǎng)絡(luò)的規(guī)模不斷擴(kuò)大, 計算節(jié)點的介數(shù)所需要的時間開銷就會增加，通常會因為其算法復(fù)雜度太高而無法適用于處理大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)。因此, Sebastian等[87]在網(wǎng)絡(luò)瓦解問題中引入近似的介數(shù)求解算法[89], 在確定節(jié)點移除順序時只需計算近似介數(shù)即可。

4.4 基于接近中心性的復(fù)雜網(wǎng)絡(luò)瓦解方法

接近中心性 (closeness centrality) [90]根據(jù)求解節(jié)點與網(wǎng)絡(luò)中余下全部節(jié)點的距離的平均值來降低特殊值的干擾。如果某個節(jié)點與網(wǎng)絡(luò)中余下節(jié)點的平均距離值越小, 則對應(yīng)節(jié)點的接近中心性值就越大。接近中心性一般可以看作根據(jù)信息在網(wǎng)絡(luò)中的平均傳播時間來判斷節(jié)點的重要性。通常來講, 接近中心性值較大的節(jié)點對于網(wǎng)絡(luò)中信息的傳播擁有較好的觀測視角。針對擁有n個節(jié)點的連通網(wǎng)絡(luò), 能夠求解任意一個節(jié)點vi到網(wǎng)絡(luò)中其他節(jié)點的平均最短距離:

di越小意味著節(jié)點vi更接近網(wǎng)絡(luò)中的其他節(jié)點, 于是把di的倒數(shù)定義為節(jié)點vi的接近中心性, 即：

Qin等[91]在研究恐怖分子網(wǎng)絡(luò)瓦解問題時, 提出利用接近中心性指標(biāo)來進(jìn)行恐怖分子網(wǎng)絡(luò)瓦解。和基于度中心性和介數(shù)中心性的瓦解策略類似, 基于接近度的瓦解策略可以分為原始網(wǎng)絡(luò)瓦解和重復(fù)計算瓦解。接近度中心性刻畫的是節(jié)點在網(wǎng)絡(luò)中所處的位置, 它是一個全局特征指標(biāo), 該瓦解策略的瓦解效果比基于局部信息的瓦解策略稍好。

5. 基于啟發(fā)式算法的復(fù)雜網(wǎng)絡(luò)瓦解方法

雖然基于中心性指標(biāo)的復(fù)雜網(wǎng)絡(luò)瓦解方法簡單易實現(xiàn), 但是很多情況下瓦解效果并不理想, 這是因為由單個重要節(jié)點(邊)組成的集合未必就是最重要的節(jié)點(邊)集, 這就好比最厲害的兩個單打球員組合在一起未必就是最厲害的雙打組合一樣。為了提升網(wǎng)絡(luò)瓦解效果, 研究人員提出了大量基于啟發(fā)式算法的復(fù)雜網(wǎng)絡(luò)瓦解方法，成為研究復(fù)雜網(wǎng)絡(luò)瓦解問題的重要途徑。

5.1 貪心算法

貪婪算法也叫做貪心算法, 該算法的核心思想是每一步均朝著在當(dāng)前看來最好的選擇方向迭代。Arulselvan等[47]提出了基于最大獨立集 (Maximal independent set, MIS) 的貪心算法，并證明了上述貪心算法的計算復(fù)雜性為O(N2M), 因此僅適用于小規(guī)模網(wǎng)絡(luò)。此外， Aringhieri等[92]改進(jìn)了局域搜索的交換操作流程, 提出了可變鄰域搜索法 (Variable neighborhood search, VNS), 將局域搜索的復(fù)雜性降為O(N2)。Wayne等[93]在貪婪算法中加入了多啟動機(jī)制。此外，在影響力最大化的相關(guān)研究中[94-96], 也引入了多種改進(jìn)的貪婪算法進(jìn)行求解, 這些算法對于網(wǎng)絡(luò)瓦解研究也有著較大的借鑒意義。

5.2 熟人免疫法

Cohen等[41]以阻斷病毒傳播為背景提出了熟人免疫 (Acquaintance immunization) 算法。熟人免疫是從網(wǎng)絡(luò)中隨機(jī)選出若干節(jié)點, 再從這些選出的節(jié)點隨機(jī)選擇一個它們的鄰居節(jié)點進(jìn)行免疫 (移除)。這種策略巧妙地解決了基于度中心性的目標(biāo)瓦解策略 (Targeted immunization) 需要知道全局信息的問題。 Holme等[97]對熟人免疫法進(jìn)行了改進(jìn)，對于隨機(jī)選出的節(jié)點, 不是隨機(jī)在這些節(jié)點的鄰居中尋找瓦解目標(biāo), 而是選取鄰居中度最大的節(jié)點。Gallos等[43]也提出了類似的改進(jìn)方法, 對于隨機(jī)選出的節(jié)點, 在它們的鄰居中選取度大于隨機(jī)選取節(jié)點的度或者超過某個閾值的節(jié)點。

5.3 影響力擴(kuò)散算法

影響力擴(kuò)散算法 (collective influence, CI) [98]是用于度量節(jié)點的影響力, 通過劃定一定的影響力范圍, 利用該范圍中每個節(jié)點的直接鄰居和間接鄰居來定量刻畫節(jié)點的影響力數(shù)值, 進(jìn)而基于節(jié)點影響力數(shù)值的降序進(jìn)行節(jié)點移除。Mugisha等[99]提出采用CI算法進(jìn)行網(wǎng)絡(luò)瓦解, 通過選出網(wǎng)絡(luò)中擁有最大傳播影響力的節(jié)點逐一進(jìn)行移除, 其對應(yīng)的瓦解效果優(yōu)于中心性算法。

5.4 置信傳播分解算法

Zhou等[100]提出了一種稱為BPD (Belief propagation-guided decimation) 的概率模型來度量當(dāng)前網(wǎng)絡(luò)中每個節(jié)點的移除概率, 并按照移除概率進(jìn)行節(jié)點移除。 Mugisha[99]針對CI算法和BPD算法進(jìn)行了瓦解效果的比較, 并發(fā)現(xiàn)在同等條件下, BPD算法所對應(yīng)的瓦解效果要優(yōu)于CI算法。Qin[101]等引入BPD算法作為移除節(jié)點順序時的基本瓦解策略, 并采用節(jié)點爆炸性滲流算法 (Node explosive percolation, NEP) 對BPD算法選出的節(jié)點進(jìn)行排序, 即NEP-BPD (NBA) 算法, 并在多種模型網(wǎng)絡(luò)和實證網(wǎng)絡(luò)中驗證了該算法的有效性。

5.5 分支移除法

分支移除法的核心思想是令網(wǎng)絡(luò)中節(jié)點的分支權(quán)重為Wi, 若節(jié)點度為1則其對應(yīng)的Wi=1, 反之則為0。在得到第一層分支的基礎(chǔ)上, 令所有節(jié)點的分支權(quán)重等于其鄰居節(jié)點中所有度為1的分支權(quán)重之和, 并且在求和的基礎(chǔ)上自加1 (若最終得到的分支權(quán)重值超過了該連通分量中所有節(jié)點數(shù)的一半則放棄自加1) , 最后移除當(dāng)前網(wǎng)絡(luò)中度為1的分支節(jié)點, 迭代直至無法繼續(xù)移除節(jié)點。Marek等[102]提出通過評估每個節(jié)點的分支權(quán)重來進(jìn)行逐個節(jié)點移除。在多種模型網(wǎng)絡(luò)實驗中, 分支移除法的瓦解效果顯著優(yōu)于ID、IB、RD和RB等中心性算法。

5.6 反向排序法

反向排序法首先通過一定的瓦解策略對網(wǎng)絡(luò)進(jìn)行瓦解并記錄當(dāng)前網(wǎng)絡(luò)所移除的節(jié)點集Vhat, 然后從被瓦解后的網(wǎng)絡(luò)出發(fā), 將被移除節(jié)點逐個添加至被瓦解后的網(wǎng)絡(luò), 選取能夠?qū)?yīng)最小連通分量規(guī)模的被移除節(jié)點, 并將該節(jié)點放入增加節(jié)點集Vadd, 迭代直至將所有被移除節(jié)點添加到被瓦解后的網(wǎng)絡(luò), 最后將增加節(jié)點集中的所有節(jié)點序號反轉(zhuǎn)即可得到對應(yīng)最低R指標(biāo)值的瓦解策略。Marek等[102]提出從被瓦解后的網(wǎng)絡(luò) (網(wǎng)絡(luò)中僅包含孤立節(jié)點或度為1的節(jié)點) 出發(fā), 通過向網(wǎng)絡(luò)中盡可能少地增加節(jié)點和邊來重建網(wǎng)絡(luò), 最后將所增加的節(jié)點序列反轉(zhuǎn)則可以得到正向的瓦解序列。其算法復(fù)雜度為O(n2), 在模型網(wǎng)絡(luò)的瓦解實驗中, 反向排序法的瓦解效果優(yōu)于分支移除法。

5.7 鄰居信息概率算法

鄰居信息概率算法是以鄰居節(jié)點信息的概率模型為核心。Li等[103]通過設(shè)定保留機(jī)制和更新機(jī)制來進(jìn)行更優(yōu)解的搜索, 即在每一次的搜索中, 保留一定比例的節(jié)點使其狀態(tài)不變, 進(jìn)而在余下的節(jié)點中隨機(jī)選出兩個相異狀態(tài)節(jié)點并交換其當(dāng)前狀態(tài)。通過實驗發(fā)現(xiàn), 鄰居信息概率算法的瓦解效果顯著優(yōu)于度中心性策略和介數(shù)中心性策略。

5.8 子圖度中心算法

子圖度中心 (CoreHD) 算法的核心是得到網(wǎng)絡(luò)的2-核, 2-核是初始網(wǎng)絡(luò)的一個子圖, 可以通過移除初始網(wǎng)絡(luò)中所有的葉子節(jié)點來得到, 也就是移除網(wǎng)絡(luò)中所有只包含一條連邊的節(jié)點。在得到2-核的基礎(chǔ)上, 按照度中心性策略對2-核進(jìn)行節(jié)點移除。不難發(fā)現(xiàn), CoreHD算法是基于K-核分解機(jī)制將網(wǎng)絡(luò)中的一階節(jié)點全部剝離, 然后將剩余網(wǎng)絡(luò)中的節(jié)點按照節(jié)點度序列降序移除。Lenka等[104]提出了CoreHD算法來進(jìn)行網(wǎng)絡(luò)瓦解, 并將CoreHD算法與CI算法、BPD算法相比較, 發(fā)現(xiàn)CoreHD算法的瓦解效果雖稍遜于BPD算法, 但是優(yōu)于CI算法的瓦解效果, 且計算時間遠(yuǎn)低于CI算法和BPD算法。

5.9 等量圖分割法

在目標(biāo)免疫過程中, 由于部分關(guān)鍵的中心節(jié)點 (hub) 通常隱藏導(dǎo)致難以被捕捉到, 或是疫苗無法提供百分百的完全保護(hù), 造成目標(biāo)免疫效果不佳。因此, 等量圖分割算法通過改進(jìn)傳統(tǒng)的Nested Dissection (ND) 算法, 將原始網(wǎng)絡(luò)劃分成若干個擁有同等節(jié)點規(guī)模的子網(wǎng)絡(luò)。比如, 當(dāng)需要將網(wǎng)絡(luò)劃分為三塊等量子網(wǎng)絡(luò)時, 首先按照節(jié)點規(guī)模將網(wǎng)絡(luò)劃分為2:1的兩塊子網(wǎng)絡(luò), 然后再按照ND算法將較大子網(wǎng)絡(luò)分為第一節(jié)點團(tuán)、第二節(jié)點圖和分割節(jié)點團(tuán), 通過不斷優(yōu)化分割節(jié)點團(tuán)中的節(jié)點數(shù)目來將較大子網(wǎng)絡(luò)劃分為兩份等量子塊, 從而完成原始網(wǎng)絡(luò)的等量圖分割算法。顯然, 相對于目標(biāo)免疫算法, 等量圖分割算法在本質(zhì)上屬于一種基于全局信息的高效免疫算法。Chen等[105]以疾病免疫為背景, 提出了一個基于圖分割的網(wǎng)絡(luò)瓦解方法, 在達(dá)到相同瓦解效果的情況下, 該方法所需要使用的疫苗數(shù)量相較于經(jīng)典的中心性瓦解策略更少，但等量圖分割法的瓦解效果要弱于影響力擴(kuò)散算法。

5.10 最小和算法

最小和算法 (Min-sum algorithm) 的核心是將網(wǎng)絡(luò)瓦解問題轉(zhuǎn)換為消圈問題, 在移除節(jié)點集中增加一定數(shù)量的節(jié)點來消除被瓦解網(wǎng)絡(luò)中可能存在的圈。在完成網(wǎng)絡(luò)消圈后, 部分樹型連通分量的規(guī)?？赡苓€大于閾值C, 因此再對最小和算法得到的消圈網(wǎng)絡(luò)引入貪婪樹分解機(jī)制來完成最終的網(wǎng)絡(luò)瓦解。Braunstein[32]等提出了最小和算法并應(yīng)用到多種模型網(wǎng)絡(luò)和實證網(wǎng)絡(luò)中, 結(jié)果表明最小和算法的瓦解效果要顯著優(yōu)于CI等經(jīng)典瓦解算法。

5.11 譜分割算法

譜分割算法的核心是利用Courant-Fischer定理對目標(biāo)網(wǎng)絡(luò)進(jìn)行不斷分割, 即將網(wǎng)絡(luò)的分割問題最終轉(zhuǎn)化成尋找網(wǎng)絡(luò)的Laplacian矩陣的第二小特征值和特征向量問題。由Courant-Fischer定理可將網(wǎng)絡(luò)的分割問題最終轉(zhuǎn)化成尋找網(wǎng)絡(luò)的Laplacian矩陣的第二小特征值, Ren[106]等提出一種譜分割近似算法, 主要分為以下三步：(1)在單位空間中構(gòu)建隨機(jī)向量v, 令隨機(jī)向量v與Lw的最小特征向量垂直, 引入線性算子使得隨機(jī)向量v不斷迭代, 在大規(guī)模網(wǎng)絡(luò)中近似收斂到Lw的次小特征值所對應(yīng)的特征向量, 從而將目標(biāo)網(wǎng)絡(luò)分割為M和兩部分; (2)構(gòu)建子網(wǎng)絡(luò)G*=(V*, E*), 其中邊集E*表示連接M和的所有邊, 點集V*表示E*關(guān)聯(lián)的所有節(jié)點, 通過求解邊集E*中對應(yīng)最小移除成本的頂點覆蓋集來確定當(dāng)前的瓦解節(jié)點集; (3)判斷當(dāng)前最大連通片規(guī)模是否小于閾值, 滿足則算法終止, 否則繼續(xù)迭代步驟(1)-步驟(2)進(jìn)行網(wǎng)絡(luò)分割和求解頂點覆蓋集。實驗結(jié)果表明, 譜分割算法在大多數(shù)情況下優(yōu)于BPD算法、等量圖分割算法和min-sum算法, 但當(dāng)評價指標(biāo)為臨界移除比時表現(xiàn)較差。

6. 基于進(jìn)化算法的復(fù)雜網(wǎng)絡(luò)瓦解方法

雖然基于啟發(fā)式算法的網(wǎng)絡(luò)瓦解方法比基于中心性指標(biāo)的網(wǎng)絡(luò)瓦解方法更加有效, 但是大多數(shù)情況下都不是最優(yōu)的。因此, 近年來很多研究人員將進(jìn)化算法 (元啟發(fā)算法) 引入網(wǎng)絡(luò)瓦解問題, 試圖通過各種進(jìn)化手段來幫助決策者從龐大的解空間中尋找接近最優(yōu)的復(fù)雜網(wǎng)絡(luò)瓦解策略。

6.1 基于禁忌搜索的復(fù)雜網(wǎng)絡(luò)瓦解方法

禁忌搜索算法是解決組合優(yōu)化問題的常用方法, 該算法的基本思想是先生成一個初始解，再從初始解的鄰域內(nèi)搜索一個更好的解，然后將其設(shè)置為當(dāng)前最優(yōu)解, 重復(fù)這一步驟直到算法滿足終止條件為止。設(shè)置禁忌列表的目的是為了避免搜索過程陷入循環(huán)。鄧燁等[107]基于禁忌搜索研究了面向無向網(wǎng)絡(luò)的復(fù)雜網(wǎng)絡(luò)最優(yōu)瓦解策略; 禹揚(yáng)等[108]研究了基于禁忌搜索的有向網(wǎng)絡(luò)最優(yōu)瓦解策略; 祁明澤等[109]利用禁忌搜索研究了多層網(wǎng)絡(luò)的最優(yōu)瓦解策略; 鄧燁等[110]將禁忌搜索算法運(yùn)用在空間網(wǎng)絡(luò)瓦解領(lǐng)域, 禁忌搜索算法也因其高效的搜索效率和靈活的初始解構(gòu)建方法，已經(jīng)在多種瓦解場景和瓦解對象中得到了廣泛應(yīng)用。

6.2 基于人工蜂群算法的復(fù)雜網(wǎng)絡(luò)瓦解方法

人工蜂群算法由三個要素組成：食物來源、雇傭蜂和非雇傭蜂。在搜索最優(yōu)解的過程中, 使用隨機(jī)生成的蜂群開始進(jìn)行迭代搜索。在算法的迭代過程中, 不同種類的蜜蜂主要有兩種常見的行為模式：雇傭蜜蜂尋找食物源以及拋棄某個食物源。Lozano等[111]在文獻(xiàn)中將復(fù)雜網(wǎng)絡(luò)最優(yōu)瓦解策略問題轉(zhuǎn)化為求解使余下網(wǎng)絡(luò)中最大介數(shù)最小化的節(jié)點移除組合優(yōu)化問題, 并將其稱為Min-Max BC問題。通過實驗發(fā)現(xiàn)，人工蜂群算法在部分參數(shù)組合下的模型網(wǎng)絡(luò)中，其瓦解效果優(yōu)于介數(shù)瓦解策略、穩(wěn)態(tài)遺傳算法和模擬退火算法等多種基于智能優(yōu)化算法的復(fù)雜網(wǎng)絡(luò)瓦解策略。

6.3 基于遺傳算法的復(fù)雜網(wǎng)絡(luò)瓦解方法

遺傳算法 (Genetic algorithm, GA) 是基于自然界個體繁殖、變異和自然選擇的進(jìn)化過程, 由孟德爾的遺傳學(xué)和達(dá)爾文的進(jìn)化論演化而來的一種搜索算法。在遺傳算法的實際運(yùn)用過程中, 研究者通常會根據(jù)問題的特征對多個編碼字符串進(jìn)行編碼, 并將這些編碼字符串為生物界中的個體。經(jīng)過基因復(fù)制、雜交、突變等遺傳操作, 按照適者生存的自然選擇規(guī)律, 通過不斷迭代, 可以獲得比父代更優(yōu)越的個體, 使搜索朝著不斷“進(jìn)化”的方向發(fā)展。最后, 根據(jù)終止準(zhǔn)則得到近似全局最優(yōu)解。多年來, 由于其優(yōu)秀的算法特性, 在計算機(jī)科學(xué)、應(yīng)用數(shù)學(xué)、決策科學(xué)和應(yīng)用經(jīng)濟(jì)學(xué)等領(lǐng)域中得到了廣泛應(yīng)用。

鄧燁等[112]在文獻(xiàn)中介紹了基于成本約束模型求解最優(yōu)瓦解策略的遺傳算法, 并分析了最優(yōu)瓦解策略的節(jié)點選擇趨勢, 最后發(fā)現(xiàn)在成本約束條件下, 小度節(jié)點會在遺傳算法求解出的最優(yōu)瓦解策略中發(fā)揮更大作用。此外, Zhou等[113]采用模因算法 (Memetic algorithm, MA) 求解網(wǎng)絡(luò)瓦解問題, MA算法是以模因 (Meme) 為文化交流的基本單元, 結(jié)合遺傳算法和局部搜索策略的一種新型智能算法。該算法繼承了遺傳算法本身的優(yōu)點, 具有較強(qiáng)的全局優(yōu)化能力和較快的計算速度, 并通過局部調(diào)整和進(jìn)化產(chǎn)生新個體，從而極大提高了算法的局部搜索能力。

6.4 模擬退火算法

模擬退火算法是對熱力學(xué)中退火過程的模擬。在優(yōu)化算法中引入Metropolis準(zhǔn)則, 可以在多項式時間內(nèi)給出近似最優(yōu)解。其本質(zhì)是一種基于蒙特卡洛方法的一種啟發(fā)式隨機(jī)搜索算法。Ventresca等[48]在網(wǎng)絡(luò)瓦解研究領(lǐng)域引入了模擬退火算法, 為了探討該算法的有效性, 進(jìn)一步在ER隨機(jī)網(wǎng)絡(luò)、BA無標(biāo)度網(wǎng)絡(luò)和WS小世界網(wǎng)絡(luò)中討論了該算法的有效性, 取得比較好的實驗結(jié)果。

6.5 種群增量學(xué)習(xí)算法

基于群體的增量學(xué)習(xí)算法 (population based incremental learning, PBIL) 將原優(yōu)化問題的解空間S映射到基因解空間Sl?？尚薪鈙l ∈ Sl由l個基因位組成, 其中第i位的值可以是集合中的任意一個或多個。集合稱為第i位的等位基因。如果第i位只能取中的一個值, 則稱第i位為單等位基因位。對于有l(wèi)個基因位、每個基因位都可以從中取值的優(yōu)化問題, 其解可以用矩陣表示, 如果矩陣元素sij=1, 就表示第i個基因位的取值等于該基因位的第j個等位基因值。

在向量中, Pl=(P1, P2, …, Pl)表示解空間Sl中的l個基因位取對應(yīng)于該基因位的等位基因值的概率, 其中表示第i個基因位取與該基因位對應(yīng)的ni個等位基因值的概率。pij為第i個基因位取等位基因集合中第j個值的概率, 且j = 1, 2, …, ni 且。

Ventresca等[48]將種群增量學(xué)習(xí)算法和模擬退火算法運(yùn)用于多種網(wǎng)絡(luò)中, 并比較了兩種算法應(yīng)用于網(wǎng)絡(luò)瓦解研究中的有效性, 實驗結(jié)果表明種群增量學(xué)習(xí)算法優(yōu)于模擬退火算法。

6.6 基于路徑再鏈接的隨機(jī)貪婪自適應(yīng)搜索算法

貪婪隨機(jī)自適應(yīng)搜索算法 (greedy randomized adaptive search procedure, GRASP) 是一個具有多個起始點的迭代算法, 具體來說, 該算法的每次循環(huán)包括兩個階段：生成可行解和搜索局部最優(yōu)解。在生成可行解的階段, 首先初始化可行解x和候選解集C, 然后迭代構(gòu)造可行解, 每次迭代生成可行解的一個元素。在每次迭代中, 根據(jù)貪婪函數(shù)對候選集合C中的每個元素進(jìn)行評估, 作為進(jìn)入限制候選列表的基礎(chǔ), 然后從列表中隨機(jī)選取一個元素加到可行解中, 并更新候選解集合。在生成可行解階段, GRASP算法可以通過連續(xù)迭代的方式在初始可行解的鄰域內(nèi)尋找最優(yōu)解來進(jìn)行替換操作, 從而解決初始可行解質(zhì)量不高的問題, 在具體操作時, 如果局部最優(yōu)解優(yōu)x于已搜索到的最優(yōu)解x*, 則用x更新x*。

為了進(jìn)一步提高算法的有效性, 可以在第二個階段, 即搜索局部最優(yōu)解結(jié)束前考慮加入路徑重新鏈接步驟, 設(shè)置大小確定的精英集合, 設(shè)x為當(dāng)前的局部最優(yōu)解, 設(shè)y為在這個集合中隨機(jī)選擇的一個解, 如果x比y的質(zhì)量更高, 則增加一條從x到y(tǒng)的路徑, 否則增加一條從y到x的路徑。

Purevsuren等[114]將基于路徑再鏈接的隨機(jī)貪婪自適應(yīng)搜索算法引入網(wǎng)絡(luò)瓦解研究領(lǐng)域, 并在多種網(wǎng)絡(luò)上進(jìn)行了實驗, 結(jié)果表明該算法的瓦解效果優(yōu)于模擬退火算法和增量式學(xué)習(xí)算法等基于進(jìn)化算法的網(wǎng)絡(luò)瓦解方法。

7. 基于機(jī)器學(xué)習(xí)的復(fù)雜網(wǎng)絡(luò)瓦解方法

在各類求解復(fù)雜網(wǎng)絡(luò)瓦解問題的算法中, 無論是基于數(shù)學(xué)規(guī)劃模型的精確求解算法還是各種啟發(fā)式算法, 都存在非常明確的求解過程, 可以遵循一定的數(shù)學(xué)模型或啟發(fā)式規(guī)則求解目標(biāo)策略。而隨著機(jī)器學(xué)習(xí)領(lǐng)域的快速發(fā)展, 為網(wǎng)絡(luò)瓦解問題提供了一種全新的求解范式, 尤其是那些與具體知識、規(guī)則無關(guān), 但是由于節(jié)點異質(zhì)性而變得難以求解的網(wǎng)絡(luò)類型, 該問題轉(zhuǎn)換為如何通過強(qiáng)化學(xué)習(xí)訓(xùn)練智能體在已知答案的模擬網(wǎng)絡(luò)上尋找最優(yōu)瓦解策略。

強(qiáng)化學(xué)習(xí)是機(jī)器學(xué)習(xí)領(lǐng)域的三大范式之一, 它是一個不斷與環(huán)境交互、獲得反饋、更新策略、反復(fù)迭代直到學(xué)習(xí)出最優(yōu)策略的過程?；隈R爾可夫決策過程 (Markov decision process, MDP) 理論來描述這種環(huán)境交互作用如下: 該過程包含狀態(tài)空間S、動作空間A、回報函數(shù)R、狀態(tài)轉(zhuǎn)移概率V和折扣因子γ的五元組構(gòu)成。Q學(xué)習(xí)是強(qiáng)化學(xué)習(xí)的主要算法之一。它采用動作-價值函數(shù)Q(s,a)來評估策略的優(yōu)劣, 表示在初始狀態(tài)s0=s, 執(zhí)行動作后a0=a, 獲得累計獎勵的期望值。

深度強(qiáng)化學(xué)習(xí) (deep reinforcement learning, DRL) 指的是利用深度神經(jīng)網(wǎng)絡(luò)作為值函數(shù)逼近器的強(qiáng)化學(xué)習(xí)算法, 如前所述, DRL不是通過獨立估計每個狀態(tài)-動作對的Q值, 而是通過深度神經(jīng)網(wǎng)絡(luò)將狀態(tài)向量直接映射到Q值。此外, 深度神經(jīng)網(wǎng)絡(luò)可以在不需要先驗知識的情況下自動從高維原始數(shù)據(jù)中提取特征, 對于大規(guī)模的狀態(tài)空間問題是有效的。

Fan等[115]創(chuàng)新地利用深度強(qiáng)化學(xué)習(xí)算法解決網(wǎng)絡(luò)瓦解問題, 并在此基礎(chǔ)上提出了FINDER算法, 具體來說, FINDER算法首先在小規(guī)模的BA網(wǎng)絡(luò)中進(jìn)行離線學(xué)習(xí), 然后在可以利用暴力窮舉法找到最優(yōu)解的網(wǎng)絡(luò)中進(jìn)行離線學(xué)習(xí), 之后在真實場景下的網(wǎng)絡(luò)中使用之前訓(xùn)練好的智能體, 以根據(jù)當(dāng)前網(wǎng)絡(luò)持續(xù)決定要移除的節(jié)點, 最終給出節(jié)點的移除順序, 并將該算法與其他算法進(jìn)行了比較。

該過程具體分為兩步：首先是編碼操作, 具體來說, 基于圖嵌入算法GraphSAGE提取網(wǎng)絡(luò)中每個節(jié)點的特征, 而每個節(jié)點的特征向量會把該節(jié)點的特征傳遞到周圍節(jié)點。然后是解碼操作, 強(qiáng)化學(xué)習(xí)中的Q學(xué)習(xí)用于依據(jù)移除節(jié)點后的連通性變化與最優(yōu)連通性變化間的差異調(diào)整生成策略 (下一步移除哪個節(jié)點) 的神經(jīng)網(wǎng)絡(luò)的參數(shù)。該神經(jīng)網(wǎng)絡(luò)是兩層全連通結(jié)構(gòu), 并選擇Relu函數(shù)作為該神經(jīng)網(wǎng)絡(luò)的激活函數(shù), 在端對端的訓(xùn)練過程中, 待優(yōu)化的損失函數(shù)為步后網(wǎng)絡(luò)重構(gòu)誤差與Q學(xué)習(xí)的獎勵函數(shù)之和。為了證明算法的有效性, 該算法在訓(xùn)練過程中采取了兩種連通性評價指標(biāo) (連接邊/最大連通片的大小), 并分別在加權(quán)節(jié)點和未加權(quán)節(jié)點的情況下對不同的網(wǎng)絡(luò)進(jìn)行訓(xùn)練和評測, 結(jié)果表明在上述四種組合下, FINDER 算法的性能都表現(xiàn)優(yōu)異。

8. 結(jié)論與展望

復(fù)雜網(wǎng)絡(luò)瓦解因為其廣泛的應(yīng)用背景正在成為多個學(xué)科領(lǐng)域共同關(guān)注的前沿?zé)狳c, 其數(shù)學(xué)本質(zhì)是一個組合優(yōu)化問題。本文首先探討了網(wǎng)絡(luò)瓦解問題的內(nèi)涵與應(yīng)用背景, 建立了網(wǎng)絡(luò)瓦解問題的一般數(shù)學(xué)模型, 在此基礎(chǔ)上從基于解析求解、基于中心性指標(biāo)、基于啟發(fā)式算法、基于進(jìn)化計算等幾個方面系統(tǒng)總結(jié)了目前復(fù)雜網(wǎng)絡(luò)瓦解問題的研究進(jìn)展。從前文可以看出, 復(fù)雜網(wǎng)絡(luò)瓦解問題研究方興未艾, 雖然取得了大量研究成果, 但仍有很多需要進(jìn)一步研究解決的問題。作為本文的結(jié)束語, 下面我們從目標(biāo)網(wǎng)絡(luò)維度、瓦解模型維度、瓦解算法維度對復(fù)雜網(wǎng)絡(luò)瓦解問題研究的未來發(fā)展方向進(jìn)行展望。

8.1 目標(biāo)網(wǎng)絡(luò)維度

8.1.1 從無向網(wǎng)絡(luò)到有向網(wǎng)絡(luò)

當(dāng)前網(wǎng)絡(luò)瓦解研究主要集中于無向網(wǎng)絡(luò), 很少考慮有向邊對瓦解效果的影響。實際上, 現(xiàn)實世界中的目標(biāo)網(wǎng)絡(luò)很多都是有向網(wǎng)絡(luò)。例如, 恐怖組織網(wǎng)絡(luò)中的單向聯(lián)絡(luò), 交通網(wǎng)絡(luò)中的單行道等。當(dāng)前已有學(xué)者[108]初步構(gòu)建了有向網(wǎng)絡(luò)的瓦解模型, 但是如何針對網(wǎng)絡(luò)中有向邊的分布情況快速有效找出有向網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(邊)仍是一個值得關(guān)注的問題。

8.1.2 從無權(quán)網(wǎng)絡(luò)到加權(quán)網(wǎng)絡(luò)

當(dāng)前網(wǎng)絡(luò)瓦解研究主要集中于無權(quán)網(wǎng)絡(luò), 即假設(shè)網(wǎng)絡(luò)中的節(jié)點或邊都是同質(zhì)的。實際上, 現(xiàn)實世界中的目標(biāo)網(wǎng)絡(luò)很多都是加權(quán)網(wǎng)絡(luò)。例如, 恐怖組織網(wǎng)絡(luò)中的不同節(jié)點危害程度不一樣, 謠言傳播網(wǎng)絡(luò)節(jié)點之間可能有多重邊等等。如何擴(kuò)展現(xiàn)有網(wǎng)絡(luò)瓦解方法使之適用于加權(quán)網(wǎng)絡(luò)的瓦解是一個值得關(guān)注的問題。

8.1.3 從拓?fù)渚W(wǎng)絡(luò)到空間網(wǎng)絡(luò)

當(dāng)前網(wǎng)絡(luò)瓦解研究主要集中于拓?fù)渚W(wǎng)絡(luò), 很少考慮節(jié)點(邊)的地理空間位置。實際上, 現(xiàn)實世界中的目標(biāo)網(wǎng)絡(luò)很多都是地理空間網(wǎng)絡(luò)。我們在尋找網(wǎng)絡(luò)瓦解方案時不再是簡單尋找關(guān)鍵節(jié)點或關(guān)鍵邊, 而是變成尋找關(guān)鍵區(qū)域。當(dāng)前, 相關(guān)文獻(xiàn)[110, 116]已初步嘗試將優(yōu)化算法和啟發(fā)式規(guī)則運(yùn)用于求解空間網(wǎng)絡(luò)瓦解問題。但是, 如何綜合考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)和節(jié)點(邊)的位置分布, 依然是未來空間網(wǎng)絡(luò)瓦解問題的一個難點問題。

8.1.4 從單層網(wǎng)絡(luò)到多重網(wǎng)絡(luò)

當(dāng)前網(wǎng)絡(luò)瓦解研究主要集中于單層網(wǎng)絡(luò), 很少考慮多重網(wǎng)絡(luò)之間耦合、依賴、級聯(lián)等復(fù)雜關(guān)系。多重網(wǎng)絡(luò)是當(dāng)前復(fù)雜網(wǎng)絡(luò)研究的一個前沿?zé)狳c, 祁明澤等[109, 117]引入多種瓦解規(guī)則初步研究了多重網(wǎng)絡(luò)的瓦解問題。但由于多重網(wǎng)絡(luò)各層的結(jié)構(gòu)關(guān)聯(lián)性復(fù)雜, 使得多重網(wǎng)絡(luò)的瓦解問題未來仍將是一個值得關(guān)注的挑戰(zhàn)性問題。

8.1.5 從靜態(tài)網(wǎng)絡(luò)到時變網(wǎng)絡(luò)

當(dāng)前網(wǎng)絡(luò)瓦解研究主要集中于靜態(tài)網(wǎng)絡(luò), 即假設(shè)目標(biāo)網(wǎng)絡(luò)是靜態(tài)的、確定的。實際上, 現(xiàn)實世界中的目標(biāo)網(wǎng)絡(luò)很多都是動態(tài)網(wǎng)絡(luò)、時變網(wǎng)絡(luò)。例如, 無人機(jī)集群的網(wǎng)絡(luò)結(jié)構(gòu)會隨著無人機(jī)的相對位置變化而演化, 疾病傳播網(wǎng)絡(luò)中的感染只能發(fā)生在特定時間段等等。相關(guān)文獻(xiàn)[118-120]基于層間相似性和排名聚合等手段探討了時變網(wǎng)絡(luò)的節(jié)點重要性, 并以此計算了移除重要節(jié)點對時變網(wǎng)絡(luò)連通性的影響力, 而如何針對時變網(wǎng)絡(luò)層間關(guān)系與各層網(wǎng)絡(luò)結(jié)構(gòu)特點來構(gòu)建合理的網(wǎng)絡(luò)瓦解模型將是未來復(fù)雜網(wǎng)絡(luò)瓦解問題的一個難點。

8.2 瓦解模型維度

8.2.1 從結(jié)構(gòu)到動力學(xué)

當(dāng)前網(wǎng)絡(luò)瓦解研究主要集中于破壞網(wǎng)絡(luò)結(jié)構(gòu), 以降低結(jié)構(gòu)連通性為目標(biāo)。實際上, 除了破壞網(wǎng)絡(luò)結(jié)構(gòu), 通過干擾節(jié)點(邊)的動力學(xué)行為也可以達(dá)到瓦解網(wǎng)絡(luò)的目的, 例如通過誘導(dǎo)信號干擾破壞敵方無人機(jī)集群的同步。這需要我們結(jié)合瓦解背景建立相關(guān)網(wǎng)絡(luò)動力學(xué)模型來尋找最優(yōu)的網(wǎng)絡(luò)瓦解方案, 是一個值得關(guān)注的前沿方向。

8.2.2 從單目標(biāo)到多目標(biāo)

當(dāng)前網(wǎng)絡(luò)瓦解研究主要集中于單目標(biāo)瓦解, 即目標(biāo)函數(shù)只有一個。如何同時權(quán)衡考慮多個目標(biāo)函數(shù)尋找有效的網(wǎng)絡(luò)瓦解策略是一個挑戰(zhàn)性問題。多目標(biāo)進(jìn)化算法將是求解這類問題的有效途徑。

8.2.3 從簡單約束到復(fù)雜約束

當(dāng)前網(wǎng)絡(luò)瓦解研究考慮的約束較少, 大多數(shù)研究中只考慮移除節(jié)點或邊的總數(shù)量等簡單約束條件。實際上, 我們在制定網(wǎng)絡(luò)瓦解方案時要考慮時間、成本、信息或者其他特定的約束條件。如何在復(fù)雜約束條件下找到合理、有效的瓦解策略是一個亟待解決的問題。

8.2.4 從靜態(tài)決策到動態(tài)博弈

當(dāng)前網(wǎng)絡(luò)瓦解研究主要還是考慮單方面的靜態(tài)決策問題, 很少考慮攻擊者和防守者之間的博弈。實際上, 因為網(wǎng)絡(luò)瓦解的效果不僅和瓦解策略有關(guān), 還和防御策略有關(guān), 因此制定網(wǎng)絡(luò)瓦解方案不僅要考慮目標(biāo)網(wǎng)絡(luò)還要考慮保護(hù)者的防御策略。在攻防博弈框架[121-123]下, 原來看起來非常重要的關(guān)鍵節(jié)點(邊)因為考慮防御策略很可能不再被移除。在不同的網(wǎng)絡(luò)結(jié)構(gòu)中什么是攻擊者和防御者的均衡策略？這是一個十分有趣而又非常復(fù)雜的問題。

8.3 瓦解算法維度

現(xiàn)實世界中網(wǎng)絡(luò)系統(tǒng)的節(jié)點規(guī)模越發(fā)龐大, 節(jié)點數(shù)量少則幾百, 多則上百萬, 算法的計算復(fù)雜性將成為制約網(wǎng)絡(luò)瓦解問題研究的一個瓶頸。研究提出高效率、低復(fù)雜度的瓦解算法是目前復(fù)雜網(wǎng)絡(luò)瓦解問題研究的當(dāng)務(wù)之急, 其中分布式算法、并行算法以及人工智能方法將是可能解決途徑。

作者

編譯

參考文獻(xiàn)

[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]方錦清, 汪小帆, 鄭志剛, 等. 一門嶄新的交叉科學(xué):網(wǎng)絡(luò)科學(xué)(上) [J]. 物理學(xué)進(jìn)展, 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]方錦清, 汪小帆, 鄭志剛, 等. 一門嶄新的交叉科學(xué):網(wǎng)絡(luò)科學(xué)(下) [J]. 物理學(xué)進(jìn)展, 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]汪小帆, 李翔, 陳關(guān)榮. 網(wǎng)絡(luò)科學(xué)導(dǎo)論 [M]. 北京: 高等教育出版社, 2012.

Wang X F, Li X, Chen G R. Network science: An introduction [M]. Beijing: Higher Education Press, 2012

[6]劉作儀. 復(fù)雜網(wǎng)絡(luò)理論及相關(guān)管理復(fù)雜性研究的資助進(jìn)展 [J]. 中國科學(xué)基金, 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ìn), 呂欣, 吳俊, 等. 復(fù)雜網(wǎng)絡(luò)抗毀性研究若干問題的思考 [J]. 系統(tǒng)工程理論與實踐, 2008, 28(S0): 116-120.

Tan Y J, Lv X, Wu J, et al. On the invulnerable research of complex networks [J]. System Eng Theor Prac, 2008, 28(S0): 116-120.

[10]吳俊, 段東立, 趙娟, 等. 網(wǎng)絡(luò)系統(tǒng)可靠性研究現(xiàn)狀與展望 [J]. 復(fù)雜系統(tǒng)與復(fù)雜性科學(xué), 2011, 8(2): 77-86.

Wu J, Duan D L, Zhao J, et al. Status and prospects on network reliability [J]. Complex Syst Complexity Sci, 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ìn), 等. 基于社會網(wǎng)絡(luò)分析理論的恐怖組織網(wǎng)絡(luò)研究綜述 [J]. 系統(tǒng)工程理論與實踐, 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]. In: Proceedings of the 8th International Command and Control Research and Technology Symposium, National Defense War College, Washington DC, 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ìn)德, 王毅. 復(fù)雜網(wǎng)絡(luò)疾病傳播動力學(xué)研究進(jìn)展 [J]. 大學(xué)數(shù)學(xué), 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]孫皓宸, 徐銘達(dá), 許小可. 基于真實人際接觸數(shù)據(jù)的新冠肺炎校園傳播與防控 [J]. 電子科技大學(xué)學(xué)報, 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]. In: Proceeding of the 11th International Conference on Signal-Image Technology & Internet-Based Systems, 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]. In: Proceedings of the 19th ACM International Conference on Information and Knowledge Management. 2010: 1817-1820.

[27]Kobayashi T, Hasui K. Efficient immunization strategies to prevent financial contagion [J]. Sci Rep, 2014, 4(1): 1-7.

[28]金偉新. 體系對抗復(fù)雜網(wǎng)絡(luò)建模與仿真 [M]. 北京: 電子工業(yè)出版社, 2010.

Jin W X. SoS-Ops M&S based on the complex network [M]. Beijing: Publishing House of Electronics Industry, 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]. In: Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing. 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]. In: Proceedings of the International Conference on Optimization and Decision Science. Springer, Cham, 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]. In: Proceedings of the International Conference on Theory and Applications of Models of Computation. Springer, Berlin, Heidelberg, 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).

[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]. In: Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics. IEEE, 2011: 2731-2736.

[46]Ortiz-Arroyo D, Hussain D M. An information theory approach to identify sets of key players[C]. In: Proceedings of the European Conference on Intelligence and Security Informatics. Springer, Berlin, Heidelberg, 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]. In: Proceedings of the International Conference on Combinatorial Optimization and Applications. Springer, Berlin, Heidelberg, 2010: 170-183.

[84]劉建國, 任卓明, 郭強(qiáng), 等. 復(fù)雜網(wǎng)絡(luò)中節(jié)點重要性排序的研究進(jìn)展 [J]. 物理學(xué)報, 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]任曉龍, 呂琳媛. 網(wǎng)絡(luò)重要節(jié)點排序方法綜述 [J]. 科學(xué)通報, 2014, 59(13): 1175-1197.

Ren X L, Lv 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]. In: Proceedings of the Tenth Workshop on Algorithm Engineering and Experiments. Society for Industrial and Applied Mathematics, 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]. In: Proceedings of the International Conference on Intelligence and Security Informatics. Springer, Berlin, Heidelberg, 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, 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. 2010: 1029-1038.

[96]胡慶成, 尹龑燊, 馬鵬斐, 等. 一種新的網(wǎng)絡(luò)傳播中最有影響力的節(jié)點發(fā)現(xiàn)方法[J]. 物理學(xué)報, 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]Li Q, Liu S, Yang X. Neighborhood information-based probabilistic algorithm for network disintegration [J]. Expert Syst Appl, 2020, 139: 112853.

[104]Zdeborova L, Zhang P, Zhou H. Fast and simple decycling and dismantling of networks [J]. Sci Rep, 2016, 6(1): 1-6.

[105]Chen Y, Paul G, Havlin S, et al. Finding a better immunization strategy [J]. Phys Rev Lett, 2008, 101(5): 058701.

[106]Ren X, Gleinig N, Helbing D, et al. Generalized network dismantling [J]. Proc Natl Acad Sci USA, 2019, 116(14): 6554-6559.

[107]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.

[108]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.

[109]Qi M, Deng Y, Deng H, et al. Optimal disintegration strategy in multiplex networks [J]. Chaos, 2018, 28(12): 121104.

[110]Deng Y, Wu J, Qi M, et al. Optimal disintegration strategy in spatial networks with disintegration circle model [J]. Chaos, 2019, 29(6): 061102.

[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]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.

[113]Zhou Y, Hao J, Glover F. Memetic search for identifying critical nodes in sparse graphs [J]. IEEE Trans Cybern, 2019, 49(10): 3699-3712.

[114]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.

[115]Fan C, Zeng L, Sun Y, et al. Finding key players in complex networks through deep reinforcement learning [J]. Nature Mach Intell, 2020, 2: 317–324.

[116]Wang Z G, Deng Y, Wang Z, et al. Disintegrating spatial networks based on region centrality [J]. Chaos, 2021, 31(6): 061101.

[117]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.

[118]郭強(qiáng), 殷冉冉, 劉建國. 基于TOPSIS的時序網(wǎng)絡(luò)節(jié)點重要性研究 [J]. 電子科技大學(xué)學(xué)報, 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.

[119]梁耀洲, 郭強(qiáng), 殷冉冉, 等. 基于排名聚合的時序網(wǎng)絡(luò)節(jié)點重要性研究 [J]. 電子科技大學(xué)學(xué)報, 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.

[120]楊劍楠, 劉建國, 郭強(qiáng). 基于層間相似性的時序網(wǎng)絡(luò)節(jié)點重要性研究 [J]. 物理學(xué)報, 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.

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

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

[123]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.

參考文獻(xiàn)可上下滑動查看

復(fù)雜網(wǎng)絡(luò)瓦解讀書會

從復(fù)雜網(wǎng)絡(luò)的構(gòu)建到智能優(yōu)化的演化，理解網(wǎng)絡(luò)的魯棒性與瓦解機(jī)制始終是一個深刻的挑戰(zhàn)。更值得深思的是，網(wǎng)絡(luò)的結(jié)構(gòu)和算法設(shè)計如何決定了網(wǎng)絡(luò)在遭遇局部攻擊時的脆弱性，及其整體瓦解的速度與范圍。動態(tài)演化過程中的節(jié)點和邊的變化，也會影響系統(tǒng)如何在瓦解中保持部分功能，或如何適應(yīng)新的結(jié)構(gòu)。因此，網(wǎng)絡(luò)瓦解研究聚焦于一個核心問題：在不同類型的網(wǎng)絡(luò)結(jié)構(gòu)（如高階網(wǎng)絡(luò)、空間網(wǎng)絡(luò)、時序網(wǎng)絡(luò)）中，局部的破壞如何引發(fā)整體功能的喪失？在面對網(wǎng)絡(luò)的異質(zhì)性和約束條件下，不同的優(yōu)化算法如何有效識別并摧毀關(guān)鍵節(jié)點與連接，從而最大化網(wǎng)絡(luò)的瓦解效應(yīng)，進(jìn)而影響系統(tǒng)的整體穩(wěn)定性與韌性？

集智俱樂部聯(lián)合北京師范大學(xué)教授吳俊、國防科技大學(xué)副研究員譚索怡、北京化工大學(xué)副教授谷偉偉、中國科學(xué)技術(shù)大學(xué)博士后范天龍、國防科技大學(xué)在讀博士卿楓共同發(fā)起，跨越網(wǎng)絡(luò)結(jié)構(gòu)、算法模型與應(yīng)用場景的視角，探索復(fù)雜網(wǎng)絡(luò)瓦解的前沿進(jìn)展。重點探討不同算法與優(yōu)化框架如何幫助我們認(rèn)識網(wǎng)絡(luò)的脆弱性，并在現(xiàn)實約束下推動網(wǎng)絡(luò)系統(tǒng)的智能演化與應(yīng)用發(fā)展。

詳情請見：

1.

2.

3.

4.

5.

6.

7.