基于熵的節點重要度評估方法

摘" 要： 針對網絡中關鍵節點識別問題，提出一種基于熵的有向加權網絡節點重要度評估方法，即EnRank算法。通過定義有向加權網絡中各個節點吸引率AR和傳輸率TR，運用熵法對節點的度、吸引率和傳輸率進行綜合運算，從而得出有關于節點重要性綜合評價指標。該算法既考慮了節點本身的重要性，也考慮了相鄰節點對其相對重要性。經過對ARPA網絡及社交網絡連鎖故障仿真實驗，驗證了該方法的可靠性。

關鍵詞： 節點重要性； 熵法； 有向加權網絡； EnRank算法

中圖分類號：O157.5" " " " " 文獻標識碼：A" " "文章編號：1006-8228（2023）12-01-04

Entropy based node importance evaluation method

Pan Xiangxiang， Yao Hongguang

（School of Air Transport， Shanghai University of Engineering Science， Shanghai 201600， China）

Abstract： Aiming at the problem of identifying key nodes in a network， an entropy based network node importance evaluation method， namely EnRank algorithm， is proposed. By defining the attraction rate AR and the transmission rate TR of each node in the directed weighted network， the degree， attraction rate and transmission rate of the node are comprehensively calculated by entropy method， and the comprehensive evaluation index of node importance is obtained. The algorithm considers both the importance of nodes themselves and the relative importance of neighboring nodes. The reliability of the method is verified by simulation experiments on ARPA network and social network.

Key words： node importance; entropy method; directed weighted network; EnRank algorithm

0 引言

近年來，復雜網絡的理論研究吸引了來自復雜性科學、信息科學、經濟學、社會學、生物信息學等相關領域的大量研究者。網絡中很多有價值的信息已經能夠被獲取到。復雜網絡研究的發展在某種意義上受到了推動。由于復雜網絡的無標度[1]和小世界特征[2]，網絡中存在一些關鍵節點對網絡的結構和功能有很大的影響。因此，網絡中關鍵節點的識別是一個具有重要研究價值的課題。目前，關于節點重要性評估的相關研究主要集中在單向加權網絡[3-7]上。因此，如何利用定量方法快速有效地挖掘定向加權網絡中的重要節點具有重要意義，有助于提高整個網絡[8]的可靠性和脆弱性。

目前，學者們提出了許多經典的評價算法，但仍存在一些不足之處。Lü[9]改進了PageRank算法背景節點以及節點與網絡中所有節點的雙向邊緣，從而大大提高了密鑰的識別精度。但該算法卻并不能直接應用于有向加權網絡中。

HITS算法[10]為每個節點提供了兩個指標：權限和集線器。在運用不同指標同時對每個節點進行排序具有開拓性意義。周漩[11]提出了節點重要性評估矩陣（NIEM），該矩陣不僅考慮了節點程度和效率，而且還考慮了鄰居的貢獻。它評估節點的重要性取決于節點之間的關系。雖然它可以表示出節點的重要性并可以運用于大型復雜網絡，但是它只考慮了節點的鄰居而忽略了節點之間的關系，因此，它的重要性并不能完全反映出真實的情況。Hu[12]認為鄰居和非鄰居在一定程度上對評估節點有一定的重要性。因此提出了一種基于節點重要性貢獻相關矩陣（NICCM）的評價方法。本文提出的EnRank算法基于AR和TR等指標，表征了一個節點與另一相鄰節點之間的重要性。運用熵法計算度、AR和TR的綜合指數。不僅考慮了節點與其相鄰節點之間的邊的權值，還考慮了相鄰節點的強度。它將同時考慮節點自身的重要性和節點對相鄰節點的相對重要性，從而使結果更加準確。這在一定程度上彌補了現有算法的不足。

本文定義了基于節點重要性的兩個指標：基于定向加權網絡的AR（吸引率）和TR（傳輸率）。利用熵法計算出節點的綜合指標。進而提出了一種基于熵法的節點重要度綜合評價方法。在這種方法中，AR和TR間接地反映了節點本身的重要性。

1 基于節點重要性的指標

1.1 定向加權網絡及評價指標

G={V，L，W}，其中V={v1，v2，…，vn}表示網絡中所包含節點的集合，所述L為邊集，且L={l1，l2，…，1m}，lt;vi，vjgt;?L描述節點vi到節點vj的一條有向邊。n為節點數記作n=|V|，m=|L|表示圖形中有向邊的數目。實驗中W表示有向加權網絡的權值矩陣，有向邊lt;vi，vjgt;的權值標記為[wij]。

[Pinij∈Viniwj，iSoutj，" " " "Vini≠Φ0，" " " " " " " " " " "else" "]" "⑴

其中，[Vini]表示指向節點i的所有節點的合集。[wj，i]表示節點j和i之間的權重，[Soutj=k=1，k≠jnwj，k]表示節點j的輸出強度。若[Pini]值越大則節點j通過節點i發送信息的概率更大。當節點i發生故障時，將嚴重影響節點j的信息傳遞能力，這表明該節點更重要。

節點傳輸速率定義為：

[Poutis∈Voutiwi，sSins，" " " "Vouti≠Φ0，" " " " " " " " " " " " " " else]" ⑵

[Vouti]指示節點i指向的所有節點的集合，[wi，s]表示節點i和節點s之間的權重，[Sins=k=1，k≠snwk，s]表示節點s的強度。若[Pouti]越大，則節點s通過節點i獲取信息的概率越大，當節點i發生故障時，會嚴重影響節點s的信息獲取，說明該節點更顯著。

網絡的最大連接系數描述為：

[G=NrN]" ⑶

其中，[Nr]表示刪除某些節點后最大連接子集中的節點數，N表示原始網絡中的節點數量。如果在移除節點時G值更快地減少，則表示該算法更有效。

網絡平均效率：

它被定義為復雜網絡中每一個節點之間距離之和的倒數的平均值，即諧平均距離，可以反映出網絡信息流通的平均難度。

[E=1NN-1i≠j1Dij]" ⑷

其中，N表示網絡中節點的數量，而[Dij]表示節點i和j之間的距離。

1.2 節點的綜合指標

熵法計算綜合指標：

[Pij=Viji=1NViji=1，2，3，......N，j=1，2，3]" ⑸

公式⑸被定義為計算第i個節點的第j個指標的比重。

[ej=-Ki=1NPijlnPijj=1，2，3]" ⑹

公式⑹為計算指標的熵，其中[K=1lnN]，N為節點數，[0≤ej≤]1。

指標的微分系數定義為：

[Hj=1-ej]" ⑺

[Wj=Hjj=13Hj]" ⑻

最后，計算綜合評價指標：

[Ci=j=13Wj×Vij]" ⑼

1.3 EnRank算法設計

EnRank具體算法（表1）步驟如下：輸入圖集[GV，L，W]，輸出為[Ci]的排名。①對于每個[Vi∈V]，根據公式⑴、公式⑵和度的定義計算每個節點的AR、TR和度，結束此項命令；②對于每個[Vi∈V]并根據公式⑸和公式⑹計算每個指標的熵[ej]，結束此項命令；③對于每個[j≤3]并根據公式⑺和公式⑻計算每個指標的權重[wj]，結束此命令；④對于每個[Vi∈V]并按公式⑼計算節點的重要性[Ci]，結束此命令；⑤獲取[Ci]的排名列表；⑥返回排名列表[Ci]。

2 算法有效性分析

為了進一步驗證算法的有效性，我們選擇研究節點重要性最常用的ARPA網絡作為研究對象。雖然它屬于無向和未加權網絡，但為了使其適用于本文的算法，我們使用加權方法[11]和定向方法[12]將其處理為有向加權網絡，如圖1所示。

觀察表2中不同方法對ARPA網絡上節點重要性的結果數據可以看出，EnRank算法所計算出的排名前五的重要節點分別是節點3、2、14、9、19，在這五個節點中除節點9外的其他節點均屬于NICCM和NIEM評估矩陣獲取的前五個重要節點。這在某種程度中顯示出EnRank的可靠性和有效性。在我們的方法中，節點9排名第四，但根據文獻[9]NICCM中只排名倒數第二，參考文獻[11]NIEM中為最后一個。刪除了節點9后，網絡的平均效率僅為0.0781，去掉節點17之后，數值轉變為0.0817。這表明節點9的重要性高于節點17，這一結果與我們的結果一致。此外，節點18、21的重要性在NICCM和NIEM重要性評估矩陣和本文所提及的EnRank算法中也大不相同。在節點18或21被刪除之后，網絡平均效率的數值為0.8180。然而，從信息傳遞的角度看，節點21不僅是節點20的惟一信息來源，還是節點6的三個信息源之一，而節點18則只是節點3和節點19的三個來源之一。因此，節點21的重要性遠遠超過節點18。

3 級聯故障模擬

通過三種不同的算法對APAR網絡進行了研究和比較。實驗結果表明，該算法能夠更好地區分節點的重要性，從而證明了該算法的有效性。經過對ARPA、空手道俱樂部以及1997年北美航空網絡USAir97的魯棒性分析，我們發現該算法能夠以高效、可靠的方式運行，從而有力地證明了其可靠性。當節點重要性排序列表中的節點被順序移除時，如果子圖S較大，G較小，則攻擊達到目標，網絡的連通性大大降低。這表明網絡的魯棒性較差，證明了相應識別算法的準確性和可靠性。本文通過級聯失效仿真實驗，對三種不同的算法進行了比較和分析。結果如圖2、圖3和圖4所示。

觀察ARPA網絡最大連通系數G的變化趨勢，當去除的節點數量增加時，EnRank算法會產生更大的下降影響。在ARPA網絡中，盡管刪除第二、第四和第六節點的性能暫時落后于NICCM，EnRank算法在刪除前七個節點后，表現出了明顯優于另外兩種算法的形勢。實驗中本文所提出的方法的最大連通系數值要低于NICCM，為0.15，比NIEM的數值小0.5。從G的變化趨勢可以看出，雖然在去除第2、4、6個節點后，EnRank算法的子圖數量S明顯大于NIEM，但卻略低于NICCM。在第七個節點被刪除時，EnRank算法的子圖數量S要明顯大于另外兩種方法。此外通過觀察空手道俱樂部和USAir97網絡的實驗，本文算法的結果要明顯優于傳統的兩種重要性評估矩陣。

4 結束語

研究發現，EnRank算法可以更好的識別ARPA網絡中各節點之間的差異。網絡平均效率會隨著本文EnRank算法發現的重要節點的去除而迅速下降。表2所記錄的排名前四的關鍵節點在被刪去之后，子圖S的數量會增加，另外，最大的子圖規模會隨之縮減。該實驗結果表明EnRank算法會顯著影響網絡的連通性。研究發現，有向加權網絡的最大連通系數G以及子圖的數量S，都可以通過本文方法來實現快速增加/減少，這進一步表明了該算法的可靠性。實驗表明，EnRank算法能夠有效地識別出ARPA網絡中的關鍵節點并區分其重要性。當去除排名前五的關鍵節點時，網絡平均效率會急劇下降，此時子圖的數量會增加，而最大子圖的規模會減少，這說明EnRank算法對網絡的連通性有著顯著的影響。有向加權網絡中最大連通系數G可以通過本文所提出的方法來降低，子圖S的數量也可以依靠此方法來增加，綜上所述，本文所提出的EnRank算法對于復雜有向加權網絡中關鍵節點的挖掘具有很好的可靠性。

參考文獻（References）：

[1] 徐鳳，朱金福，苗建軍.基于復雜網絡的空鐵復合網絡的魯棒性研究[J].復雜系統與復雜性科學，2015，12（1）：40-45.

[2] Watts D J， Strogatz S H， \"Collective dynamics of 'small-world' networks，\" Nature，1998，393（6）：440-442.

[3] 董兵.航空交通系統的交通復雜性研究[D].成都：西南交通大學，2016.

[4] 程光權，陸永中， 張明星，等.復雜網絡節點重要度評估及網絡脆弱性分析[J].國防科技大學學報，2017，39（1）：120-127.

[5] 陳靜，孫林夫.復雜網絡中節點重要度評估[J].西南交通大學學報，2009，44（3）：426-429.

[6] 段東立，戰仁軍.基于相繼故障信息的網絡節點重要度演化機理分析[J]. 物理學報，2014，63（6）：385-393.

[7] Hu P， Fan W L， Mei S W， \"Identifying node importance incomplex networks，\" Physica A： Stat. Mech. Appl.，2015，429（6）：169-176.

[8] 阮逸潤，老松楊，王竣德，等.基于領域相似度的復雜網絡節點重要度評估算法[J].物理學報，2017，66（3）：365-373.

[9] 馮霞，賈宏璨.考慮節點失效和邊失效的航空網絡魯棒性[J].北京交通大學學報，2021，45（5）：84-92.

[10] Kleinberg J M， \"Authoritative sources in a hyperlinkedenvironment，\" JACM，1999，46（9）：604-632.

[11] Zhou X， Zhang F M， Li K W， Hui X B， Wu H S， \"Findingvital node by node importance evaluation matrix in complex networks，\" Acta Phys. Sin.，2012，61：1-7

[12] Mirzasoleiman Baharan， Babaei Mahmoudreza， Jalili"Mahdi， Safari Mohammadali， \"Cascaded failures in weighted networks，\" Physical review. E， Statistical， nonlinear， and soft matter physics，2011，84（10）.