利用節點傳播熵識別超網絡重要節點

吳英晗，田 闊，李明達，胡 楓

1.青海師范大學 計算機學院，青海 810008

2.藏語智能信息處理及應用國家重點實驗室，青海 810008

3.高原科學與可持續發展研究院，青海 810008

網絡科學的蓬勃發展使得復雜網絡的研究成為諸多領域關注的熱點。重要節點識別作為分析與理解復雜網絡特性、結構、功能的有效方式之一，被廣泛地研究并應用。例如，通過對新冠病毒傳播網絡中的超級傳播者實施隔離，能夠大幅度降低病毒的傳播速度，進而抑制病毒的擴散；通過對社會網絡中輿論領袖的言論加以控制，能夠有效抑制或促進信息的傳播；通過對交通網絡中重要的樞紐站點進行維保，能保證整個交通網絡正常運行的穩定性和流暢性。由此可見，識別網絡中的重要節點具有重大的應用意義。

由于現實世界是由多種主體關系組成的復雜系統，不同系統結構在網絡中表現為節點與邊的異質性[1]。在某些情況下，基于普通圖的復雜網絡[2-3]不能完全刻畫真實世界的網絡特征，因而，人們便將研究的視角轉向基于超圖的超網絡[4-8]。目前，研究人員根據不同的實際需求提出了眾多超網絡重要節點識別方法。其中，超度[7]是評估網絡節點重要性的常用方法，該方法有效但不精準；介數中心性[8]和接近中心性[8]考慮節點間的最短路徑數量和平均最短距離，此類方法從網絡全局角度出發，效果明顯但時間復雜度較高，不適用于大規模超網絡；K-shell分解法[9]考慮節點在網絡中的位置信息，計算時間復雜度低，適用于大型網絡，但其劃分結果過于粗?；榱烁纳平Y果粗粒化的情況，周麗娜等[10]基于復合參數的思想，結合超度及K-shell 值利用歐氏距離公式提出了一種超網絡關鍵節點識別方法。Son等[11]基于轉錄組學數據構建超圖，引入新的平均超圖中心性指標對與病毒/病原體感染相關的基因集進行對比分析，結果表明平均調和s-介數中心性能夠有效識別關鍵基因。Kovalenko 等[12]用向量表示超圖中節點的重要性，并據此揭示了同一節點在不同階數的交互關系中所扮演的不同角色；Aktas等[13]基于擴散模型，提出了兩種新的超圖拉普拉斯算子用以識別超圖中重要的超邊，并通過與一般中心性指標對比分析了新方法的性能優勢；Xie等[14]運用超圖上的傳播動力學過程提出了一種基于節點適應度消減的影響力最大化算法，揭示了超圖中節點間的高影響力重疊現象與節點度、超度間的強相關性。Lai 等[15]選取不同類型的交通網絡為對象，采用節點度、鄰居節點度、加權K-shell 鄰域識別方法（KSD）、度K-shell識別方法（DKS）以及度K-shell鄰域識別方法（DKSN）對關鍵節點進行識別，結果表明，綜合考慮因素的KSD方法識別效果最好，具有一定的實際意義。

傳統上使用熵[16-17]來描述整個網絡結構的復雜性和統計特性。Chen 等[18]提出結構熵來度量網絡的復雜性。張齊[19]提出一種基于非廣延統計力學的結構熵來度量網絡的復雜性。黃亞麗等[20]基于網絡節點在K 步內可達的節點總數定義K-階結構熵，用來評估網絡的異構性。Wang等[21]提出一種基于K殼和節點信息熵的改進算法，用來區分上層外殼和下層外殼中節點的重要性。Zhao 等[22]基于蛋白質復合物二階鄰域信息及信息熵和亞細胞定位提出一種必需蛋白質預測新方法NⅠE；賴強等[23]采用高度數加邊、高介數加邊、低度數加邊、低介數加邊和隨機加邊策略對城市公交網絡進行魯棒性優化，最后得出低度數和低介數加邊策略對網絡魯棒性提升的效果較好。田文等[24]引入相對熵，結合灰色關聯分析法綜合評價航路點重要程度，并采用基于K-means聚類方法有效劃分航路節點等級，提高了評價結果的全面準確性。

迄今為止，網絡熵已成為復雜網絡中評估節點重要性的有力工具，不少專家學者利用該工具設計出一系列有價值的識別方法?？v觀目前超網絡中基于網絡熵的研究成果，王福紅等[25]基于上下熵公理，通過對Tsallis熵以及Daroczy 熵進行合理處理，提出了一種度量超網絡復雜性的上下熵模型，為探索超網絡的復雜特性提供了新的理論基礎和參考；周麗娜等[26]通過研究節點及其直接和間接鄰居節點的關聯關系，利用節點信息熵表征節點在超網絡中的重要性，為超網絡重要節點識別提供了一種新的研究視角。由于該指標是一種局部性指標，僅僅考慮了一階鄰居節點的影響，而超網絡中節點的影響不僅取決于節點的局部影響，還依賴于節點的全局影響，因此，本文提出一種基于節點傳播熵的超網絡重要節點識別方法（PE）。該方法利用節點聚集系數和鄰居數目表征節點信息的局部傳播影響，通過節點間最短路徑和K殼分解法反映節點信息的全局傳播影響，充分考慮節點自身及其鄰域節點的影響，最后利用節點傳播熵來表征節點在網絡中的重要性。為了驗證該方法的有效性和適用性，本文選用了來自不同領域的六個實證超網絡，并采用六種已有的重要節點識別方法作為比較方法，在此基礎上，利用單調性、魯棒性以及SⅠR傳播模型證明了該方法的可行性。

1 相關知識

1.1 超網絡定義

2006 年，Estrada 等[5]首次提出基于超圖的網絡稱為超網絡（hypernetwork），其中超圖理論的基本概念和性質由Berge[27]給出，設V={v1,v2,…,vn} 是一個有限集；若ei≠φ(i=1,2,…,m)，且，則稱二元關系H=(V,E) 為超圖，其中vi(i=1,2,…,n) 稱為超圖的節點，ej(j=1,2,…,m)稱為超圖的超邊。超圖的鄰接矩陣A(H)是一個N×N的對稱方陣，其元素aij表示與節點vi和vj都相關聯的超邊數量。關聯矩陣B(H)是一個N×M的矩陣，如果節點vi與超邊ej關聯，則bij=1，否則為0。

1.2 超度

在超網絡H中，節點vi的超度是衡量節點影響力的最簡單指標。與節點vi相關聯的超邊數量越多，該節點的影響力就越大。節點vi的超度定義為：

1.3 信息熵

信息熵于1949年由Shannon等[16]提出，信息熵和熱力學熵緊密相關，所以信息熵是可以在衰減的過程中被測定出來的。因此信息的價值是通過信息的傳遞體現出來的。熵值越大，傳播得越廣，流傳時間越長的信息越有價值。在圖熵中，信息熵反映節點的局部重要性。網絡的信息熵被定義為：

其中，Ii為節點vi的重要性。

1.4 介數中心性

超網絡中，介數中心性通常根據最短超路徑來定義，刻畫節點對于網絡中沿著最短超路徑傳輸網絡流的控制力，節點的介數中心性值越大，該節點的影響力就越大。節點vi的介數中心性[7-8]定義為：

其中，gk表示節點vj和節點vk之間的最短超路徑數目，gk(i)表示節點vj和節點vk之間的最短超路徑中經過節點vi的數目。

1.5 接近中心性

接近中心性衡量的是節點到超網絡中其他節點的最短路徑之和，若某個節點到網絡中其他節點的最短路徑之和最小，即該節點可以在最短的時間內進行信息傳播，其影響力就越大。

對于具有n個節點的超網絡來講，節點vi到超網絡中其他節點的平均距離[9]可以表示為：

di越小，節點vi與超網絡中其他節點越接近。節點vi的接近中心性[8]定義為di的倒數，計算如下：

其中，dij表示節點vi到節點vj的最短距離。

1.6 子圖中心性

子圖中心性[5]從全局視野刻畫了網絡中各節點的相對重要性，反映了節點在不同子圖中的參與情況。超網絡中節點vi的子圖中心性定義為超網絡H中起止于該節點的不同長度的閉合路徑之和，可用鄰接矩陣特征值和特征向量表示：

其中，λj是超網絡H的鄰接矩陣A的特征值，uj是λj所對應的特征向量，uij表示特征向量的第i個元素。

1.7 超網絡的K殼分解法

K殼（K-shell）分解法[10]作為一種從網絡整體結構確定超網絡中節點位置的全局性指標，其基本思想是通過迭代的方式將超網絡劃分為從核心到邊緣的不同層次，越靠近核心的節點越具有影響力。具體劃分過程為：首先，刪除超網絡中超度為1 的節點及超邊超度為1 的超邊；其次，刪除后的網絡中將出現新的超度為1的節點，繼續刪除新出現的超度為1 的節點及超邊；最后，重復上述操作直至超網絡中不再出現超度為1 的節點及超邊超度為1的超邊為止。此時所有被刪除的節點Ks值為1。以此類推，直至超網絡中所有節點都被賦予Ks值。如圖1為超網絡的3-shell分解過程示例圖[10]。

圖1 超網絡的3-shell分解過程圖Fig.1 3-shell decomposition process diagram of hypernetwork

1.8 核度中心度

核度中心度kd s指標由周麗娜等[10]人提出，該指標有效改善了超網絡K-shell分解方法的區分度。它綜合考慮節點超度和K-shell 兩種指標的性質，利用歐氏距離公式定性計算超網絡中節點的核度值，節點vi的核度中心度定義為：

其中，dH(i)表示節點vi的超度，Ks(i)表示節點vi的Ks值。

2 構建節點傳播熵度量指標

當節點在整個超網絡中有效地傳播信息時，該節點的重要性及其對其他節點的影響力就會增強。由于節點在網絡中的傳播能力受節點局部拓撲信息和全局拓撲信息的影響，在評估超網絡中節點的傳播能力時，本文從熵的角度出發綜合考慮節點的聚集系數、鄰居數目、K 殼分解法以及最短路徑，充分考慮節點自身及其鄰域節點的影響，提出一種節點傳播熵指標來度量節點在網絡中的重要性。

2.1 節點的局部傳播能力

網絡是由若干“群”或“團”構成，每個群內部的節點之間連接相對緊密。在超網絡中，通常用聚集系數來衡量節點的聚類程度。隨機游走理論中，信息是從網絡中的某個節點以一定的概率傳播到與其連接的其他節點，因此，節點的聚集系數越大，信息越容易被傳回始發點，節點的傳播能力也就越差。進一步，本文考慮聚類系數對節點局部傳播能力的影響。節點的聚集系數定義為：

其中，Mi表示節點vi的kH(i)個鄰居節點間實際存在的超邊數，kH(i)(kH(i)-1)表示kH(i)個鄰居節點間最大可能存在的超邊數。

由于節點的聚集系數度量與朋友的朋友成為朋友的概率，這就表明節點的局部傳播能力不僅與一階鄰居的數量有關，還與二階鄰居的數量有關。因此，本文綜合考慮節點的聚集系數及其鄰域數量，用來描述節點的局部傳播能力，定義如下：

其中，N1(i)和N2(i)分別表示節點vi的一階和二階鄰居節點數量，CH(i)表示節點vi的聚集系數。

2.2 節點的全局傳播能力

超網絡中節點的傳播能力不僅取決于節點的局部拓撲信息，還依賴于節點的全局拓撲信息。K殼分解法作為描述節點在網絡中所處位置的全局指標，可以用來描述每個節點與整個網絡之間的關系以及不同節點之間的關系。當節點的鄰域節點的Ks值較大時，節點的傳播能力就會增強，但如果節點間的距離較大，就會減弱節點的傳播能力。因此，在評估節點的傳播能力時還需要考慮節點間最短路徑的影響。

綜合考慮節點所處位置以及最短路徑對節點傳播能力的影響，將節點的全局傳播能力定義為：

其中，Ksi表示節點vi的Ks值，Dij表示節點vi到節點vj之間的最短路徑。

2.3 節點傳播熵

在圖熵中，信息熵可以反映節點的重要性，而節點的重要性需要考慮節點的所有鄰接節點，由于鄰居節點的貢獻不同，本文在兼顧節點局部和全局拓撲信息的同時，充分考慮節點自身及其鄰居節點的影響，基于信息熵對節點傳播熵進行以下定義：

其中，N(i)表示節點vi的鄰居節點集，-IjlnIj表示鄰居節點的貢獻，Ii為節點vi的相對重要度函數，計算如下：

3 基于節點傳播熵的重要節點識別算法

基于節點傳播熵的重要節點識別方法構造的基本思想是從熵的角度綜合考慮節點的聚集系數、鄰居數目、K 殼分解法和最短路徑對節點傳播能力的影響，進而評估網絡中節點的重要性。由于聚集系數和鄰域數目能體現節點的局部拓撲信息，而K殼分解法和最短路徑表征了節點的全局拓撲信息，兼顧這兩種拓撲信息，利用信息熵度量網絡結構復雜性，并對每個節點自身及其鄰域節點進行綜合考察，從而給出一種基于節點傳播熵的識別超網絡中重要節點方法，簡稱為PE算法，其主要算法描述如下所示。

算法1PE算法

輸入：超網絡H=(V,E)

輸出：超網絡中各節點傳播熵PE值

1.fori=1 ton

2.根據公式（8）、（9）計算節點的局部傳播能力;

3.根據公式（10）計算節點的全局傳播能力;

4.根據公式（11）計算節點的相對重要度函數;

5.forjinN1(i)

6.根據公式（12）計算節點的傳播熵值;

7.end

8.end

由以上描述可知，PE 算法要遍歷網絡中的每個節點，在計算節點的局部傳播能力時，考慮節點及其二階鄰域拓撲結構間的關系，故時間復雜度為O(n2)；在計算節點的全局傳播能力時，節點的K殼重要性指標的時間復雜度為O(n)，節點到其他節點間的最短路徑的計算中使用了Dijkstra 算法，時間復雜度為O(n2)；在計算節點的PEi值時，時間復雜度為O(n)。因此，本文提出的PE算法的時間復雜度為O(n2)。其中，n為超網絡中節點的總數。

4 實驗結果與分析

4.1 有效性分析

為了驗證本文提出的PE 方法的有效性和準確性，首先以蛋白復合物超網絡[28]為例進行仿真分析。該網絡包含2 314個人類蛋白質節點以及蛋白質之間相互作用形成的1 342 條復合物超邊，根據在線基因必需數據庫（online gene essentiality（OGEE），https：//v3.ogee.info/browse）[29]查詢蛋白質的重要性。使用精確率指標評估七種不同中心性指標識別的蛋白復合物超網絡中的必需蛋白質。該指標僅考慮前k個節點是否準確預測，其值等于前k個節點中準確預測的節點比例。精確率定義如下：

其中，np表示前k個節點中包含的重要節點數。在該蛋白復合物超網絡中，k設置為1 000。從表1 可以看出，相比較其他重要節點識別方法而言，PE方法的精確度最高，表明PE 方法可以準確識別出超網絡中的重要節點。

表1 七種不同中心性方法識別重要蛋白的精確率Table 1 Precision of seven different centrality methods for identifying essential proteins

4.2 實驗數據

在實驗中采用了六種來自不同領域的實證超網絡，分別為：Karate超網絡、西寧市公交超網絡、都柏林感染超網絡、Facebook 電視節目超網絡、藥物靶標超網絡以及科研合作超網絡。各超網絡的統計特征如表2 所示。其中n為超網絡中節點總數，m為超邊總數，為平均超度，為平均最短路徑長度，CH為超網絡聚集系數。

表2 超網絡的統計特性Table 2 Statistical characteristics of hypernetworks

4.3 評價標準

4.3.1 單調性評價指標

本文采用單調性評價指標M(R)來量化不同重要性評估方法的分辨率，定義如下：

其中，R為重要節點識別方法得到的每個節點的重要性排序向量，n為網絡節點數目，nr表示重要性相同的節點數量。M(R)的取值介于[0，1]。如果M(R)=1 則排序向量R是完全單調的，說明該識別方法能將網絡中所有節點的重要性完全區分；反之，則表示網絡中所有節點的重要性相同。M值越高，表明識別方法的區分能力越高。

4.3.2 魯棒性評價指標

本文從魯棒性的角度通過移除節點后對網絡連通度的影響來評估重要節點識別方法的準確性。超網絡中，連通分量是一個網絡子超圖，其中子超圖中的任意兩個節點是連通的。最大連通子圖是指隨著節點移除網絡分解出的多個連通子超圖中包含節點數最多的連通分量，可以反映超網絡的連通性。如果移除的是重要節點，最大連通子圖的規模會變小。網絡的最大連通系數定義為移除節點后網絡最大連通子圖中包含的節點數與原始網絡總節點數之比，計算方法如下：

其中，nc表示移除部分節點后網絡的最大連通子圖包含的節點數，n為原始網絡總節點數。

利用最大連通系數來計算網絡的魯棒性，計算公式如下：

其中，rj表示移除j個節點后的最大連通系數。R越小，網絡崩潰得越快，說明移除的節點越重要。

4.3.3 SIR傳播模型

本文采用SⅠR（susceptible-infected-removed）模型來檢測超網絡中重要節點的傳播能力，SⅠR模型將網絡中節點的狀態劃分為三類：易感狀態S、感染狀態I以及恢復狀態R。SⅠR模型傳播過程如圖2所示。

圖2 SⅠR傳播模型圖Fig.2 Diagram of SⅠR propagation model

在傳播初始階段，網絡中一個或多個節點處于感染狀態，其余節點均處于易感狀態。在每個時間步中，處于I狀態的節點以傳播概率β感染處于S狀態的鄰居節點，同時以概率γ進入恢復狀態，且不再被感染。重復上述傳播過程直到網絡中沒有處于感染狀態的節點。在整個SⅠR傳播過程結束后，將網絡中處于R狀態的節點數量視為節點的傳播能力，記作F(t)。

4.4 實驗分析

4.4.1 單調性實驗分析

為了度量PE 方法對重要節點的區分度，本文選用超度(dH)、介數中心性（BC）、接近中心性（CC）、子圖中心性（SC）、K 殼分解法(Ks)、核度中心度(kd s)共6 種識別方法作為對比方法，利用單調性指標評估6種對比方法與本文所提出的PE方法的分辨率。表3記錄了不同識別方法在6 個真實網絡中的單調性值；圖3 則更為直觀地呈現了不同方法之間的差異。

表3 不同識別方法的單調性指標MTable 3 Monotonicity index M of different evaluation methods

圖3 不同評估方法的單調性指標MFig.3 Monotonicity index M of different evaluation methods

結果表明，PE 方法在5 個真實超網絡中表現較好。此外，CC和SC方法的區分度也很好。與其他6種方法相比，PE方法在大多數情況下的M值最高且接近1。因此，PE方法能夠較好地區分節點的重要性。

4.4.2 魯棒性實驗分析

為了進一步分析PE 方法識別的節點的重要性，本組實驗分別通過超度(dH)、介數中心性（BC）、接近中心性（CC）、子圖中心性（SC）、K 殼分解法（Ks）、核度中心度(kd s)和節點傳播熵（PE）7種方法將6種實證超網絡的所有節點進行重要性排序，并按照重要性排序依次移除一定比例的節點，基于連通性分析刪后網絡的最大連通系數，以此來評估7 種不同重要性度量指標的魯棒性。移除節點后網絡的最大連通系數變化曲線圖如圖4 所示；不同重要性度量指標的魯棒性值如表4所示；圖5則更為直觀地呈現了不同方法之間的魯棒性差異。

表4 不同識別方法的魯棒性值RTable 4 Robustness values R of different evaluation methods

圖4 超網絡最大連通系數Fig.4 Maximum connectivity coefficient of hypernetworks

圖5 不同評估方法的魯棒性值RFig.5 Robustness value R of different evaluation methods

從圖4 可知，在Karate 超網絡中，當移除節點的比例到0.3的時候，通過PE方法移除節點后的最大連通系數變化比較明顯，較初始階段下降85%，說明相較于其他幾種方法，PE 方法具有一定的優勢。在其余超網絡中，表現最優的是BC方法，這是因為BC方法可以準確識別網絡中的“橋”節點，隨著高介數節點的移除，則會斷開網絡的連通性，因而網絡的最大連通系數變化比較明顯。Ks以及kd s方法在移除節點初期，最大連通系數變化明顯的原因是，二者均是在dH的基礎上提出的改進方法，按此方法選擇的重要節點移除時，節點的鄰居數量相對其他方法更多，移除節點及其連邊后最大連通子圖的規模會銳減。在科研合作超網絡和藥物靶標超網絡的實驗中，移除節點初期階段，PE方法的效果不如BC、dH、Ks以及kd s方法，但是后期的效果是具有優勢的，可見，對于網絡的蓄意攻擊，PE 方法考慮了長期的收益。此外，在整個魯棒性實驗中，PE方法的效果明顯優于CC和SC方法。

由表4 可知，魯棒性R值越小，該方法的性能表現越好。圖5 可以更直觀看出，在5 個真實超網絡中，PE方法要優于CC 和SC 方法，與其他方法相比不明顯，但是與超度相比，PE方法提高了節點重要性的區分度，與BC、CC 方法相比，PE 方法在時間復雜度上得到了有效提升。隨著網絡規模的擴大，PE 方法的魯棒性也在提升，在對科研合作、藥物靶標超網絡進行攻擊時，由于其平均路徑長度相對較大且聚集系數較低，PE 方法的效果相對明顯。雖然PE方法不是降低超網絡連通性的最佳選擇，但該方法計算復雜度相對較低且傾向于優先破壞網絡中的傳播核心結構。

4.4.3 SIR傳播模型實驗分析

為了驗證PE方法識別的重要節點在超網絡中的傳播能力，本節通過在6 個真實超網絡上使用SⅠR 模型模擬傳播過程，對比不同方法到達穩態時的感染節點數來考察節點的重要性。本實驗選取7 種算法識別的重要節點排序列表中前10 個節點作為初始感染節點，觀察每一時間步網絡中感染過的節點數目以及最終到達穩態時感染過的節點數目，為保證傳播過程正常進行，設定傳播概率為網絡的傳播閾值，即，其中為網絡平均超度，恢復率γ=0.1。實驗結果如圖6所示。

圖6 節點傳播能力Fig.6 Node propagation ability

在SⅠR 模型的實驗中，傳播感染的節點數越多，證明所識別的節點在網絡中的重要性越高。通過對比圖6 中6 個真實網絡的傳播情況可知，對于各個傳播時間通過PE方法識別的重要節點的傳播能力明顯優于其他六種方法，其傳播曲線始終位于各方法曲線之上，表明該方法識別的重要節點最終到達穩態時感染過的節點數目是最高的。在科研合作超網絡中，PE 方法的傳播效果完全優于其他方法，原因是該網絡聚集系數相對較小且網絡節點連接稀疏，對該類型網絡進行信息傳播時，PE 方法的優勢較明顯。從圖6 的曲線斜率來看，傳播到達穩態之前通過PE算法識別的節點傳播能力的曲線斜率要高于其他6 種方法，表明通過PE 算法識別的節點在網絡中的傳播速度較快，傳播范圍較廣，進而驗證了本文所提出的方法可以有效識別超網絡中的重要節點。

5 結語

本文從熵的角度綜合考慮節點自身聚集特性、所處網絡位置及其路徑信息對節點傳播能力的影響，提出了一種基于節點傳播熵的超網絡重要節點識別方法PE。通過對6 個真實網絡進行仿真驗證，結果表明PE 方法具有高區分度，明顯的傳播優勢，可以在不同類型的超網絡中發現具有強傳播能力的節點。此外，PE 方法的時間復雜度為O(n2)，適用于大規模超網絡。

由于真實網絡呈現出動態性以及多層多級多維的特征，本文提出的方法還存在一定的不足，在未來的工作中會結合網絡的時空特性，將提出的PE 方法應用于多層超網絡的重要節點識別研究。