王新棟，于 華，江 成

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

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

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

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

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

本文的主要貢獻如下：

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

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

1 相關(guān)工作

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

(1)

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

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

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

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

2 IP-KPP-POS模型建立

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

基于對KPP-POS的檢測指標DR的優(yōu)化, 建立考慮網(wǎng)絡(luò)內(nèi)部距離加權(quán)的深入優(yōu)化的0-1整數(shù)線性規(guī)劃的關(guān)鍵節(jié)點積極效應模型(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)迫使每個網(wǎng)絡(luò)的其余部分節(jié)點最多只受一個關(guān)鍵節(jié)點影響；約束(5)在資源有限條件下限制網(wǎng)絡(luò)關(guān)鍵節(jié)點的總數(shù)量；約束(6)允許只有當前位置為關(guān)鍵節(jié)點時，點i才能受點j影響。

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

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

3.1 貪婪算法設(shè)計

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

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

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

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

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

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

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

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

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

4 實驗分析

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

4.1 特定E-R 隨機圖

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

表4 特定E-R 隨機圖上的實驗分析Table 4 Experimental analysis on a specific E-R random graph

圖1 特定E-R 隨機圖Fig.1 A specific E-R random graph

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

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

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

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

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

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

從第9行可以看出，當N=70，E=683，K=3時，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ā)式算法的求解時間遠遠優(yōu)于KPP-POS貪婪算法和IP-KPP-POS模型的求解時間，而且IP-KPP-POS模型的優(yōu)化效果明顯優(yōu)于IP-KPP-POS模型的啟發(fā)式算法和KPP-POS貪婪算法。

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

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

為驗證IP-KPP-POS模型在真實網(wǎng)絡(luò)上的性能，本節(jié)在如圖2所示的真實恐怖網(wǎng)絡(luò)數(shù)據(jù)集上進行實驗分析，實驗結(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恐怖分子的開源文獻編制的[22]。 該數(shù)據(jù)集包含與911事件相關(guān)的恐怖主義襲擊事件人員之間的所有聯(lián)系。數(shù)據(jù)集包含63個節(jié)點和154條邊。

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

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

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

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

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

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

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

4.5 實驗結(jié)果

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

5 總結(jié)

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