基于鄰域K-shell分布的關鍵節點識別方法

吳亞麗，任遠光，董昂，周傲然，吳學金，鄭帥龍

1.西安理工大學 自動化與信息工程學院，西安 710048

2.陜西省復雜系統控制與智能信息處理重點實驗室，西安 710048

現實生活中的許多復雜系統如電力網絡、交通網絡、疾病網絡、社交網絡和生物網絡等均可以抽象為復雜網絡，其中存在著一些重要的節點對于網絡的結構功能、結構特性以及信息流通起主導作用[1]。例如，電力網絡[2]中，保護樞紐節點可以避免發生級聯故障[3]，從而預防大規模停電事故；交通網絡[4-5]中，關鍵節點的癱瘓或失效都會對整個交通網絡的連通性、通行效率和運力分配產生重大影響，引發交通擁堵和經濟損失等問題；疾病網絡[6-7]中，通過追蹤和管理關鍵人員，可以有效地阻止疾病擴散。因此，準確和高效地識別復雜網絡中具有影響力的節點一直是復雜網絡研究的熱點問題。

目前國內外學者提出了許多識別復雜網絡關鍵節點的方法，如度中心性（degree centrality，DC）[8]，特征向量中心性（eigenvector centrality，EC）[9]，介數中心性（betweenness centrality，BC）[10]和接近中心性（closeness centrality，CC）[11]；度中心性認為節點的重要性取決于其鄰居節點的數量，計算復雜度低，適用于大規模網絡，然而忽視了節點鄰域的拓撲信息，準確性通常較低；特征向量中心性基于隨機游走的思想，考慮了節點的度及其鄰居節點包含的信息；介數中心性和接近中心性是兩種基于網絡全局特性的方法，但隨著網絡規模的爆發式增長，這兩種方法的計算復雜度往往較高，并且難以處理網絡中的一些孤立節點。

Kitsak 等人[12]于2013 年提出的K 殼分解法（K-shell decomposition，K-shell）根據節點在網絡中的位置對所有節點的重要性進行分層，并且認為越接近網絡核心位置的節點重要性越高。在大規模網絡得到了廣泛使用，但其不足之處在于無法區分處于相同殼層節點的重要性。為解決這一問題，研究人員在K-shell 方法的基礎上又提出了一些改進的方法。Zeng 等人[13]提出混合度分解方法（mixed degree decomposition，MDD），該方法考慮已移除節點對于指定節點的影響，通過耗盡度和剩余度對節點的重要性進行評估；Bae 和Kim[14]在2016 年提出了鄰域核心中心度方法（the coreness centrality，Cnc+），該方法通過對鄰居節點的Ks值求和來評估節點的重要性；Wang 等人[15]考慮了K-shell 分解中產生的迭代信息，提出了一種K-shell迭代因子方法（the K-shell iteration factor，KS_IF）；朱曉霞等人[16]在K-shell方法的基礎上，考慮到邊和鄰居節點的差異貢獻性對節點重要性的影響，提出加權度方法（modified K-shell，MKS）；Qiu等人[17]提出一種基于全局和局部影響的關鍵節點識別方法（the local influence and global influence，LGI），根據節點的度、聚類系數和位置信息對節點的重要性進行排序；Lai等人[18]綜合考慮節點度、鄰域節點度以及K-shell信息，提出加權K-shell 度鄰域識別方法（the weighted k-shell degree neighborhood identification method，KSD）。上述方法雖然對于關鍵節點識別的準確性得到提升，然而對節點鄰居Ks值累加的形式不能充分考慮鄰域信息對于節點重要性的貢獻，影響關鍵節點識別能力。

為了更充分地利用節點鄰域的信息，本文提出了一種基于節點鄰域K-shell 分布的關鍵節點識別方法（Kshell distribution of neighbours，KDN）。該方法通過節點鄰域的Ks值定義節點的熵，來反映鄰居節點的Kshell 分布特征，認為節點的鄰居節點越多，鄰居節點的Ks值越大且分布越均勻（更多的鄰居節點處于網絡核心），則該節點重要性越高。為了驗證所提方法的有效性，本文基于易感-感染-恢復模型（susceptible-infectedrecovered，SIR）[19-22]，在11 個真實網絡數據集上進行了仿真和驗證，并與部分現有關鍵節點識別方法對比分析，實驗結果表明本文所提出KDN方法的優越性。

1 理論基礎

1.1 K-shell方法

K-shell方法主要利用節點的位置信息，根據網絡中節點所處位置（處于網絡核心或邊緣），劃分不同殼值來評價節點重要性，該方法步驟如下：

首先，去除掉網絡中度為1 的節點及其連邊，然后迭代至整個網絡中不存在度為1的節點，將此次去除的節點歸為1-shell 層，并分配Ks值為1。重復執行該過程，可以得到2-shell、3-shell等層，最終將網絡中所有節點劃分為不同的層，每個節點都相應地分配了Ks值。其中Ks值最大的節點所在的層即為核心層，而核心層節點的影響力大于非核心層節點。

圖1 所示為一個小型網絡的K-shell 分解示例圖。K-shell方法將網絡分成了3層，節點1，2，3，4的Ks值為3，節點5，6，7，8 的Ks值為2，節點9，10，11，12，13，14，15的Ks值為1，K-shell方法將擁有相同Ks值的節點視為具有相同的重要性。

圖1 K-shell分解示例圖Fig.1 Example diagram of K-shell decomposition

1.2 混合度分解

在混合度分解方法中，用耗盡度來衡量已去除節點對于指定節點的影響。這種采用混合Ks值的改進方法，既增加了網絡分層的層數，又提高了關鍵節點識別的準確性，該方法可以表示為：

其中，λ是一個可調參數，λ∈[0,1]。當λ=0 時，MDD方法與K-shell 方法相同。當λ=1 時，MDD 方法與DC方法一致，Km(i)為混合Ks值，Kr(i)為剩余度，Ke(i)為耗盡度。

2 研究方法

K-shell方法是識別復雜網絡關鍵節點的方法之一，但該方法只考慮節點的位置信息，忽視了節點鄰域的拓撲信息，無法準確評估網絡中節點的傳播能力。考慮鄰居節點的Ks值可以提高對于節點重要性的識別能力，具有高Ks值鄰居節點的節點更加關鍵[16]。

如圖2 的小型網絡圖，節點1 和節點2 度值相同和Ks值相同（度為5，Ks值為2），且鄰居節點的Ks之和相等，但是節點1的傳播能力（spreading capability，SC）卻明顯優于節點2，SC1>SC2。節點1的和節點2的鄰居Ks值分布分別為[2，2，2，2，2]和[3，2，2，1，2]。在這種情況下，可以合理假設，如果節點具有更多的鄰居節點且鄰居節點的Ks值既高又均勻，則該節點的傳播能力更強，重要性也更高。

圖2 示例網絡Fig.2 Schematic network

信息熵[23]是用來衡量信息不確定性或信息量的量化指標，信息量越多，熵值越大，反之則越小。在離散的事件集合中，信息熵與事件發生的概率分布、可能事件的數量之間存在密切關系。為了更充分地利用節點的信息，本文以信息熵作為載體，通過節點全局信息Ks值定義概率分布pi，計算得到節點vi的鄰域Ks熵。熵值的大小可以反映節點的鄰居節點數量和鄰域節點位置分布的均勻性。鄰居節點越多，熵值越大；鄰域Ks值分布越均勻，熵值也會變大。

2.1 信息熵

美國學者香農于1948年提出了信息熵（information entropy）[23]的概念。熵值的大小可以反映事件包含信息量的多少，X表示可能事件x1,x2,…,xn的集合，pi表示事件xi的概率。X的信息熵可由式（2）計算：

一方面，X分布更均勻，熵值更大。另一方面，n不斷增加，熵值也會隨之增大。

2.2 基于鄰域K-shell分布的復雜網絡關鍵節點識別方法

如果一個節點有更多的鄰居節點位于網絡的核心位置，即擁有較高的Ks值，并且鄰居節點Ks值的分布更加均勻，則該節點在網絡中傳播能力更強，同時具有更高的重要性。節點vi的Ks值用Ks(vi)表示，Ni表示節點vi的鄰居節點集合，節點vi鄰居節點的Ks值之和用Ks'(vi)來表示，計算公式為：

通過式（4）計算得到節點vi的鄰域Ks熵E(vi)：

節點vi的影響能力（influence ability，IA）為其鄰居節點的熵E(vi)之和：

最終，節點的KDN(vi)值計算公式如式（6）所示：

節點vi的KDN值越大，說明節點的重要性越高。

3 實驗分析和結果

3.1 實驗數據集

本文使用示例網絡和不同類型的真實網絡進行實驗和仿真，其中10 個真實網絡由網絡數據庫（https：//networkrepository.com/index.php）提供。

11 個網絡分別為：（1）Schematic 網絡；（2）Karate網 絡；（3）Dolphins 網絡；（4）Train 網絡；（5）Jazz 網絡；（6）USAir97 網絡；（7）Netscience 網絡；（8）Email 網絡；（9）Euroroad網絡；（10）Hamsterster網絡；（11）PowerGrid網絡。11 個網絡的信息如表1 所示，其中N表示網絡的節點數量，E表示網絡的邊數，表示網絡的平均度，表示網絡的最短平均距離，c表示網絡的集聚系數，Ksmax表示利用K-shell方法對網絡進行分解之后網絡核心層的核值，βth表示網絡的流行閾值。

表1 11個網絡的統計特性Table 1 Statistical characteristics of 11 complex networks

3.2 區分度評價

為了評估不同方法對節點重要性的區分能力，使用DM（distinct metric）[24]指標進行檢驗。當DM=1，表示所有節點具有不同的重要性。DM 值越接近1，說明對節點重要性的區分能力越強。通過式（7）計算DM值：

表2 總結了不同方法在11 個復雜網絡上的DM值。KDN 方法在7個網絡中DM值是最高的，在Karate網絡和Hamsterster網絡中，KDN方法與LGI方法接近，在Euroroad 網絡和Powergrid 網絡中DM 值較低，原因是在Euroroad 網絡和Powergrid 網絡節點數量眾多，但其最大Ks值分別為2和5，表明在K-shell分解中有很多節點被分在相同的層級，這間接導致KDN 方法在這兩個網絡中的區分能力并不高。圖3為不同方法top節點的DM 值變化曲線，其中在Dolphins 網絡、USAir97 網絡和Email 網絡中，KDN 方法對前10%、前20%、…所有節點重要性的區分能力上有著明顯的優勢，僅在Netscience 網絡中對少部分top 節點重要性的區分能力低于BC方法。

表2 不同方法在11個網絡中的DM值Table 2 DM values of different methods on 11 complex networks

圖3 不同方法top節點的DM值變化曲線Fig.3 DM values curve of top nodes with different methods

除DM 指標以外，使用單調性函數（monotonicity function，M）[14]來對不同關鍵節點識別方法的區分度進行分析，M指標的計算如式（8）所示：

其中，R表示需要排序的數據向量，n表示R中不同等級的數目，nr表示相同等級節點的個數，如果所有節點的重要性都被分配在同一等級上，那么M=0；如果所有節點的重要性都被分配到不同的等級上，則M=1。

表3 為不同方法在11 個網絡上的M 值，KDN 方法在7個網絡中的M值最高，在其他4個網絡中KDN方法的M值和最高的M值接近。圖4為不同方法top節點的M 值變化曲線圖，從圖中可以看出KDN 方法不僅對于少部分關鍵節點重要性的區分效果顯著，對所有節點重要性的區分能力也有著明顯的優勢。綜上所述，KDN方法對于節點重要性的區分能力較好。

表3 不同方法在11個網絡 中的M值Table 3 M values obtained by different methods on 11 complex networks

圖4 不同方法top節點的M值變化曲線Fig.4 M values curve of top nodes with different methods

此外，為了更直觀地展示不同方法的區分能力。圖5顯示了不同方法在Train網絡、USAir97網絡、Netscience網絡和Email網絡中節點等級數量以及每個等級占據節點數的頻率分布。KDN 方法在4 個網絡中提供的排名包含更多等級，而每個等級所涵蓋的節點數量又低于其他方法，這表明KDN方法可以更好地區分節點的重要性。

圖5 同方法的等級頻次分布圖Fig.5 Graded frequency distribution offered by different methods

3.3 關鍵節點識別準確性實驗

關鍵節點識別的準確性直接反映方法的性能，是最重要的指標之一。為了驗證KDN方法對節點重要性識別的準確性，本實驗將每個方法得到的節點重要性排序結果與經過SIR模擬得到的排序結果進行比較，并計算對應的Kendall系數值[25-26]。

（1）SIR感染模型

在SIR 模型中[19-22]，網絡中的每個節點可能處于三種不同的狀態：易感狀態（susceptible state），即健康狀態，該狀態節點有一定概率被疾病傳播所感染；感染狀態（infected state），處于該狀態的節點具有感染能力，可以感染易感態節點；恢復狀態（recovered state），該狀態表示感染狀態節點已經從感染狀態下恢復，不再具有感染能力。

在SIR傳播模型初期，網絡中僅有一個節點處于感染狀態，其余節點均處于易感狀態。在每個時間步長中，感染節點以一定的感染概率β對其周圍鄰居節點進行感染，使其進入感染狀態，隨后該節點會轉變為恢復狀態，而處于恢復狀態的節點則不再被感染。該過程一直持續，直到網絡中不存在任何處于感染狀態的節點。在SIR過程結束后，將處于恢復狀態的節點數量視為節點的傳播能力，并通過重復此過程計算每個節點的傳播能力，從大到小排序后得出SIR 排序列表。在SIR 傳播過程中，β的取值和網絡的傳播閾值βth有關，當β大于βth，疾病可以在網絡中大范圍傳播；當β較小，疾病只能在小范圍內傳播[27]，流行閾值βth的計算公式如下：

（2）準確性評價

在SIR 過程中，當 |E|<100 時，將SIR 過程重復進行10 000次；當100<|E|<10 000，將SIR過程重復執行1 000 次；當 |E|>10 000 時，將SIR 過程重復進行100次[27]。將SIR排序結果與其他排序方法的結果做比較，計算得到Kendall 系數值來度量它們之間的相關性。Kendall 系數越大，說明與SIR 排序結果相關性越高，即方法的識別結果具有更高的準確性。Kendall相關系數τ的定義如下：

其中，X和Y分別表示兩個排序列表，nc表示排序列表中一致對的數目，nd表示排序列表中非一致對的數目，n為排序列表中包含的元素數。

表4為不同方法與SIR模擬結果對比得到的Kendall系數值，表中β為網絡的感染率。在11個網絡中，KDN方法的Kendall 系數值在所有方法中均最高，識別結果具有更高的準確性。

表4 不同方法的排序列表和SIR排序列表的Kendall系數值Table 4 Kendall coefficient values of ranking lists of different methods and SIR ranking lists

在接下來的實驗中，通過改變感染率β，在Karate網絡、Dolphins 網絡、Netscience 網絡和Euroroad 網絡中進行SIR 模擬，以驗證KDN 方法識別關鍵節點的準確性，通過使用Kendall 系數值比較不同方法與不同感染率下SIR的排序結果。圖6為不同方法得到的排序結果與不同感染率下SIR排序結果之間的Kendall系數變化情況，βth在圖中用虛線進行表示。在βth附近，KDN方法在四個網絡中的Kendall 系數值均高于其他方法，因此KDN方法對于關鍵節點的識別具有較高的準確性。

圖6 不同 方法排序結果與SIR排序結果的Kendall變化曲線Fig6 Cauve of viaion of Kendall coefficient between ranking results obtained by different methods and SIR ranking results

Kendall相關系數實驗考慮了網絡中所有節點的排名。然而，關鍵節點通常關注小部分數量節點，因此在接下來的實驗中，使用排序相似函數（ranking similarity function，F(L)）[28]來評估KDN 方法對于前r位節點排名的準確性。排序相似函數通過式（11）進行計算：

其中，L(r)和L'(r)表示在各自排序列表中的前r個節點。

如圖7 所示，KDN 方法在USAir97 網絡、Email 網絡、Euroroad網絡和Hamsterster網絡中始終保持較高的排序相似函數值，證明該方法對于前r個節點的排序列表具有較高的精確度，進一步說明KDN 方法識別關鍵節點的準確性優于其他方法。

圖7 前r個節點的排序相似函數變化曲線Fig.7 Curve of variation of ranking similarity function on top rnodes

3.4 時間性能

為了評價KDN 方法的時間性能，本文對不同方法在不同網絡中的運行時間進行了比較。計算機配置為Intel Core i5-8250U@1.80 GHz、8 GB RAM，64 位Windows10 系統，在此電腦上運行了Python 3.10 環境下的實驗程序。

在不同網絡上進行100 次重復實驗并計算平均時間得出運行時間，結果如表5 所示。DC 方法僅考慮節點鄰居節點的數目，雖然運行時間很短，但識別的準確性和區分度較低，因此不關注該方法的時間性能。Kshell方法原理簡單，計算復雜度僅為O(n)，但不能區分同層節點的重要性。除K-shell方法與Cnc+方法，KDN方法在不同網絡上的運行時間最短，具有較好的時間性能。

表5 11個網絡中不同方法的運行時間Table 5 Running times of different methods on 11 networks 單位：s

圖8為不同方法在6個網絡中運行時間結果圖。KDN方法的運行時間明顯低于MDD方法、BC方法、CC方法和LGI方法，略高于K-shell方法和Cnc+方法。其中BC方法和CC方法考慮整個網絡的路徑信息，運行時間明顯高于其他方法。綜合考慮，KDN方法在時間指標方面表現出良好的性能。

圖8 不同方法在6個網絡中的運行時間Fig.8 Running times of different methods on six networks

4 總結與展望

精準識別復雜網絡中的關鍵節點一直是復雜網絡領域的研究熱點。本文通過綜合考慮節點的全局信息和局部信息，提出了一種基于鄰域K-shell分布的關鍵節點識別方法，并在11個網絡數據集上進行實驗驗證。結果表明，所提方法的識別結果在11個網絡數據集上均取得了最高的準確性，并且具有良好的區分度和時間性能。在當前大多數網絡都是動態變化的背景下，如何進一步利用節點位置信息和結構特點來評估動態網絡中節點的重要性將是未來的一個重要研究方向。