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

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

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

3.高原科學與可持續(xù)發(fā)展研究院，青海 810008

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

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

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

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

1 相關(guān)知識

1.1 超網(wǎng)絡定義

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

1.2 超度

在超網(wǎng)絡H中，節(jié)點vi的超度是衡量節(jié)點影響力的最簡單指標。與節(jié)點vi相關(guān)聯(lián)的超邊數(shù)量越多，該節(jié)點的影響力就越大。節(jié)點vi的超度定義為：

1.3 信息熵

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

其中，Ii為節(jié)點vi的重要性。

1.4 介數(shù)中心性

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

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

1.5 接近中心性

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

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

di越小，節(jié)點vi與超網(wǎng)絡中其他節(jié)點越接近。節(jié)點vi的接近中心性[8]定義為di的倒數(shù)，計算如下：

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

1.6 子圖中心性

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

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

1.7 超網(wǎng)絡的K殼分解法

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

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

1.8 核度中心度

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

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

2 構(gòu)建節(jié)點傳播熵度量指標

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

2.1 節(jié)點的局部傳播能力

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

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

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

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

2.2 節(jié)點的全局傳播能力

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

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

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

2.3 節(jié)點傳播熵

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

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

3 基于節(jié)點傳播熵的重要節(jié)點識別算法

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

算法1PE算法

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

輸出：超網(wǎng)絡中各節(jié)點傳播熵PE值

1.fori=1 ton

2.根據(jù)公式（8）、（9）計算節(jié)點的局部傳播能力;

3.根據(jù)公式（10）計算節(jié)點的全局傳播能力;

4.根據(jù)公式（11）計算節(jié)點的相對重要度函數(shù);

5.forjinN1(i)

6.根據(jù)公式（12）計算節(jié)點的傳播熵值;

7.end

8.end

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

4 實驗結(jié)果與分析

4.1 有效性分析

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

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

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

4.2 實驗數(shù)據(jù)

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

表2 超網(wǎng)絡的統(tǒng)計特性Table 2 Statistical characteristics of hypernetworks

4.3 評價標準

4.3.1 單調(diào)性評價指標

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

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

4.3.2 魯棒性評價指標

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

其中，nc表示移除部分節(jié)點后網(wǎng)絡的最大連通子圖包含的節(jié)點數(shù)，n為原始網(wǎng)絡總節(jié)點數(shù)。

利用最大連通系數(shù)來計算網(wǎng)絡的魯棒性，計算公式如下：

其中，rj表示移除j個節(jié)點后的最大連通系數(shù)。R越小，網(wǎng)絡崩潰得越快，說明移除的節(jié)點越重要。

4.3.3 SIR傳播模型

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

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

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

4.4 實驗分析

4.4.1 單調(diào)性實驗分析

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

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

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

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

4.4.2 魯棒性實驗分析

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

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

圖4 超網(wǎng)絡最大連通系數(shù)Fig.4 Maximum connectivity coefficient of hypernetworks

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

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

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

4.4.3 SIR傳播模型實驗分析

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

圖6 節(jié)點傳播能力Fig.6 Node propagation ability

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

5 結(jié)語

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

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