基于交叉熵的節點重要性排序算法

龔志豪，蔣 沅，代冀陽，楊智翔

(南昌航空大學信息工程學院 南昌 330063)

隨著網絡科學的發展與進步，復雜系統已深入人類社會的各個領域，復雜網絡作為刻畫復雜系統的工具，在生態、社會、經濟、交通等諸多系統中有著重要影響[1-2]。關鍵節點影響著網絡的結構和信息傳遞功能，評估關鍵節點是復雜網絡的研究熱點[3-4]。一方面，快速準確地識別出關鍵節點并提供保護機制可提升網絡的抗毀性[5]。另一方面，基于關鍵節點也可以提出更高效的攻擊策略[6-7]。因此，設計高效的關鍵節點評估算法具有重要的理論和實踐意義。

近年來，研究人員關于識別關鍵節點已有許多研究成果，經典的評估算法有基于節點鄰近信息的度中心性[8]、基于最短路徑數目的介數中心性[9]、基于平均距離的接近中心性[10]以及基于網絡位置的K-殼分解法[11]等。其中度中心性雖然簡單直接，但對鄰居節點的重要性區分度較低，并且考慮的鄰近信息有限，因此評估的精確性不高。介數和接近中心性僅考慮信息在最短路徑上傳播，而實際上傳播可能基于其他可達路徑，此外基于路徑的算法時間復雜度較高，不適用于大型網絡。而具有較低時間復雜度的K-殼分解法認為節點重要性取決于所處網絡的位置，內核層節點的重要性高于邊緣的節點，但對同一殼層的節點卻無法進一步區分其重要性差異，并且節點在剝離時會對網絡的整體結構信息造成破壞[12]。為彌補經典算法評估的局限性，文獻[13]考慮節點與其相鄰節點之間的相關性，提出了映射熵來評估網絡中節點的重要性。文獻[14]通過衡量節點的局部拓撲重合度來刻畫節點間的相似性，提出了鄰域相似度算法用于評估節點的重要性。文獻[15]結合節點的K-殼以及信息熵，根據其分層大小依次進行迭代，可區分內層殼與外層殼中的節點重要性。文獻[16]受引力公式啟發，將節點的度值作為質量，并將最短路徑長度作為距離，考慮了節點的近鄰以及路徑信息，提出了引力模型算法。文獻[17]考慮節點在網絡中所處的位置，提出了一種基于K-殼分解法的改進引力模型算法。

熵[18]可用于定量描述信息量的大小，當使用熵理論刻畫復雜網絡時，信息熵可表征節點的局部重要性，因此，可考慮用子網絡的熵來表征網絡整體結構的特性。如文獻[19]提出了信息熵來評估復雜系統的結構特征，取得了較好的成效。文獻[20]改進了K-殼值對信息熵的計算，提出了一種結合節點信息熵與迭代因子的算法。文獻[21]基于非廣延統計力學，提出了一種局部結構熵來量化復雜網絡中的關鍵節點。文獻[22]結合網格約束系數以及節點的K-殼中心性，基于Tsallis 熵提出了一種節點重要性識別方法。

受上述研究啟發，本文提出了一種基于交叉熵的節點重要性識別算法CE+（cross entropy），該方法充分考慮了節點自身以及其周圍節點信息的整體重要性，CE+的值反映了節點與其近鄰節點之間的差異性，并且該算法時間復雜度僅為O(n)，適用于大型網絡。通過在8 個不同領域的真實網絡上進行蓄意攻擊實驗，并選用7 種不同的節點重要性排序算法作為對比，采用單調性指標[23]、極大連通系數[24]、網絡效率[25-26]以及SIR 模型[27]等指標驗證了本文所提出CE+算法的有效性和適用性。

1 理論基礎

假設無向未加權的網絡G=(V,E)， 其中V是網絡G的節點集合， |V|=n，E是網絡的邊集合，|E|=m。A=(ai j)n×n通常表示網絡的鄰接矩陣，若節點i與 節點j相連，則ai j=1， 否則ai j=0。

1.1 度中心性

度中心性[9]是度量重要節點性能最基礎的指標，節點的鄰居節點數越多，則自身的影響力越大，其定義為：

1.2 介數中心性

當網絡中某一節點i存在于其他節點之間的最短路徑上并且次數越多時，則說明節點i的關鍵程度越高，其定義為：

1.3 映射熵

文獻[13]考慮節點中所有鄰域相關的局部信息，提出了映射熵來評估復雜網絡中的節點中心性，定義為：

式中，M是節點i的 鄰居集； D Cj是其相鄰節點之一的度中心性。

1.4 鄰域相似度

文獻[14]綜合考慮了節點的度值和鄰居節點的拓撲重合度，提出了一種基于鄰域相似度的評估算法，定義為：

式中，n(i)為 節點i的 鄰居節點；若節點b與c無連邊，則s im(b,c)=|n(b)∩n(c)|/|n(b)∪n(c)|； 若節點b與c有連邊，則s im(b,c)=1。

1.5 改進的K-殼分解法

文獻[15]結合K-殼分解法以及節點的信息熵，根據K-殼的分層大小依次進行迭代，每層中選擇節點信息熵最高的節點，直到所有節點均被選中為止，定義為：

式中， τ(i)表 示節點i的 鄰居集；

1.6 引力模型

文獻[16]綜合考慮了節點的鄰居信息和節點間的路徑信息，分別將節點的度值和最短路徑長度類比為物體的質量和距離，提出了引力模型算法，計算公式如下：

式中，R表示截斷半徑，通常為平均最短距離的一半。由于僅考慮了截斷半徑內的引力，該算法也被稱為局部引力模型。

1.7 KSGC 算法模型

文獻[17]認為節點在網絡中所處的位置是一個重要屬性，因此，在K-殼分解法的基礎上對引力模型進行了改進，提出了KSGC 算法用于評估節點的影響力，計算公式如下：

1.8 交叉熵

交叉熵[28]廣泛應用于邏輯回歸模型分析中，其定義為隨機分布p和q之間的自信息差異，可用來量化兩個變量之間的相似度，通常交叉熵值越大，則兩個變量之間的差異性越大，其計算公式如下：

式中，x表示事件包含的信息量。對式(8)同時增減可得：

將式(9)中的前兩項對數函數合并可得：

則式(10)可被定義為：

式中，H(p)為 信息熵，表示隨機分布p的平均信息量；DKL(p‖q)為 相對熵，同樣反映隨機分布p和q之間的差異程度。因此，交叉熵作為信息熵與相對熵之和，對于隨機變量的信息量及其差異性刻畫更加直觀。

2 基于交叉熵的節點重要性排序算法

2.1 算法構造

交叉熵可衡量隨機變量所包含信息量的差異，類似地，復雜網絡中不同節點之間的拓撲信息也存在差異，因此考慮引入交叉熵衡量復雜網絡中節點的統計特征。

基于交叉熵的節點重要性排序算法的原理是綜合考察節點自身以及其周圍節點信息的整體重要性，結合這兩種拓撲信息，可利用交叉熵值來量化節點分布之間的差異，若交叉熵值越大，則節點之間分布差異性越大，說明該節點代表性越高，重要性更顯著。因此本文提出了基于交叉熵的算法CE+，其定義如下：

式中，j∈Γ(i)表 示節點j是節點i的 鄰居節點；Ii表示節點i的異構性。考慮到度中心性可在時間復雜度較低的同時較好地反映節點及其近鄰節點所構成子網絡的拓撲結構，因此將Ii定義為：

由此，節點之間的異構性可得以良好的表征。在基于交叉熵的節點重要性計算方法中，通過融合中心節點與其局部節點的信息結構并相互交叉考慮，使得節點影響力的差異刻畫更為準確。該算法的偽代碼如下。

表1 列出了8 種不同評估算法的時間復雜度，分別包括局部、全局以及混合3 個類型的網絡信息。其中CE+算法的時間復雜度與DC、LLS、ME 以及IKS 算法同為最低。

表1 不同評估算法的時間復雜度

2.2 示例分析

為初步驗證CE+算法的量化分辨率與精確性，構建示例網絡如圖1 所示。

圖1 示例網絡

在示例網絡中，以節點24 為例，其交叉熵計算過程如下：

節點24 的度值為1，其鄰居節點23 的度值為3，而節點23 的其余鄰居節點3、25 的度值分別為4、2，故計算節點24 的交叉熵值為0.282 4。同理，可以計算示例網絡中其他節點的交叉熵值，其計算結果如表2 所示。

表2 各節點的交叉熵值

表3 記錄了不同評估算法對示例網絡中節點進行排序的結果，可以看出，KSGC 和GM 算法與本文所提出的CE+算法具有相同的排名廣度，但其對首要節點的排序結果略有不同，分別移除節點4、5 和14，得出非連通子圖的數量分別為2、2 和6，顯然移除節點14 對網絡破壞性更大。此外其余算法對網絡外圍節點的量化區分度較低，過于粗粒化。因此CE+算法對重要節點排序的精確性得到了初步驗證。

表3 不同評估算法排序結果

3 實驗數據集與評價指標

3.1 實驗數據集

實驗選用了8 個不同領域的真實網絡數據集，分別是：維基語錄編輯網絡Wikiquote[29]、金融網絡Economic[30]、約束優化模型網絡BP[31]、犯罪案件人物關系網絡Crime[32]、大學生電子郵件網絡Email[33]、空中交通管制網絡Traffic[34]、智人細胞中的蛋白質網絡Proteins[35]以及青少年朋友關系網絡Adolescent[36]。表4 列出了各網絡的拓撲統計參數，其中N和E分別為網絡的節點總數和連邊總數，D表示網絡的密度，kmax表示網絡節點的最大度值，和

表4 8 個真實網絡的拓撲統計特征及傳播率

3.2 評價指標

為驗證CE+算法的性能，本文基于網絡節點的單調關系、魯棒性以及SIR 傳播動力學模型對節點重要性進行研究。首先采用單調性指標定量分析不同算法的分辨率，其次選取極大連通系數以及網絡效率指標來評估攻擊節點前后網絡結構和功能的變化，最后在SIR 模型上再進行傳播仿真實驗分析。

單調性指標[23]是通過計算節點重要性排序中具有相同排名索引的節點比例來度量節點的評估效果，定義為：

式中，R為經由節點重要性排序算法所得到的排名索引；nr表示具有相同排名索引的節點數量；M(R)∈[0,1]， 若M(R)=1，則該算法完全單調，所有節點都具有不同的排名索引值。若M(R)=0，則該算法無法區分，每個節點的排名索引值相同。

極大連通系數[24]常用于評價移除網絡中的節點后對極大連通子集的影響，表示為：

網絡效率[25-26]常用于度量網絡連通性的強弱，計算公式為：

攻擊網絡中一定比例的節點，若網絡效率下降趨勢越明顯，則該算法的排序準確性越高。

SIR 模型[27]常用于驗證節點傳播信息與病毒的能力，在SIR 模型中，網絡中的所有節點具有3 種狀態，分別是易感狀態S、感染狀態I 以及免疫狀態R。病毒傳播初始時，除少數節點處于感染狀態外，其他節點均處于易感狀態。每個時間步長里，感染節點以β 的概率嘗試感染易感的鄰居節點，此外，感染節點還以μ 的概率嘗試恢復為免疫節點，為不失一般性，本文設定恢復率μ =1。需要注意的是，免疫節點不會被再次感染，同樣也不具有感染能力。當網絡達到穩定時，傳播過程結束，此時免疫節點的數量可用于量化初始感染節點的傳播能力。

4 實驗分析

本文選取了度中心性（DC）、介數中心性（BC）等經典算法作為對比方法，還選取了鄰域相似度（LLS）、引力模型（GM）、改進的引力模型（KSGC）、映射熵（ME）以及改進的K-殼分解法（IKS）等近期提出的性能顯著的排序算法進行比較，記錄8 種排序算法在8 個真實網絡數據上各評估指標的實驗結果。

4.1 單調性指標

表5 記錄了本文所提出的CE+算法與其他評估算法的單調性指標，加粗數值為最優值，可以看出，CE+算法在大部分網絡中均表現出較好的分辨率，并在一些網絡（如BP、Adolescent）中達到了1，這說明CE+算法是完全單調的，網絡中的每個節點都具有不同的排名索引值。此外，KSGC和GM 算法也表現出良好的區分度。

表5 不同評估算法的單調性指標

4.2 極大連通系數

圖2 呈現了不同評估算法模擬蓄意攻擊網絡所造成極大連通系數變化的趨勢，其中橫坐標為各評估算法排序下依次移除節點占節點總數的比例，縱坐標為極大連通系數，可以看出在8 個真實網絡中，本文提出的CE+算法均表現出更好的攻擊效果。在BP 和Adolescent 網絡中，各算法的前期破壞效果出現了高度重合，這是因為網絡的連邊總數遠高于節點總數，導致節點間緊密連接，而當攻擊節點數達到一定比例時，CE+算法表現出了較其他算法更為明顯的攻擊效果。因此，CE+算法度量節點重要性的準確性得到了驗證。

圖2 8 個網絡在各類評估算法攻擊下極大連通系數變化

4.3 網絡效率

圖3 展現了利用不同的評估算法排序依次移除節點后，對網絡效率所造成的變化趨勢。可以看出，在Wikiquote 網絡、Economic 網絡和Adolescent網絡中，CE+算法相較于其他算法對網絡的蓄意攻擊效果更為明顯，而在Crime 網絡與Traffic 網絡中，KSGC 和IKS 算法的攻擊效果基本一致，ME 和DC 算法分別在移除節點比例達到16%以及18%時，破壞效果最明顯。此外，當攻擊節點比例相同時，CE+算法的破壞曲線整體下降最快，這說明此時的網絡連通性最差。因此，CE+算法度量節點重要性的準確性得到了進一步驗證。

圖3 8 個網絡在各類評估算法攻擊下網絡效率的變化

4.4 SIR 模型傳播

為從不同角度評價CE+算法的有效性和適用性，在SIR 模型中再進行傳播實驗分析，利用各種評估算法排序前10%的節點作為初始感染節點，傳播率閾值設定為βth=/。其中為平均度，為二階平均度。實際傳播率基于閾值四舍五入并精確到百分位，具體取值如表5 所示。為減小迭代過程隨機的影響，本文選擇對于N<1 000 的網絡模擬迭代1 000 次，對于N＞1 000 的網絡模擬迭代100 次。

圖4 反映了各評估算法中重要性排名前10%的節點作為感染節點N隨時間步長t的變化趨勢，可以看出當時間步長達到15 時，大部分網絡趨于穩定，其中CE+算法的傳播曲線具有處于穩定狀態時的最高高度以及最大斜率，這說明本文所提出的算法具有最廣泛的傳播范圍以及最快傳播速率。而在BP 網絡中，CE+算法的傳播效果與其他算法的差異較小，是因為該網絡的節點間分布密集，關聯程度較高，信息具有易傳播、易擴散的特點。整體來看，CE+算法相較于其他算法更能準確快速地挖掘出網絡中影響能力較強的節點。

圖4 8 個網絡在各類評估算法下感染節點的變化

為比較不同比例的初始節點在傳播達到穩態時的規模，本文分別選取模擬迭代1 000 次的Crime網絡以及模擬迭代次數100 次的Traffic 網絡，并分別選取各種算法排名前5%、15%以及20%的節點作為感染節點進行傳播驗證實驗，實驗結果分別如圖5 和圖6 所示。結合圖5 中Crime 和Traffic網絡圖可知，BC 算法曲線趨于穩態的高度僅在初始感染節點為5%時較高，IKS 算法曲線也僅在初始感染節點比例為20%時具有較大的斜率，而CE+算法在各種比例初始感染節點下均具有顯著的傳播范圍以及感染速率，可知CE+算法在這兩方面優于其他算法，由此驗證了CE+算法的有效性以及適用性。

圖5 不同比例初始節點在Crime 網絡上感染節點的變化

5 結 束 語

在網絡科學研究中，識別復雜網絡中的核心關鍵節點有助于提高網絡的魯棒性和抗毀性。本文基于交叉熵提出了一種新的節點性能評價排序算法，算法只需獲取中心節點與其近鄰節點的信息就可反映節點之間的差異性，并且時間復雜度僅為O(n)，適用于刻畫大規模復雜網絡中節點的重要性。通過在8 個不同領域的真實網絡上進行單調關系、極大連通系數、網絡效率以及SIR 模型傳播實驗，結果表明，本文所提的CE+算法對比DC、BC、LLS、KSGC、GM、ME 和IKS 算法具有更高效的性能。