社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)的積極效應(yīng)問題*

王新棟，于 華，江 成

(1 中國(guó)科學(xué)院大學(xué)工程科學(xué)學(xué)院， 北京 100049； 2 首都經(jīng)濟(jì)貿(mào)易大學(xué)信息學(xué)院， 北京 100070)

隨著科學(xué)技術(shù)的進(jìn)步和社會(huì)物質(zhì)的富足，人類社會(huì)的分工合作趨于精細(xì)化和網(wǎng)絡(luò)化。人們處于各種形形色色的復(fù)雜網(wǎng)絡(luò)中，比如，與生活密切相關(guān)的社會(huì)網(wǎng)絡(luò)[1]和鐵路交通運(yùn)輸網(wǎng)[2]，威脅人類健康的流行病疾病傳播網(wǎng)絡(luò)[3]，以及威脅人類社會(huì)安定的恐怖組織網(wǎng)絡(luò)[4]等等?，F(xiàn)實(shí)網(wǎng)絡(luò)中的節(jié)點(diǎn)地位存在明顯的差異，關(guān)鍵節(jié)點(diǎn)相對(duì)于其他節(jié)點(diǎn)能更大程度地影響網(wǎng)絡(luò)的結(jié)構(gòu)和功能[5-6]。如何正確評(píng)價(jià)個(gè)人在社交網(wǎng)絡(luò)中的地位、分析相互作用影響和關(guān)聯(lián)關(guān)系，以及群體行為的效應(yīng)等問題已經(jīng)成為復(fù)雜網(wǎng)絡(luò)研究中一項(xiàng)具有重要意義的課題。特別地，隨著大數(shù)據(jù)時(shí)代的來(lái)臨，關(guān)鍵節(jié)點(diǎn)的檢測(cè)問題研究已經(jīng)成為研究熱點(diǎn)。其中復(fù)雜網(wǎng)絡(luò)上節(jié)點(diǎn)積極效應(yīng)研究涉及動(dòng)力學(xué)、拓?fù)鋵W(xué)、運(yùn)籌學(xué)等多個(gè)學(xué)科的交叉應(yīng)用，應(yīng)用情景廣泛，如社交網(wǎng)絡(luò)中的謠言傳播[7]、通訊網(wǎng)絡(luò)中的病毒傳播[8]、電力網(wǎng)絡(luò)中的相繼故障[9]，以及經(jīng)濟(jì)網(wǎng)絡(luò)中的危機(jī)擴(kuò)散[10]，等等。

在國(guó)內(nèi)，眾多學(xué)者們從不同的實(shí)際問題出發(fā)設(shè)計(jì)出各種各樣的方法。孫睿和羅萬(wàn)伯[11]對(duì)網(wǎng)絡(luò)輿情中節(jié)點(diǎn)重要性評(píng)估方法的研究現(xiàn)狀進(jìn)行綜述，并從基于節(jié)點(diǎn)屬性和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)兩個(gè)方面，總結(jié)節(jié)點(diǎn)重要性的評(píng)價(jià)模型和方法。Hu等[12]將K殼分解法與社區(qū)結(jié)構(gòu)相結(jié)合，提出一種改進(jìn)指標(biāo)，并在流行病傳染模型領(lǐng)域上實(shí)證分析，驗(yàn)證該方法得到的關(guān)鍵傳染源，相比K殼分解方法得到的傳染源，具有更強(qiáng)的傳播能力。趙之瀅等[13]在復(fù)雜網(wǎng)絡(luò)理論、動(dòng)力系統(tǒng)理論與控制理論結(jié)合的基礎(chǔ)上，開展復(fù)雜動(dòng)態(tài)網(wǎng)絡(luò)同步與控制理論的研究。利用網(wǎng)絡(luò)中節(jié)點(diǎn)所關(guān)聯(lián)的社團(tuán)數(shù)目衡量節(jié)點(diǎn)的傳播能力，提出一種基于網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的節(jié)點(diǎn)影響力度量方法，通過(guò)在Facebook社區(qū)、郵件通訊和博客平臺(tái)等多個(gè)互聯(lián)網(wǎng)領(lǐng)域數(shù)據(jù)集上實(shí)驗(yàn)評(píng)測(cè)，證實(shí)此方法能更有效地檢測(cè)出互聯(lián)網(wǎng)領(lǐng)域內(nèi)信息傳播能力較強(qiáng)的關(guān)鍵人物。

在國(guó)外，多個(gè)領(lǐng)域的學(xué)者對(duì)復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)挖掘的相關(guān)理論基礎(chǔ)進(jìn)行了探索性研究。Borgatti[14]率先提出KPP-POS (key player problem positive)的概念，即尋找一組關(guān)鍵節(jié)點(diǎn)用作信息擴(kuò)散的種子可以最快速讓信息在整個(gè)網(wǎng)絡(luò)中擴(kuò)散。Hussain[15]提出適應(yīng)一般性系統(tǒng)的關(guān)于KPP問題的條件概率和熵度量的統(tǒng)計(jì)方法。為了更有效地找到最佳解決方案，Hamill 等[16]提出基于對(duì)關(guān)鍵節(jié)點(diǎn)選擇的有條件約束的線性規(guī)劃問題。在線性規(guī)劃問題基礎(chǔ)上，McGuire 和Deckro[17]進(jìn)一步擴(kuò)展到加權(quán)WKPP-Pos以便考慮節(jié)點(diǎn)的權(quán)重和邊緣的關(guān)系權(quán)重。Yang[18]通過(guò)考慮網(wǎng)絡(luò)的結(jié)構(gòu)及其節(jié)點(diǎn)和邊緣的屬性，提出一個(gè)廣義的關(guān)鍵節(jié)點(diǎn)問題GKPP (generalized key player problem)。

綜上所述，利用數(shù)學(xué)規(guī)劃的模型和思想研究網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)問題屬于學(xué)術(shù)前沿，相關(guān)理論和方法的研究也鮮有見聞。因此，本文基于網(wǎng)絡(luò)的整體結(jié)構(gòu)，考慮關(guān)鍵節(jié)點(diǎn)對(duì)網(wǎng)絡(luò)積極效應(yīng)的影響，采用數(shù)學(xué)規(guī)劃的方法建立更加精確的模型并設(shè)計(jì)高效的求解算法，通過(guò)對(duì)這部分問題進(jìn)行深入研究，完善關(guān)鍵節(jié)點(diǎn)檢測(cè)理論和方法。

本文的主要貢獻(xiàn)如下：

1)基于對(duì)KPP-POS檢測(cè)指標(biāo)DR的優(yōu)化，建立0-1整數(shù)線性規(guī)劃的關(guān)鍵節(jié)點(diǎn)積極效應(yīng)模型(0-1 integer linear programming key players problem positive effects model, IP-KPP-POS)，用來(lái)解決社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)積極效應(yīng)的問題，并對(duì)該模型進(jìn)行精確求解。

2)設(shè)計(jì)局部搜索啟發(fā)式算法對(duì)IP-KPP-POS模型進(jìn)行求解，以適應(yīng)不同規(guī)模網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)檢測(cè)問題。并通過(guò)在特定隨機(jī)圖、多種類型隨機(jī)網(wǎng)絡(luò)以及真實(shí)標(biāo)準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集上的綜合實(shí)驗(yàn)分析，驗(yàn)證本文所提出的模型在多個(gè)性能指標(biāo)上的明顯優(yōu)勢(shì)。

1 相關(guān)工作

復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的選擇標(biāo)準(zhǔn)是多樣的，有時(shí)需要初始免疫的節(jié)點(diǎn)在傳染病擴(kuò)散時(shí)能最大限度地保護(hù)全體人群，而有時(shí)需要破壞節(jié)點(diǎn)造成最廣泛的連鎖故障等等。因此，找到一個(gè)最佳量化節(jié)點(diǎn)在每種情況下的重要性的通用指標(biāo)是不可能的[19]。Borgatti[14]最早給出社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)消極效應(yīng)和積極效應(yīng)的正式定義，并提出DF指標(biāo)和DR指標(biāo)分別用來(lái)衡量網(wǎng)絡(luò)的離散程度和網(wǎng)絡(luò)的聚合程度。DF和DR指標(biāo)具體表示如下：

(1)

DF指標(biāo)很好地刻畫了網(wǎng)絡(luò)的離散程度，但直接對(duì)DF指標(biāo)進(jìn)行優(yōu)化存在計(jì)算上的不可行性。為解決當(dāng)前所面臨的問題，Arulselvan 等[20]針對(duì)社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)消極效應(yīng)問題建立0-1 整數(shù)線性規(guī)劃模型并設(shè)計(jì)啟發(fā)式算法進(jìn)行求解，取得了較好的實(shí)驗(yàn)效果。然而，該模型只考慮連通分支內(nèi)節(jié)點(diǎn)的個(gè)數(shù)，而忽視了連通分支內(nèi)部的結(jié)構(gòu)，不能有效優(yōu)化連通分支的內(nèi)部結(jié)構(gòu)。為了更好地優(yōu)化連通分支的內(nèi)部結(jié)構(gòu)，Jiang 等[21]對(duì)DF指標(biāo)進(jìn)行近似，綜合考慮剩余網(wǎng)絡(luò)的一步連通性和兩步連通性，開創(chuàng)性地建立 0-1 二次約束二次規(guī)劃模型并設(shè)計(jì)算法進(jìn)行求解，填補(bǔ)了將DF指標(biāo)融入數(shù)學(xué)規(guī)劃模型研究的空白。

然而到目前為止，關(guān)于如何將積極效應(yīng)指標(biāo)DR融入數(shù)學(xué)規(guī)劃的模型中，采用系統(tǒng)的方法檢測(cè)關(guān)鍵節(jié)點(diǎn)研究的更是接近空白。本文在現(xiàn)有研究的基礎(chǔ)上，基于對(duì)KPP-POS檢測(cè)指標(biāo)DR的優(yōu)化，針對(duì)社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)積極效應(yīng)問題，建立0-1整數(shù)線性規(guī)劃的關(guān)鍵節(jié)點(diǎn)積極效應(yīng)模型，并設(shè)計(jì)一種計(jì)算復(fù)雜度較低且精確度較高的局部搜索啟發(fā)式算法對(duì)網(wǎng)絡(luò)的關(guān)鍵節(jié)點(diǎn)進(jìn)行識(shí)別。

本文所研究的社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)積極效應(yīng)問題(KPP-POS)具體是指：給定無(wú)向圖G(V,E)和正整數(shù)K，從節(jié)點(diǎn)集合V中選擇K個(gè)節(jié)點(diǎn)子集合，使其關(guān)聯(lián)節(jié)點(diǎn)的總數(shù)最多，從而達(dá)到最大傳播效應(yīng)的目的。這個(gè)問題的本質(zhì)是計(jì)算一組節(jié)點(diǎn)成員(KP集)與另一組節(jié)點(diǎn)成員(網(wǎng)絡(luò)的其余部分)之間的連接(內(nèi)聚)強(qiáng)度。函數(shù)指標(biāo)DR就很好地描述了集合K的成員與網(wǎng)絡(luò)的剩余部分(V-K)之間的內(nèi)聚程度。

其中，dKj定義為從集合K到剩余部分節(jié)點(diǎn)j的最小距離，分子表示為從KP集合到所有剩余節(jié)點(diǎn)的最小距離的倒數(shù)之和，分母功能是標(biāo)準(zhǔn)化度量指標(biāo)，即DR∈[0,1]。DR可看作是KP集合節(jié)點(diǎn)達(dá)到其余所有節(jié)點(diǎn)的加權(quán)比例，并且到達(dá)其他節(jié)點(diǎn)的權(quán)值和它們最小距離成反比。當(dāng)且僅當(dāng)距離為1時(shí)，節(jié)點(diǎn)被賦予最大權(quán)值1。因此，當(dāng)每個(gè)外部節(jié)點(diǎn)與KP集合的至少一個(gè)成員相鄰(即KP集合是支配集合)時(shí)，DR取最大值1。當(dāng)KP集合的任何成員都不與外部節(jié)點(diǎn)集的成員相鄰，即KP集完全離散時(shí)，得到最小值0。

2 IP-KPP-POS模型建立

公式(1)給出衡量網(wǎng)絡(luò)聚合程度的指標(biāo)DR，雖然DR考慮了距離加權(quán)，但是DR指標(biāo)包含最短路徑dKj的求解，直接把DR作為目標(biāo)進(jìn)行優(yōu)化復(fù)雜度高，求解困難。另外，對(duì)于一步可達(dá)路徑dij=1,1/dij=1；對(duì)于兩步可達(dá)路徑dij=2,1/dij=1/2；dij≥3,1/dij相應(yīng)減少為1/3， 1/4,…,0。在資源有限或成本約束條件下，可以假設(shè)兩步和兩步以上可達(dá)路徑在實(shí)際中是不連通的，在此假設(shè)條件下，對(duì)DR的優(yōu)化就簡(jiǎn)化為對(duì)一步可達(dá)路徑節(jié)點(diǎn)對(duì)的連通性能最大化優(yōu)化問題。

基于對(duì)KPP-POS的檢測(cè)指標(biāo)DR的優(yōu)化, 建立考慮網(wǎng)絡(luò)內(nèi)部距離加權(quán)的深入優(yōu)化的0-1整數(shù)線性規(guī)劃的關(guān)鍵節(jié)點(diǎn)積極效應(yīng)模型(0-1 Integer linear programming key players problem positive effects model, IP-KPP-POS)，具體模型表示如下。

SKPP-POS={n|yn=1}.

(2)

(3)

(4)

(5)

xij≤yj,?i,j∈V.

(6)

xij,yj∈{0,1},?i,j∈V.

(7)

aij∈{0,1},?i,j∈V.

(8)

模型變量解釋如表1所示。

表1 模型變量解釋Table 1 Explanations of model variables

約束(4)迫使每個(gè)網(wǎng)絡(luò)的其余部分節(jié)點(diǎn)最多只受一個(gè)關(guān)鍵節(jié)點(diǎn)影響；約束(5)在資源有限條件下限制網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的總數(shù)量；約束(6)允許只有當(dāng)前位置為關(guān)鍵節(jié)點(diǎn)時(shí)，點(diǎn)i才能受點(diǎn)j影響。

為快速求解，本文采用MATLAB中內(nèi)置的Integer Linear Programming算法包對(duì)IP-KPP-POS模型求解；已有文章證明，網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)問題是NP-complete的[20]。因此，為適應(yīng)大規(guī)模網(wǎng)絡(luò)的求解，本文在第3節(jié)中設(shè)計(jì)啟發(fā)式算法進(jìn)行求解。

3 啟發(fā)式算法設(shè)計(jì)

3.1 貪婪算法設(shè)計(jì)

最近，已有學(xué)者提出針對(duì)社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)積極效應(yīng)問題求解的KPP-POS貪婪算法，并通過(guò)實(shí)驗(yàn)證實(shí)了該算法的有效性[14]。KPP-POS貪婪算法如表2所示。

表2 關(guān)鍵節(jié)點(diǎn)檢測(cè)的貪婪算法Table 2 Greedy algorithm for key players detection

這個(gè)算法首先隨機(jī)選擇k個(gè)節(jié)點(diǎn)作為關(guān)鍵節(jié)點(diǎn)填充集合S，然后設(shè)置合適的初始目標(biāo)值。隨后對(duì)集合S中的每個(gè)節(jié)點(diǎn)u和每個(gè)不在集合S中的節(jié)點(diǎn)v進(jìn)行交換，如果目標(biāo)值得到改善，那就進(jìn)行交換并更新目標(biāo)值，反之取消交換，直到目標(biāo)值不再得到優(yōu)化時(shí)程序終止。

由于此貪婪算法選取起始關(guān)鍵節(jié)點(diǎn)集采用隨機(jī)的方式，所以運(yùn)行結(jié)果容易陷入局部最優(yōu)解。為有效地解決該問題，通常使用數(shù)十個(gè)隨機(jī)起始集重復(fù)實(shí)驗(yàn)，最終選取實(shí)驗(yàn)結(jié)果最好的目標(biāo)值對(duì)應(yīng)的關(guān)鍵節(jié)點(diǎn)集S，但同時(shí)也增加整個(gè)求解過(guò)程的運(yùn)行時(shí)間，即減緩全局收斂速度。

3.2 貪婪結(jié)合局部搜索的啟發(fā)式算法

為了能夠求解較大規(guī)模社交網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)積極效應(yīng)問題，本文在貪婪框架內(nèi)結(jié)合局部搜索方法，設(shè)計(jì)了一個(gè)啟發(fā)式算法。如表3所示。

這個(gè)算法首先選擇能夠使得目標(biāo)值最優(yōu)的第一個(gè)節(jié)點(diǎn)，即所有節(jié)點(diǎn)中度最大的一個(gè)節(jié)點(diǎn)。然后在刪除已選擇的關(guān)鍵節(jié)點(diǎn)的剩余網(wǎng)絡(luò)中，加入可以使目標(biāo)值最優(yōu)的下一個(gè)節(jié)點(diǎn)，通過(guò)局部搜索方法，每次從已選擇作為關(guān)鍵節(jié)點(diǎn)的集合中取出一個(gè)節(jié)點(diǎn)，與剩余網(wǎng)絡(luò)中的一個(gè)節(jié)點(diǎn)置換，如果可以增加目標(biāo)值(目標(biāo)值為max)，那么進(jìn)行置換；反之，取消置換。同理，按照該方法對(duì)集合中的其他節(jié)點(diǎn)做置換嘗試，直至選擇的關(guān)鍵節(jié)點(diǎn)個(gè)數(shù)達(dá)到預(yù)先設(shè)定的K值。

表3 關(guān)鍵節(jié)點(diǎn)檢測(cè)的啟發(fā)式算法Table 3 Heuristic algorithm for key players detection

該啟發(fā)式算法起始集選擇使得目標(biāo)值最優(yōu)的節(jié)點(diǎn)，這種起始集的選擇減少了得到局部最優(yōu)解的可能并且加快了全局收斂速度。顯而易見，該啟發(fā)式算法的主要消耗在局部搜索增強(qiáng)操作上，復(fù)雜度為O(N)。

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

本章節(jié)將通過(guò)在特定隨機(jī)圖，多種類型隨機(jī)網(wǎng)絡(luò)和真實(shí)標(biāo)準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集上同KPP-POS貪婪算法綜合實(shí)驗(yàn)對(duì)比分析，對(duì)提出的IP-KPP-POS模型、IP-KPP-POS 啟發(fā)式算法進(jìn)行驗(yàn)證。其中，IP-KPP-POS模型、IP-KPP-POS啟發(fā)式算法都是使用MATLAB語(yǔ)言編程開發(fā)的，所有的模型和算法均在配置為Windows操作系統(tǒng)的臺(tái)式機(jī)電腦平臺(tái)上運(yùn)行。平臺(tái)的具體配置為：主頻2.6 GHz 的驍龍 CPU；32 G 的內(nèi)存。

4.1 特定E-R 隨機(jī)圖

如圖1所示，本文在節(jié)點(diǎn)規(guī)模為15，邊規(guī)模為41，連接密度為30%的ER隨機(jī)生成圖上進(jìn)行闡述。以DR指標(biāo)作為網(wǎng)絡(luò)積極效應(yīng)的評(píng)測(cè)標(biāo)準(zhǔn)，根據(jù)前文對(duì)DR的定義，當(dāng)DR值越大，說(shuō)明選擇的一組節(jié)點(diǎn)(KP集)的成員與另一個(gè)節(jié)點(diǎn)(網(wǎng)絡(luò)的其余部分)的成員之間的連接或內(nèi)聚越強(qiáng)，即更具有重要性；反之亦然。實(shí)驗(yàn)結(jié)果如表4所示。

表4 特定E-R 隨機(jī)圖上的實(shí)驗(yàn)分析Table 4 Experimental analysis on a specific E-R random graph

圖1 特定E-R 隨機(jī)圖Fig.1 A specific E-R random graph

表4中，前兩列分別表示實(shí)驗(yàn)中網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和邊數(shù)，第3列表示關(guān)鍵節(jié)點(diǎn)的個(gè)數(shù)K值；Obj表示對(duì)應(yīng)方法求解所得到的目標(biāo)值，KP集表示求解得到的關(guān)鍵節(jié)點(diǎn)集，T表示方法求解時(shí)間，單位為ms；而DR表示衡量網(wǎng)絡(luò)凝聚程度的優(yōu)化效果指標(biāo)。上標(biāo)“*”表示針對(duì)同一網(wǎng)絡(luò)優(yōu)化效果更好的一方。

當(dāng)K值分別取1、2和3，即網(wǎng)絡(luò)中作為關(guān)鍵節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)目分別為 1、2和3 時(shí)，3種方法的DR值都相同。這意味著在關(guān)鍵節(jié)點(diǎn)數(shù)目分別為1、2和3時(shí)，IP-KPP-POS模型和IP-KPP-POS啟發(fā)式算法跟KPP-POS貪婪算法在網(wǎng)絡(luò)積極效應(yīng)優(yōu)化效果一致，但I(xiàn)P-KPP-POS啟發(fā)式算法的運(yùn)行時(shí)間要明顯優(yōu)于IP-KPP-POS模型和KPP-POS貪婪算法。

4.2 多種類型隨機(jī)網(wǎng)絡(luò)

為測(cè)試不同K值下，IP-KPP-POS模型和IP-KPP-POS啟發(fā)式算法的性能，針對(duì)節(jié)點(diǎn)數(shù)為20、50、70、120，邊數(shù)分別為56、383、683、1 538，連接密度為30%的隨機(jī)網(wǎng)絡(luò)圖，同KPP-POS貪婪算法進(jìn)行實(shí)驗(yàn)對(duì)比分析，實(shí)驗(yàn)結(jié)果如表5所示。

表5 多種類型隨機(jī)網(wǎng)絡(luò)上的實(shí)驗(yàn)分析Table 5 Experimental analysis on various types of random networks

表5中，前兩列分別表示實(shí)驗(yàn)中網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)和邊數(shù)，第3列表示關(guān)鍵節(jié)點(diǎn)的個(gè)數(shù)K值；Obj表示對(duì)應(yīng)方法求解所得到的目標(biāo)值，T表示方法求解時(shí)間，單位為ms；而DR表示衡量網(wǎng)絡(luò)凝聚程度的優(yōu)化效果指標(biāo)。上標(biāo)“*”表示針對(duì)同一網(wǎng)絡(luò)優(yōu)化效果更好的一方。例如，第1行至第3行表示對(duì)于一個(gè)節(jié)點(diǎn)數(shù)為20，邊數(shù)為56的網(wǎng)絡(luò)圖，當(dāng)K值分別為 1、2、 3 時(shí)，IP-KPP-POS模型、IP-KPP-POS模型啟發(fā)式算法和KPP-POS貪婪算法的優(yōu)化效果對(duì)比分析。

從第9行可以看出，當(dāng)N=70，E=683，K=3時(shí)，IP-KPP-POS模型、IP-KPP-POS模型的啟發(fā)式算法和KPP-POS貪婪算法的最優(yōu)值為分別為57、55和55，網(wǎng)絡(luò)的DR值分別為0.925 4、0.910 4和0.910 4，IP-KPP-POS模型的啟發(fā)式算法優(yōu)化效果和KPP-POS貪婪算法相同，但是IP-KPP-POS模型的啟發(fā)式算法的求解時(shí)間遠(yuǎn)遠(yuǎn)優(yōu)于KPP-POS貪婪算法和IP-KPP-POS模型的求解時(shí)間，而且IP-KPP-POS模型的優(yōu)化效果明顯優(yōu)于IP-KPP-POS模型的啟發(fā)式算法和KPP-POS貪婪算法。

從整體的對(duì)比實(shí)驗(yàn)結(jié)果來(lái)看，雖然IP-KPP-POS模型的求解時(shí)間要比KPP-POS貪婪算法的求解時(shí)間長(zhǎng)，但是IP-KPP-POS模型的求解精度要比KPP-POS貪婪算法更高；同時(shí)在同樣的優(yōu)化效果下， IP-KPP-POS模型的啟發(fā)式算法的求解時(shí)間遠(yuǎn)遠(yuǎn)優(yōu)于KPP-POS貪婪算法和對(duì)應(yīng)的IP-KPP-POS模型的求解時(shí)間。此外，IP-KPP-POS模型的啟發(fā)式算法和IP-KPP-POS模型求解的結(jié)果大部分一致，這也證實(shí)了啟發(fā)式算法的正確性。

4.3 真實(shí)恐怖網(wǎng)絡(luò)數(shù)據(jù)集

為驗(yàn)證IP-KPP-POS模型在真實(shí)網(wǎng)絡(luò)上的性能，本節(jié)在如圖2所示的真實(shí)恐怖網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)分析，實(shí)驗(yàn)結(jié)果如表6所示。

圖2 “9.11”恐怖網(wǎng)絡(luò)數(shù)據(jù)集Fig.2 “9.11” terrorist network dataset

Krebs的911劫持者數(shù)據(jù)集：以下數(shù)據(jù)集是由Krebs使用關(guān)于9/11恐怖分子的開源文獻(xiàn)編制的[22]。 該數(shù)據(jù)集包含與911事件相關(guān)的恐怖主義襲擊事件人員之間的所有聯(lián)系。數(shù)據(jù)集包含63個(gè)節(jié)點(diǎn)和154條邊。

當(dāng)K值取3，也就是網(wǎng)絡(luò)中作為關(guān)鍵節(jié)點(diǎn)的節(jié)點(diǎn)數(shù)目為 3 時(shí)， Borgatti的Key Player Set模型[14]和McGuire的WKPP-Pos模型[17]選擇的節(jié)點(diǎn)集都是5、34和46，DR值為0.788 9；而本文所建立的IP-KPP-POS模型選擇的是節(jié)點(diǎn)集是20、34和56，DR值為0.811 1，優(yōu)化效果明顯好于0.788 9。通過(guò)比較可以看出，本文建立的IP-KPP-POS模型在真實(shí)恐怖網(wǎng)絡(luò)數(shù)據(jù)集上網(wǎng)絡(luò)積極效應(yīng)優(yōu)化效果相比其他方法明顯占優(yōu)。

表6 真實(shí)恐怖網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)比較Table 6 Comparison on a real terror network dataset

4.4 Facebook數(shù)據(jù)集

由于IP-KPP-POS模型的算法復(fù)雜度較高，求解算法又受到MATLAB的內(nèi)置約束限制，目前在現(xiàn)有平臺(tái)只能求解節(jié)點(diǎn)規(guī)模小于100的網(wǎng)絡(luò)。為驗(yàn)證在大規(guī)模網(wǎng)絡(luò)上的性能，本章節(jié)在開源評(píng)測(cè)數(shù)據(jù)集網(wǎng)絡(luò)“Facebook數(shù)據(jù)集”[23]上對(duì)比IP-KPP-POS啟發(fā)式算法和KPP-POS貪婪算法，該數(shù)據(jù)集包含347個(gè)節(jié)點(diǎn)和5 038條邊。實(shí)驗(yàn)結(jié)果如表7所示。

表7 Facebook數(shù)據(jù)集上的實(shí)驗(yàn)比較Table 7 Comparisons on the Facebook dataset

從表7可以看出，當(dāng)網(wǎng)絡(luò)規(guī)模增加到347時(shí)，IP-KPP-POS啟發(fā)式算法的平均運(yùn)行時(shí)間為2.3e2，而KPP-POS貪婪算法的平均運(yùn)行時(shí)間為2.2e3，KPP-POS貪婪算法大約是IP-KPP-POS啟發(fā)式算法平均運(yùn)行時(shí)間的10倍。從DR的結(jié)果對(duì)比來(lái)看，IP-KPP-POS啟發(fā)式算法所選擇的關(guān)鍵節(jié)點(diǎn)集，優(yōu)于KPP-POS貪婪算法所選擇的關(guān)鍵節(jié)點(diǎn)集。

對(duì)于更大規(guī)模的網(wǎng)絡(luò)，論文同樣進(jìn)行了實(shí)驗(yàn)分析。由于 KPP-POS貪婪算法的復(fù)雜度遠(yuǎn)高于IP-KPP-POS啟發(fā)式算法的復(fù)雜度。隨著網(wǎng)絡(luò)規(guī)模的增加， KPP-POS貪婪算法的計(jì)算運(yùn)行時(shí)間大幅增加。當(dāng)網(wǎng)絡(luò)規(guī)模為 958 時(shí)，IP-KPP-POS啟發(fā)式算法運(yùn)行時(shí)間平均為1.7e5，而 KPP-POS貪婪算法的運(yùn)算時(shí)間平均為 2.0e6。因此，在現(xiàn)有的計(jì)算資源有限的平臺(tái)約束下，因缺少對(duì)照實(shí)驗(yàn)數(shù)據(jù)，很難進(jìn)行更大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)集的驗(yàn)證評(píng)測(cè)。在未來(lái)研究中，可以增加計(jì)算資源，在更大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)對(duì)照分析。

4.5 實(shí)驗(yàn)結(jié)果

為了評(píng)測(cè)IP-KPP-POS模型以及IP-KPP-POS啟發(fā)式算法的有效性和正確性，同KPP-POS貪婪算法在特定E-R 隨機(jī)圖，多種類型隨機(jī)網(wǎng)絡(luò)以及真實(shí)標(biāo)準(zhǔn)網(wǎng)絡(luò)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)。實(shí)驗(yàn)表明，本文所提出的模型方法在多個(gè)性能指標(biāo)上具有明顯優(yōu)勢(shì)。特別地，在小數(shù)據(jù)集上，IP-KPP-POS模型以及IP-KPP-POS啟發(fā)式算法在網(wǎng)絡(luò)積極效應(yīng)優(yōu)化方面同樣出色；但隨著數(shù)據(jù)規(guī)模的擴(kuò)大，IP-KPP-POS模型檢測(cè)到的關(guān)鍵節(jié)點(diǎn)在網(wǎng)絡(luò)積極效應(yīng)優(yōu)化精確度上比IP-KPP-POS啟發(fā)式算法和KPP-POS貪婪算法的精確度更高一些，但是IP-KPP-POS啟發(fā)式算法的求解時(shí)間要明顯優(yōu)于IP-KPP-POS模型和KPP-POS貪婪算法的求解時(shí)間。

5 總結(jié)

在本文中，我們提出一種新的方法IP-KPP-POS解決復(fù)雜網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)檢測(cè)積極效應(yīng)問題。由于問題的NP難特性，又對(duì)該模型的求解算法深入研究。一方面，利用0-1整數(shù)線性規(guī)劃方法對(duì)模型求解，滿足小規(guī)模網(wǎng)絡(luò)的快速精確求解；另一方面，設(shè)計(jì)貪婪局部搜索的啟發(fā)式算法，滿足大規(guī)模網(wǎng)絡(luò)的節(jié)點(diǎn)檢測(cè)。通過(guò)在E-R隨機(jī)網(wǎng)絡(luò)、多種類型隨機(jī)圖、真實(shí)恐怖網(wǎng)絡(luò)、Facebook數(shù)據(jù)集等多種數(shù)據(jù)集上同KPP-POS貪婪算法進(jìn)行對(duì)比實(shí)驗(yàn)，驗(yàn)證模型的正確性和有效性。實(shí)驗(yàn)結(jié)果表明，本文提出的IP-POS-CNP模型，在準(zhǔn)確性能上明顯高于傳統(tǒng)的KPP-POS方法，并且所設(shè)計(jì)的對(duì)應(yīng)的啟發(fā)式算法在求解速度上具有顯著優(yōu)勢(shì)，更加適合大規(guī)模網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的快速檢測(cè)。本文的研究成果可為各領(lǐng)域的關(guān)鍵節(jié)點(diǎn)相關(guān)問題提供決策支持。在未來(lái)的研究中，本文將對(duì)有向有權(quán)圖中關(guān)鍵節(jié)點(diǎn)的挖掘進(jìn)一步探索研究。