復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)組識(shí)別問題模型和算法研究*

江 成，張 軍，盧 山

首都經(jīng)濟(jì)貿(mào)易大學(xué) 信息學(xué)院，北京 100070

1 引言

隨著科技進(jìn)步和全球一體化進(jìn)程加速，人們?nèi)找嫣幱诟鞣N復(fù)雜網(wǎng)絡(luò)中。例如，互聯(lián)網(wǎng)網(wǎng)絡(luò)、電力和交通網(wǎng)絡(luò)、經(jīng)濟(jì)和金融網(wǎng)絡(luò)以及社會(huì)網(wǎng)絡(luò)等。這些網(wǎng)絡(luò)中存在一些對結(jié)構(gòu)和功能影響程度更大的特殊節(jié)點(diǎn)，通常被稱為關(guān)鍵節(jié)點(diǎn)。這些關(guān)鍵節(jié)點(diǎn)在網(wǎng)絡(luò)中雖然數(shù)量不多，卻可以快速波及并影響網(wǎng)絡(luò)中的大部分節(jié)點(diǎn)[1]。例如，TOMsInsight團(tuán)隊(duì)針對2014年“冰桶挑戰(zhàn)”形成的社會(huì)網(wǎng)絡(luò)數(shù)據(jù)分析發(fā)現(xiàn)：53%名人將相關(guān)視頻、圖片和文字發(fā)布到社交網(wǎng)絡(luò)，被傳播展示占比高達(dá)99%，而47%非名人被傳播展示占比不到1%[2]。由此可見，社會(huì)網(wǎng)絡(luò)傳播中的關(guān)鍵節(jié)點(diǎn)——名人效應(yīng)是非常顯著的。

關(guān)鍵節(jié)點(diǎn)組識(shí)別問題是指[3]：在資源有限的情況下，從給定的網(wǎng)絡(luò)圖G=(V,E)中選擇K個(gè)節(jié)點(diǎn)（V、E分別代表節(jié)點(diǎn)集和邊集，K為正整數(shù)），使得移除這K個(gè)節(jié)點(diǎn)后，剩余網(wǎng)絡(luò)的某種衡量指標(biāo)（如離散程度或傳播效應(yīng)等）最優(yōu)化。關(guān)鍵節(jié)點(diǎn)組識(shí)別問題作為復(fù)雜網(wǎng)絡(luò)微觀層面的重要研究內(nèi)容，直接關(guān)系到信息的傳播速度和影響范圍，吸引了管理學(xué)、信息科和物理科學(xué)等多個(gè)領(lǐng)域?qū)W者的共同關(guān)注，并得到了廣泛的應(yīng)用。例如，流行病傳播網(wǎng)絡(luò)中，在醫(yī)療資源有限的情況下，對哪些關(guān)鍵個(gè)體優(yōu)先接種免疫以最有效阻斷病毒大規(guī)模傳播的問題[4]；通信網(wǎng)絡(luò)中，對哪些影響力重要性用戶重點(diǎn)識(shí)別以提升網(wǎng)絡(luò)消息傳播效率的問題[5]；恐怖主義網(wǎng)絡(luò)中，選擇哪些關(guān)鍵恐怖分子使得其被定點(diǎn)清除后網(wǎng)絡(luò)的破壞程度最大，即最小化恐怖主義襲擊活動(dòng)可能性的問題[6]；交通網(wǎng)絡(luò)中，選擇哪些關(guān)鍵基礎(chǔ)設(shè)施重點(diǎn)保護(hù)，使得不致于因?yàn)橐馔庠蚨鴮?dǎo)致網(wǎng)絡(luò)大面積癱瘓的問題[7]。此外，關(guān)鍵節(jié)點(diǎn)組識(shí)別問題在電力系統(tǒng)關(guān)鍵部件保護(hù)[8]，生物網(wǎng)絡(luò)關(guān)鍵蛋白和基因的識(shí)別[9]，社會(huì)網(wǎng)絡(luò)意見領(lǐng)袖挖掘[10]等領(lǐng)域也有著重要應(yīng)用。總結(jié)國內(nèi)外已有研究可見，目前關(guān)鍵節(jié)點(diǎn)組識(shí)別問題研究主要是基于仿真模擬、指標(biāo)度量和數(shù)學(xué)建模三種方式開展的。

在仿真模擬方面，已有研究大多借鑒流行病學(xué)中的疾病傳播模型來模擬網(wǎng)絡(luò)中節(jié)點(diǎn)的影響力傳播。因而，在這種類型方法下，復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)組識(shí)別問題經(jīng)常被等同于節(jié)點(diǎn)影響力最大化問題[11]。如Saito等基于SIS（susceptible infected susceptible）疾病傳播模型構(gòu)建了一個(gè)多層的圖結(jié)構(gòu)，用于識(shí)別社會(huì)網(wǎng)絡(luò)中最具影響力的節(jié)點(diǎn)[12]。Salamanos等通過圖采樣方法來識(shí)別復(fù)雜網(wǎng)絡(luò)中最具影響力的節(jié)點(diǎn)，并基于SIS和SIR（susceptible infected recovered）疾病傳播模型進(jìn)行實(shí)驗(yàn)?zāi)M[13]；王禎駿等提出了一種融合內(nèi)容信息和動(dòng)態(tài)時(shí)間特性的影響力傳播模型，并借助該模型識(shí)別社會(huì)網(wǎng)絡(luò)中最有影響力的用戶[14]；張?jiān)骑w等針對多個(gè)影響力同時(shí)傳播且影響力間存在促進(jìn)傳播關(guān)系的情況下，對關(guān)聯(lián)影響力傳播最大化問題進(jìn)行建模，并提出基于節(jié)點(diǎn)激活貢獻(xiàn)估計(jì)的求解算法[15]。

在指標(biāo)度量方面，基于圖論的指標(biāo)經(jīng)常用來評價(jià)節(jié)點(diǎn)的重要性，例如，節(jié)點(diǎn)的中心度[16]、節(jié)點(diǎn)的介數(shù)[17]、節(jié)點(diǎn)的緊度[18]、節(jié)點(diǎn)的特征值[19]、K殼分解[20]等。然而這些指標(biāo)只能反映網(wǎng)絡(luò)的單一屬性，忽略了整體結(jié)構(gòu)和功能。為此，Borgatti從網(wǎng)絡(luò)的整體結(jié)構(gòu)出發(fā)，提出了衡量網(wǎng)絡(luò)離散程度的專用度量指標(biāo)DF，但直接優(yōu)化DF因計(jì)算復(fù)雜度高而缺乏實(shí)際操作的可行性，因此其采用貪婪搜索方法對DF求解[3]?？傮w來看，指標(biāo)度量方法反映了網(wǎng)絡(luò)拓?fù)涞木植刻匦曰蛉痔匦?，設(shè)計(jì)容易，簡單直觀。但是，按照指標(biāo)對單個(gè)節(jié)點(diǎn)重要性排序結(jié)果選擇的前K個(gè)節(jié)點(diǎn)組合，往往并不是復(fù)雜網(wǎng)絡(luò)整個(gè)最優(yōu)的K個(gè)關(guān)鍵節(jié)點(diǎn)集合[21]。

近年來，基于數(shù)學(xué)建模的方法逐漸得到國內(nèi)外相關(guān)學(xué)者的關(guān)注。例如，Arulselvan等率先提出了整數(shù)線性規(guī)劃模型，通過最小化剩余網(wǎng)絡(luò)中連通分支的個(gè)數(shù)識(shí)別稀疏網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)集合，奠定了關(guān)鍵節(jié)點(diǎn)組識(shí)別問題的主流模型地位[22]。由于在求解精度上較基于仿真模擬和指標(biāo)度量的方法更占優(yōu)勢，該模型得到了學(xué)者們的關(guān)注，并且衍生出一些變體模型，例如最大化剩余網(wǎng)絡(luò)連通分支的個(gè)數(shù)[23-24]和最小化最大連通分支中的節(jié)點(diǎn)個(gè)數(shù)[25]等。此外，現(xiàn)有研究已經(jīng)證明關(guān)鍵節(jié)點(diǎn)組識(shí)別問題是NP難問題[22]，因此基于貪婪搜索[26]、遺傳算法[27]、模擬退火[28]的一些啟發(fā)式算法也被提出來用于求解這些識(shí)別模型。更多關(guān)于關(guān)鍵節(jié)點(diǎn)組識(shí)別的研究方法請參考文獻(xiàn)[29-31]。

根據(jù)以上分析可見，現(xiàn)有的關(guān)鍵節(jié)點(diǎn)組識(shí)別方法較多，但各有側(cè)重。其中，基于仿真模擬的方法側(cè)重于從功能性傳播角度研究節(jié)點(diǎn)影響力，而對網(wǎng)絡(luò)整體結(jié)構(gòu)的穩(wěn)定性考慮不足；基于指標(biāo)度量的方法，因其簡單直觀，計(jì)算復(fù)雜度較低，成為目前主要的識(shí)別方法，但其更適合于節(jié)點(diǎn)重要性排序問題[32-34]，對多個(gè)關(guān)鍵節(jié)點(diǎn)集合的識(shí)別問題評價(jià)不夠全面。而在數(shù)學(xué)建模方面，盡管已有研究在關(guān)鍵節(jié)點(diǎn)組識(shí)別問題上已經(jīng)取得了顯著的成果，但是當(dāng)前模型方法單一，并且現(xiàn)有的整數(shù)線性規(guī)劃模型本身存在不能夠區(qū)分連通分支內(nèi)部結(jié)構(gòu)的缺陷。

為此，本文從網(wǎng)絡(luò)的整體結(jié)構(gòu)和功能出發(fā)，對復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)組識(shí)別問題模型和算法進(jìn)行研究，本文的主要貢獻(xiàn)如下：

（1）構(gòu)建基于0-1二次約束二次規(guī)劃的關(guān)鍵節(jié)點(diǎn)組識(shí)別模型，通過最小化二階路徑內(nèi)連通節(jié)點(diǎn)對的個(gè)數(shù)，實(shí)現(xiàn)區(qū)分連通分支內(nèi)部結(jié)構(gòu)的能力。

（2）提出兩種模型求解方法：一種是松弛為半正定規(guī)劃模型并利用內(nèi)點(diǎn)算法求解，這種方法適用于小規(guī)模網(wǎng)絡(luò)的近似求解；另一種是設(shè)計(jì)貪婪搜索和局部置換相結(jié)合的啟發(fā)式算法，用于大規(guī)模網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)組識(shí)別。

（3）進(jìn)行了大量人工隨機(jī)圖和真實(shí)復(fù)雜網(wǎng)絡(luò)數(shù)據(jù)集的實(shí)驗(yàn)分析，驗(yàn)證了所建立模型和算法的正確性和有效性。

2 相關(guān)工作

Krackhardt構(gòu)建了用于計(jì)算每個(gè)連通分支內(nèi)部連通節(jié)點(diǎn)對個(gè)數(shù)的度量指標(biāo)[35]，如下所示：

式中，sk表示移除關(guān)鍵節(jié)點(diǎn)后剩余網(wǎng)絡(luò)中第k個(gè)連通分支中的節(jié)點(diǎn)個(gè)數(shù)。該指標(biāo)計(jì)算簡單，計(jì)算復(fù)雜度較低，可以通過枚舉方法求解，但其忽視了連通分支的內(nèi)部結(jié)構(gòu)。在此基礎(chǔ)上，從網(wǎng)絡(luò)的整體結(jié)構(gòu)出發(fā)，文獻(xiàn)[3]提出了衡量網(wǎng)絡(luò)離散程度的專用指標(biāo)DF，定義如下：

式中，dij表示節(jié)點(diǎn)對i和j之間的最短路徑，DF∈[0,1]，且DF值越大，網(wǎng)絡(luò)的離散程度越大。DF指標(biāo)雖然設(shè)計(jì)比較完善，但因其計(jì)算復(fù)雜度高，導(dǎo)致對其直接優(yōu)化缺乏實(shí)際操作的可行性。

在Krackhardt指標(biāo)基礎(chǔ)上，Arulselvan等建立了最小化剩余網(wǎng)絡(luò)連通節(jié)點(diǎn)對個(gè)數(shù)的整數(shù)線性規(guī)劃模型（integer linear programming，ILP）[22]，以便更好地洞察和深入理解關(guān)鍵節(jié)點(diǎn)組識(shí)別問題。然而，該模型和其衍生出的變體模型均存在不能夠區(qū)分連通分支的內(nèi)部結(jié)構(gòu)的缺陷，這一問題直接導(dǎo)致了實(shí)際優(yōu)化效果并不理想。

3 模型規(guī)劃

為解決當(dāng)前主流的整數(shù)線性規(guī)劃模型對連通分支內(nèi)部結(jié)構(gòu)的考慮不足，本文將基于DF指標(biāo)建立數(shù)學(xué)模型，并提出新的計(jì)算解決方法。

3.1 模型的建立

基于0-1二次約束二次規(guī)劃（quadratically constrained quadratic programming，QCQP）建立模型，具體規(guī)劃如下：

其中，A是網(wǎng)絡(luò)的鄰接矩陣，如果節(jié)點(diǎn)i和j是鄰居節(jié)點(diǎn)，則aij=1，否則aij=0；vi=1表示節(jié)點(diǎn)i作為關(guān)鍵節(jié)點(diǎn)被移除，否則，vi=0；xij=1表示在移除關(guān)鍵節(jié)點(diǎn)后剩余網(wǎng)絡(luò)中節(jié)點(diǎn)i和j是鄰居節(jié)點(diǎn)，否則xij=0。此模型的目標(biāo)函數(shù)是最小化剩余網(wǎng)絡(luò)中二階路徑內(nèi)連通節(jié)點(diǎn)對的個(gè)數(shù)；約束（3）重新計(jì)算了移除關(guān)鍵節(jié)點(diǎn)后剩余網(wǎng)絡(luò)的鄰接矩陣，即如果節(jié)點(diǎn)對i和j在原網(wǎng)絡(luò)中是鄰居節(jié)點(diǎn)，但節(jié)點(diǎn)i或j被作為關(guān)鍵節(jié)點(diǎn)移除的話，則節(jié)點(diǎn)i和j之間的邊消失，并且這兩個(gè)節(jié)點(diǎn)在剩余網(wǎng)絡(luò)鄰接矩陣中對應(yīng)的值為0；約束（4）表示在資源有限的條件下，被移除的關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)不能超過K個(gè)。約束（5）約束模型為0-1非線性規(guī)劃模型。

3.2 模型與DF指標(biāo)的關(guān)系

（1）當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)為完全圖時(shí)，誤差為0；

（2）當(dāng)網(wǎng)絡(luò)結(jié)構(gòu)為星型網(wǎng)絡(luò)時(shí)，目標(biāo)引入的誤差也為0；

4 算法求解

由于QCQP是非凸的二次規(guī)劃模型，為了高效求解，本文采取兩種求解途徑：一種是將其松弛為半正定規(guī)劃模型進(jìn)行求解；另一種方法通過設(shè)計(jì)啟發(fā)式算法加以求解。

4.1 半正定松弛求解方法

這里對QCQP模型寫成矩陣表示形式，并松弛為半正定規(guī)劃模型（semi-definite programming relaxation，SDPR）的形式如下：

這里，W為將QCQP模型寫成矩陣形式的系數(shù)矩陣。y=(x11,x12,…,x1n,x21,x22,…,x2n,…,xn1,xn2,…,xnn)。利用商用軟件Matlab調(diào)用Gurobi接口中的內(nèi)點(diǎn)算法，可以快速求解SDPR模型。需要注意的是，這種快速求解的松弛方法只提供了QCQP模型問題最優(yōu)解的一個(gè)下界。當(dāng)然，可以在此下界的基礎(chǔ)上，進(jìn)一步設(shè)計(jì)分支定界算法求取最優(yōu)解。

4.2 啟發(fā)式算法求解

采用貪婪搜索和局部置換相結(jié)合的思想，設(shè)計(jì)了一種新的啟發(fā)式算法。

算法1QCQP模型啟發(fā)式算法

輸入：網(wǎng)絡(luò)圖G和關(guān)鍵節(jié)點(diǎn)組個(gè)數(shù)K。

輸出：關(guān)鍵節(jié)點(diǎn)組集合和目標(biāo)函數(shù)值。

（1）初始化一個(gè)空集S。若集合的元素個(gè)數(shù)小于K值，則最大化QCQP模型目標(biāo)函數(shù)值，貪婪地向集合中逐個(gè)增加節(jié)點(diǎn)，直到該集合元素個(gè)數(shù)等于K。

（2）每次從S集合、V-S集合中各選取一個(gè)節(jié)點(diǎn)嘗試互換，進(jìn)行2節(jié)點(diǎn)交換的局部搜索。如果交換能夠減少目標(biāo)函數(shù)值，則進(jìn)行互換，否則不互換。直至遍歷所有2節(jié)點(diǎn)交換組合。

（3）返回目標(biāo)函數(shù)值最小下的節(jié)點(diǎn)組合S，以及相應(yīng)的目標(biāo)函數(shù)值。

4.3 復(fù)雜度分析

松弛求解方法的時(shí)間復(fù)雜度為O((n3.5)4)，計(jì)算成本較高，只適合小規(guī)模網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)組識(shí)別。而啟發(fā)式算法的計(jì)算復(fù)雜度為O(n3)，適用于識(shí)別較大規(guī)模網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)組識(shí)別。如果需要進(jìn)一步降低算法復(fù)雜度，可以結(jié)合群體智能算法加以優(yōu)化。

5 實(shí)驗(yàn)分析

本章選取了多組不同規(guī)模的隨機(jī)圖和真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，其中人工數(shù)據(jù)集可以通過圖模型隨機(jī)生成，而真實(shí)數(shù)據(jù)集可以從佛羅里達(dá)大學(xué)開源數(shù)據(jù)庫中下載獲取[36]。由于關(guān)鍵節(jié)點(diǎn)組識(shí)別問題限定在資源有限的條件下，因此本文討論的實(shí)驗(yàn)結(jié)果限制在K≤|V|/2條件下。本文采用的松弛求解方法的編程語言為Matlab，調(diào)用Gurobi和CVX接口；啟發(fā)式算法求解的編程語言為Java。所有編程語言的實(shí)驗(yàn)運(yùn)行環(huán)境是1.70 GHz英特爾驍龍?zhí)幚砥鳎?6 GB內(nèi)存，Windows操作系統(tǒng)。

5.1 人工網(wǎng)絡(luò)實(shí)驗(yàn)

為了驗(yàn)證模型的魯棒性，本文選取了多種連接結(jié)構(gòu)的網(wǎng)絡(luò)圖進(jìn)行實(shí)驗(yàn)，包括Erdos-Renyi圖[37]、Geometric圖[38]、Sticky 圖[39]、Range因果圖[40]和 Kleinberg圖[41]，并且每種類型網(wǎng)絡(luò)都隨機(jī)選取了不同的規(guī)模。雖然可以比較K≤|V|/2的結(jié)果，直至DF=1為止。但由于空間所限，此處僅針對Erdos-Renyi(|V|=14,|E|=36)列出全部結(jié)果，如表1所示。其余實(shí)驗(yàn)數(shù)據(jù)集僅列出K≤5的結(jié)果，如表2～表5所示。其中，K為所識(shí)別關(guān)鍵節(jié)點(diǎn)的個(gè)數(shù)，Obj為移除關(guān)鍵節(jié)點(diǎn)后的模型目標(biāo)函數(shù)值，T為運(yùn)算執(zhí)行時(shí)間，度量時(shí)間為毫秒（ms），DF指標(biāo)用來評價(jià)識(shí)別結(jié)果的好壞，上標(biāo)“*”表示性能比較中占優(yōu)的一方。以Erdos-Renyi圖為例，從表1中可以看出，盡管本文利用松弛方法只求得QCQP問題的近似解，但在大部分情況下，求解的效果都好于傳統(tǒng)的整數(shù)線性規(guī)劃模型。例如，表1中第3行表示了一個(gè)具有14個(gè)節(jié)點(diǎn)和36條邊的E-R隨機(jī)網(wǎng)絡(luò)，當(dāng)關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)為1時(shí)，ILP模型及其啟發(fā)式算法得到的目標(biāo)函數(shù)值均為79，相應(yīng)的DF值是0.419 4和0.413 9；而本文提出的SDPR模型及QCQP啟發(fā)式算法得到的目標(biāo)函數(shù)值均為386，相應(yīng)的DF值均為0.435 9。這說明SDPR模型和QCQP啟發(fā)式所識(shí)別的關(guān)鍵節(jié)點(diǎn)，被移除后造成的網(wǎng)絡(luò)離散程度更大，在識(shí)別效果上更為有效。當(dāng)然，也存在ILP模型和啟發(fā)式勝出的少數(shù)情形，這是由于本文所提出的近似求解方法只求得SDPR模型的近似解，在某些情況下會(huì)略遜于ILP模型求得的最優(yōu)解。但從表1～表5的整體實(shí)驗(yàn)效果來看，SDPR模型和QCQP啟發(fā)式算法在大部分實(shí)驗(yàn)情況下均取得了較好實(shí)驗(yàn)效果。

Table 1 Results on Erdos-Renyi(|V|=14,|E|=36)networks表1 Erdos-Renyi(|V|=14,|E|=36)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

Table 2 Results on geometric(|V|=10,|E|=15)networks表2 Geometric(|V|=10,|E|=15)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

Table 3 Results on Sticky(|V|=12,|E|=9)networks表3 Sticky(|V|=12,|E|=9)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

Table 4 Results on Range dependent(|V|=14,|E|=15)networks表4 Range因果 (|V|=14,|E|=15)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

Table 5 Results on Kleinberg(|V|=16,|E|=47)networks表5 Kleinberg(|V|=16,|E|=47)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

Fig.1 Statistical results on Erdos-Renyi networks圖1 Erdos-Renyi隨機(jī)網(wǎng)絡(luò)實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

Fig.2 Statistical results on Range dependent networks圖2 Range因果網(wǎng)絡(luò)實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

Fig.3 Statistical results on small world networks圖3 小世界網(wǎng)絡(luò)實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

此外，針對Erdos-Renyi隨機(jī)圖、Range因果圖和小世界網(wǎng)絡(luò)圖，本文又分別隨機(jī)生成不同規(guī)模下（節(jié)點(diǎn)8、節(jié)點(diǎn)10和節(jié)點(diǎn)12）的網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，統(tǒng)計(jì)分析本文所提出方法與傳統(tǒng)ILP方法比較情況下，勝出、平局和敗出各自所占的比例。圖1～圖3分別展示了在100組Erdos-Renyi隨機(jī)圖、Range因果圖和小世界網(wǎng)絡(luò)圖在節(jié)點(diǎn)規(guī)模為8、10和12規(guī)模下實(shí)驗(yàn)的統(tǒng)計(jì)情況分布圖。從圖中可以看出，本文提出的方法在大多數(shù)情況下占優(yōu)。

5.2 真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)

為了驗(yàn)證本文所提出算法的有效性，本文進(jìn)一步選取了Can73通信網(wǎng)絡(luò)、Football115合作網(wǎng)絡(luò)、Jazz198音樂家社交網(wǎng)絡(luò)和Celegans453網(wǎng)絡(luò)標(biāo)準(zhǔn)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。由于空間所限，此處僅列出K≤10的結(jié)果，從表6～表9可見，本文所提出的QCQP啟發(fā)式算法在大多數(shù)情況下識(shí)別的DF效果好于ILP啟發(fā)式算法的DF值，并且在計(jì)算時(shí)間上占優(yōu)，QCQP啟發(fā)式算法的運(yùn)行效率大約是ILP啟發(fā)式算法的102～103倍。

從表6～表9中可見，本文所提出的QCQP啟發(fā)式算法在大部分情況下效果占優(yōu)。但由于QCQP啟發(fā)式求解的是QCQP模型的近似解，因此在個(gè)別點(diǎn)也存在不如ILP模型啟發(fā)式的情況，后續(xù)可以進(jìn)一步設(shè)計(jì)精確求解算法。為了能夠進(jìn)一步從“實(shí)際角度”解釋關(guān)鍵節(jié)點(diǎn)，本文又基于“9?11”恐怖襲擊網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)。將本文方法識(shí)別出關(guān)鍵恐怖分子群組，與“9?11”恐怖襲擊事件調(diào)查報(bào)告[42]所公布的恐怖分子地位進(jìn)行比較驗(yàn)證。實(shí)驗(yàn)結(jié)果表明：本文方法所識(shí)別出關(guān)鍵恐怖分子頭目群組，與“9?11”恐怖襲擊事件調(diào)查中利用社交網(wǎng)絡(luò)度、介性和緊度分析得到的恐怖分子頭目吻合度較好，具體實(shí)驗(yàn)的結(jié)果如表10所示。

Table 6 Results on Can(|V|=73,|E|=47)networks表6 Can(|V|=73,|E|=47)通信網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

Table 7 Results on Football(|V|=115,|E|=47)social networks表7 Football(|V|=115,|E|=47)社交網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

Table 8 Results on Jazz(|V|=198,|E|=47)social networks表8 Jazz(|V|=198,|E|=47)社交網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

Table 9 Results on Celegans(|V|=453,|E|=2 025)networks表9 Celegans(|V|=453,|E|=2 025)網(wǎng)絡(luò)實(shí)驗(yàn)結(jié)果

為了展示移除關(guān)鍵節(jié)點(diǎn)后網(wǎng)絡(luò)的變化情況，圖4～圖6以Can73通信網(wǎng)絡(luò)為例，分別可視化展示了ILP啟發(fā)式方法和QCQP啟發(fā)式算法在K=1、K=5和K=10的識(shí)別結(jié)果。

6 總結(jié)與展望

本文從網(wǎng)絡(luò)整體結(jié)構(gòu)出發(fā)，提出了一種非凸的0-1二次約束二次規(guī)劃模型，模型的目標(biāo)是最小化移除關(guān)鍵節(jié)點(diǎn)后剩余網(wǎng)絡(luò)中二階路徑內(nèi)的連通節(jié)點(diǎn)對的個(gè)數(shù)，通過這樣的建模方法，實(shí)現(xiàn)了區(qū)分連通分支內(nèi)部結(jié)構(gòu)的能力。在此基礎(chǔ)上，本文又設(shè)計(jì)了兩種模型求解方法：一種是通過半正定松弛的方法識(shí)別小規(guī)模網(wǎng)絡(luò)中的關(guān)鍵節(jié)點(diǎn)組；另一種是設(shè)計(jì)了結(jié)合貪婪搜索和局部置換的啟發(fā)式算法，以適應(yīng)大規(guī)模網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)組識(shí)別。通過在多組不同規(guī)模的隨機(jī)網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)實(shí)驗(yàn)，驗(yàn)證了模型和算法的正確性和有效性。在未來的研究中，本文將擴(kuò)展模型到大規(guī)模網(wǎng)絡(luò)、有向有權(quán)網(wǎng)絡(luò)以及動(dòng)態(tài)網(wǎng)絡(luò)中進(jìn)行識(shí)別應(yīng)用。

Table 10 Comparisons on“9?11”terrorist attack dataset(|V|=63,|E|=154)表10 “9?11”恐怖襲擊數(shù)據(jù)集（|V|=63,|E|=154）上的實(shí)驗(yàn)比較

Fig.4 Experimental results on Can73 network for K=1圖4 Can73通信網(wǎng)絡(luò)上K=1時(shí)實(shí)驗(yàn)結(jié)果對比

Fig.5 Experimental results on Can73 network for K=5圖5 Can73通信網(wǎng)絡(luò)上K=5時(shí)實(shí)驗(yàn)結(jié)果對比

Fig.6 Experimental results on Can73 network for K=10圖6 Can73通信網(wǎng)絡(luò)上K=10時(shí)實(shí)驗(yàn)結(jié)果對比