基于網絡熵變率的節點重要性排序方法*

陳 前 王昌達

（江蘇大學計算機科學與通信工程學院 鎮江 212013）

1 引言

幾乎所有的復雜系統（比如社會、生物、信息、技術、交通運輸系統等）都可以表示為網絡［1］。其中，節點代表系統構成要素，節點連邊上的負載信息代表系統要素間的聯系。對網絡中少數關鍵節點的破壞就能導致網絡整體癱瘓。其中，關鍵節點是指相對于網絡中其他節點而言，能更大程度地影響網絡通信或安全功能的特殊節點。因此對網絡中關鍵節點進行保護，能夠大幅度提高網絡的可用性與抗毀性；對社交網絡中的關鍵節點進行引導，能更好地干預網絡輿情的發展。

節點的重要性不僅與網絡拓撲結構有關，也與當前網絡負載狀態有關。在不同的網絡負載狀態下，不同位置的節點會體現出不同的重要性。

目前，基于網絡拓撲的節點重要性評價方法主要可以分成五類：1）基于鄰居節點：這一類方法主要考慮當前節點的臨近節點信息。比如度中心性方法（DC）［2］使用相鄰節點的數量作為節點重要性的度量。這種方法實現簡單，但忽略了鄰居節點自身的影響，因此度中心性方法的準確性不高。2）基于路徑長度：這一類方法主要是通過節點在信息傳遞中所擔任的角色來衡量節點重要性，比如接近中心性方法（CC）［3］通過計算節點與其他節點間的平均距離來衡量節點重要性。這類方法使用全局信息度量節點的重要性，準確性高但計算復雜度也高。3）基于特征向量：特征向量指標是從網絡中節點的地位或聲望角度考慮，將單個節點的聲望看成是所有其它節點聲望的線性組合，從而得到一個線性方程組。該方程組矩陣最大特征值所對應的特征向量就是各個節點的重要性［4］。特征向量中心性方法（EC）［5］和PageRank［6］方法是此類的典型方法。4）基于節點移除和收縮：通過刪除節點或者收縮節點對網絡產生的破壞性來衡量節點的重要性。比如艾新波提出的熵變量方法［7］，該方法將節點的重要性定義為某節點刪除前后網絡熵的變化值，但由于每一次節點刪除后都需要計算網絡熵，導致了算法計算復雜度也變大。5）混合方法：通過綜合前幾類方法以達到對節點重要性更全面的分析。此類方法包括文獻［8］中通過信息熵加權方法，對節點位置屬性和鄰居屬性進行加權來度量節點重要性；文獻［9］中使用一種基于相對熵的綜合評價方法。

基于當前網絡負載變化衡量節點重要性的代表性成果相對較少，其中比較有代表性的成果是我們課題組金甜甜等［10］提出的DPCR（Direct Principal Component Ranking）和CPCR（Comprehensive Principal Component Ranking）方法。此類方法可以根據網絡的拓撲以及網絡中數據包傳輸的方向性對節點的重要性排序。

為了能綜合考慮網絡負載變化和網絡拓撲結構對節點重要性的影響，本文提出一種基于網絡熵變率的MixR（Mix Ranking）節點重要性排序算法。為了驗證該方法的有效性，本文在兩個公開數據集上使用SIR（Susceptible-Infected-Recovered）模型［1］度量節點的影響力，并將其與其他已知的節點重要性排序方法進行比較，實證了MixR 的有效性和準確性。

2 相關概念

本節首先給出流量矩陣的數學模型和基于有向圖的網絡拓撲的中心性方法；然后介紹了網絡熵的幾種形式；最后對SIR 模型的評判標準和評判過程做簡要總結。

2.1 網絡負載的流量矩陣模型

在網絡流量矩陣OD（Origin-Destination）Matrix中，OD 流（k1，k2）的定義是從節點k1（源節點）進入，最后流出節點k2（目標節點）的所有流量的集合［11］。對于一個有著n個節點的網絡，它的網絡流量矩陣共有n n個元素。一般地，用T來表示流量矩陣，用tij表示OD流（i，j），其中矩陣第i行元素的和代表從節點i流出的總流量，矩陣第j 列元素的和就代表著流入節點j的總流量。

2.2 基于網絡拓撲的中心性度量方法

度中心性：有向圖中度中心性分為出度中心性、入度中心性和度中心性，節點的出度就是指以節點為頭的節點數量，入度就是以其為尾的節點數量。節點的度就是節點的出度和入度之和，節點的度中心性值越大，節點能接觸的其他節點越多，一般認為這樣的節點在網絡中越重要。

接近中心性：節點的接近中心性值表示為一個節點到其他節點的平均最短距離的倒數，值越大，節點越接近其他節點，越能更好地控制網絡中信息流動，一般認為這樣的節點越重要。

特征向量中心性：該方法的本質是將一個節點的重要性表達成它的鄰居節點的重要性之和。節點的特征向量中心性值越大，節點連接的鄰居節點越重要，節點本身也就成為一個重要節點。

2.3 半局部中心性方法

節點的半局部中心性方法（semi-local centrality）［12］是一種基于半局部信息的節點重要性排序方法。該方法首先給出節點的兩層鄰居度的定義N(w)，其值為節點w兩跳范圍內鄰居節數量和。在有向圖中，節點的半局部中心性方法只考慮出度，因此將N(w)定義為從節點w出發兩跳范圍內可到達的節點數量，其定義為

其中T(u)是從節點u出發一跳范圍鄰居節點的集合，最終給出節點i的半局部中心性

圖1 擁有七個節點的有向圖

以圖2 為例，計算節點a的半局部中心性，Q(a)out=N(b)out，從節點b出發到達節點g，而節點g可以到達的節點有a，c，d，e，f，所以N(b)out=6，依此類推，我們有以下結果：CLa-out=Q(b)out=N(g)out=6。

圖2 Abilene網絡的拓撲結構

2.4 網絡熵

網絡熵有香農熵［13］、Rényi 熵［14］和Tsallis 熵［15］等多種不同的形式。在Rényi 熵和Tsallis 熵中，參數α可以調節不同概率p 分布對整體結果產生的影響。當α=1 時，Rényi 熵和Tsallis 熵就退化成香農熵；當α＞1 時，由于p 值的范圍是0～1 之間，p 值越小，pa的值越趨近于0，此時高概率事件的分布相比于低概率事件更明顯，因此主要體現的是高概率事件的分布狀態；當α＜0 時，主要體現的是低概率事件的分布狀態。

2.5 SIR模型

SIR模型是一種常用的節點影響力評估模型［1，16］。在SIR 模型中，節點重要性的評判標準一般有：給定時間內感染源感染的節點總數以及感染總數達到穩態時的用時。

在SIR模型中，每一個節點都有3種狀態：1）易感染狀態；2）已感染狀態；3）恢復狀態。這三種狀態節點在所有節點中所占個數分別為S（t），I（t）和R（t）。對于初始受到感染的節點，節點以概率λ感染其它易受感染的節點。在復雜網絡SIR 模型中，假設被感染的節點周圍所有的鄰居節點都有機會被感染。經過t 時間后，將感染態的節點在整個網絡中所占的個數F（t）作為傳播范圍衡量指標。

3 MixR動態節點重要性排序方法

本節首先給出網絡熵變率的定義，并對其原理進行分析，然后在此基礎上設計了MixR算法。

3.1 網絡熵變率

網絡熵可以用來描述網絡安全性能，網絡熵值越小，說明系統的安全性越好［17］。對于網絡中某一項性能來說，可以將其熵值定義為pi，pi是與這項性能相對應狀態出現的概率。

若將一個源節點附近聚集的所有OD流看成是基本狀態，則在節點i附近網絡熵的定義如下：

文獻［17］中利用熵差來反映網絡遭受的攻擊效果。而在本文中，熵差是網絡流量變化導致的網絡熵值的變化，所以單靠熵差無法體現網絡熵隨網絡負載變化的快慢。因此本文給出了網絡熵變率的概念，即用網絡熵值變化的速率來反映網絡流量的變化快慢。

我們選取不同時刻的網絡流量矩陣T1和T2，最終得到節點i附近的網絡熵變率為

在網絡中，大部分流量總是聚集在少量節點附近［18］，這些節點附近的流量變化對節點產生的影響越大，這些節點也被稱為關鍵節點。以網絡熵變率為指標，可以在網絡中快速、準確地找到這些關鍵節點。

3.2 MixR算法

為了兼顧網絡拓撲結構對節點重要性產生的影響，本文在熵變率的基礎上結合了網絡拓撲結構信息，即基于節點出度的半局部中心性方法。半局部中心法能夠衡量節點四跳范圍內的鄰居信息，這種方法比度中心性方法的準確度高，比接近中心性方法和特征向量中心性方法復雜度低。將其與網絡熵變率的方法相結合，能在準確性和復雜性之間實現一個可接受的折中。最終得到的MixR算法是一個動態方法與靜態方法相結合的方法。算法的具體操作過程為：

基于不同時刻的網絡流量矩陣求得節點的網絡熵變率：REC=[r1，r2，…，r3]T，同時基于網絡的鄰接矩陣求出節點的出度半局部中心性：CLout=[c1，c2，…，cn]T，最后將兩者相結合得到MixR的公式：

得到的是最終的節點重要性指標，值越大的元素對應的節點越重要。

以下是算法的偽代碼：輸入網絡的鄰接矩陣A和不同時刻的網絡流量矩陣，輸出由Ranknode表示，我們通過對Ranknode進行排序來得到最終的節點重要性排序序列。

算法：MixR算法

輸入：Traffic1N*N Traffic2N*N AN×N

輸出：Ranknode

1）For i=1 to N do

2） For j=1 to N do

4 實驗

4.1 使用的數據集

本文使用兩個公開數據集來驗證MixR 的有效性，其中一個來自Abilene 網絡［19］，另一個來自GEANT 網絡［20］，這兩個數據集的下載地址是https：//blog.csdn.net/qq_36042551/article/details/103207827。Abilene 網絡擁有12 個PoP 點和30 條邊；GEANT 擁有23 個PoP 點和74 條邊。兩個數據集中采集的流量矩陣之間的最小間隔時間是可調整的。Abilene的最小時間間隔是5min；GEANT 最小時間間隔是15min。

Abilene 網絡和GEANT 網絡的拓撲結構分別見圖2和圖3。

圖3 GEANT網絡的拓撲結構

4.2 實驗方法

本文首先使用DC，CC，EC，半局部中心性算法和MixR 算法對網絡中節點的重要性進行排序，然后使用SIR 模型對排序的結果進行驗證。具體方法是首先將上述各算法得到的排名前6 的節點分別作為網絡的初始傳染源，然后使用SIR 模型進行感染模擬，最后比較傳染源節點在網絡中感染的節點總數和達到穩態時所用的時間。需要強調的是本文網絡熵變率在計算中都是采用的出流量，所以在計算節點的DC值和半局部中心性值時都是采用出度。

4.3 結果分析

實驗得到的節點重要性排序序列會隨著流量矩陣的更新而改變。為了節約篇幅，只給出排名前六的節點變化序列，表1 給出了Abilene 網絡中每隔五分鐘的節點重要性序列的變化，表2 給出了GEANT 網絡中每隔15min 的節點重要性序列的變化。

表1 Abilene網絡的節點重要性變化情況

表2 GEANT網絡的節點重要性變化情況

結合網絡拓撲觀察節點的重要性變化，我們可以發現，雖然網絡中節點的重要性是在不斷變化，網絡中仍然還是存在一個節點的重要區域。在Abilene 網絡中，在下午六點至七點這個時間，重要節點大多數都集中于右邊的區域（圖2 加粗區域）。在GEANT網絡中，在早上八點至九點這段時間，重要節點大多數都集中于中間的區域（圖3 加粗區域）。

表3和表4分別給出了兩個網絡中各種算法的前六名節點排序結果。我們將這些節點作為SIR模型中的感染源進行影響力分析，并比較了幾種方法的差異性，結果見圖4。

表3 Abilene網絡的前六名節點排序結果

表4 GEANT網絡的前六名節點排序結果

圖4 兩個網絡上的SIR模型實驗結果

如圖4（a）所示，在Abilene 網絡中，EC 方法得到的前6 名節點的傳播性能最好，其次就是MixR。EC 的表現如此好是因為特征向量中心性本身就適合于描述節點的長期影響力，如在疾病傳播、謠言擴散中，一個節點的EC 分值較大說明該節點距離傳染源更近的可能性越大［4］。根據我們的節點排序結果，EC 方法得到的排名前6 的節點6，4，11，9，1，12 在網絡中相對分散，而且網絡中只有12 個節點，這導致剩下的節點每個都能找到與自己距離十分相近的感染源。由此，EC 的表現優于我們的方法。但隨著網絡規模的擴大，在GEANT 網絡中，MixR 算法要優于其他4 種方法，這說明MixR 得出的重要節點在規模較大的網絡中處于更為關鍵的位置。

5 結語

節點的重要性不僅與網絡的拓撲結構有關，而且與當前的網絡負載狀態相關，本文提出了網絡熵變率的概念，利用其來研究網絡負載變化對節點重要性的影響。同時，我們利用半局部中心性方法來衡量節點附近的拓撲結構。通過兩者相結合，得到的MixR算法從網絡負載和網絡拓撲兩方面綜合衡量節點重要性，這是一種靜態方法和動態方法相結合的方法。方法的有效性最終也在公開數據集上進行實驗得到了驗證。