吳英晗，田 闊，李明達(dá)，胡 楓

1.青海師范大學(xué) 計(jì)算機(jī)學(xué)院，青海 810008

2.藏語智能信息處理及應(yīng)用國家重點(diǎn)實(shí)驗(yàn)室，青海 810008

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

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

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

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

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

1 相關(guān)知識

1.1 超網(wǎng)絡(luò)定義

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

1.2 超度

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

1.3 信息熵

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

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

1.4 介數(shù)中心性

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

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

1.5 接近中心性

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

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

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

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

1.6 子圖中心性

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

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

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

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

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

1.8 核度中心度

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

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

2 構(gòu)建節(jié)點(diǎn)傳播熵度量指標(biāo)

當(dāng)節(jié)點(diǎn)在整個(gè)超網(wǎng)絡(luò)中有效地傳播信息時(shí)，該節(jié)點(diǎn)的重要性及其對其他節(jié)點(diǎn)的影響力就會增強(qiáng)。由于節(jié)點(diǎn)在網(wǎng)絡(luò)中的傳播能力受節(jié)點(diǎn)局部拓?fù)湫畔⒑腿滞負(fù)湫畔⒌挠绊?，在評估超網(wǎng)絡(luò)中節(jié)點(diǎn)的傳播能力時(shí)，本文從熵的角度出發(fā)綜合考慮節(jié)點(diǎn)的聚集系數(shù)、鄰居數(shù)目、K 殼分解法以及最短路徑，充分考慮節(jié)點(diǎn)自身及其鄰域節(jié)點(diǎn)的影響，提出一種節(jié)點(diǎn)傳播熵指標(biāo)來度量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性。

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

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

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

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

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

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

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

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

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

2.3 節(jié)點(diǎn)傳播熵

在圖熵中，信息熵可以反映節(jié)點(diǎn)的重要性，而節(jié)點(diǎn)的重要性需要考慮節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)，由于鄰居節(jié)點(diǎn)的貢獻(xiàn)不同，本文在兼顧節(jié)點(diǎn)局部和全局拓?fù)湫畔⒌耐瑫r(shí)，充分考慮節(jié)點(diǎn)自身及其鄰居節(jié)點(diǎn)的影響，基于信息熵對節(jié)點(diǎn)傳播熵進(jìn)行以下定義：

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

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

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

算法1PE算法

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

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

1.fori=1 ton

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

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

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

5.forjinN1(i)

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

7.end

8.end

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

4 實(shí)驗(yàn)結(jié)果與分析

4.1 有效性分析

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

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

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

4.2 實(shí)驗(yàn)數(shù)據(jù)

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

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

4.3 評價(jià)標(biāo)準(zhǔn)

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

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

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

4.3.2 魯棒性評價(jià)指標(biāo)

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

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

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

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

4.3.3 SIR傳播模型

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

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

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

4.4 實(shí)驗(yàn)分析

4.4.1 單調(diào)性實(shí)驗(yàn)分析

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

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

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

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

4.4.2 魯棒性實(shí)驗(yàn)分析

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

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

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

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

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

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

4.4.3 SIR傳播模型實(shí)驗(yàn)分析

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

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

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

5 結(jié)語

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

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