基于網(wǎng)絡(luò)熵變率的節(jié)點重要性排序方法*

陳 前 王昌達

（江蘇大學(xué)計算機科學(xué)與通信工程學(xué)院 鎮(zhèn)江 212013）

1 引言

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

節(jié)點的重要性不僅與網(wǎng)絡(luò)拓撲結(jié)構(gòu)有關(guān)，也與當(dāng)前網(wǎng)絡(luò)負載狀態(tài)有關(guān)。在不同的網(wǎng)絡(luò)負載狀態(tài)下，不同位置的節(jié)點會體現(xiàn)出不同的重要性。

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

基于當(dāng)前網(wǎng)絡(luò)負載變化衡量節(jié)點重要性的代表性成果相對較少，其中比較有代表性的成果是我們課題組金甜甜等［10］提出的DPCR（Direct Principal Component Ranking）和CPCR（Comprehensive Principal Component Ranking）方法。此類方法可以根據(jù)網(wǎng)絡(luò)的拓撲以及網(wǎng)絡(luò)中數(shù)據(jù)包傳輸?shù)姆较蛐詫?jié)點的重要性排序。

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

2 相關(guān)概念

本節(jié)首先給出流量矩陣的數(shù)學(xué)模型和基于有向圖的網(wǎng)絡(luò)拓撲的中心性方法；然后介紹了網(wǎng)絡(luò)熵的幾種形式；最后對SIR 模型的評判標(biāo)準(zhǔn)和評判過程做簡要總結(jié)。

2.1 網(wǎng)絡(luò)負載的流量矩陣模型

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

2.2 基于網(wǎng)絡(luò)拓撲的中心性度量方法

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

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

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

2.3 半局部中心性方法

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

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

圖1 擁有七個節(jié)點的有向圖

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

圖2 Abilene網(wǎng)絡(luò)的拓撲結(jié)構(gòu)

2.4 網(wǎng)絡(luò)熵

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

2.5 SIR模型

SIR模型是一種常用的節(jié)點影響力評估模型［1，16］。在SIR 模型中，節(jié)點重要性的評判標(biāo)準(zhǔn)一般有：給定時間內(nèi)感染源感染的節(jié)點總數(shù)以及感染總數(shù)達到穩(wěn)態(tài)時的用時。

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

3 MixR動態(tài)節(jié)點重要性排序方法

本節(jié)首先給出網(wǎng)絡(luò)熵變率的定義，并對其原理進行分析，然后在此基礎(chǔ)上設(shè)計了MixR算法。

3.1 網(wǎng)絡(luò)熵變率

網(wǎng)絡(luò)熵可以用來描述網(wǎng)絡(luò)安全性能，網(wǎng)絡(luò)熵值越小，說明系統(tǒng)的安全性越好［17］。對于網(wǎng)絡(luò)中某一項性能來說，可以將其熵值定義為pi，pi是與這項性能相對應(yīng)狀態(tài)出現(xiàn)的概率。

若將一個源節(jié)點附近聚集的所有OD流看成是基本狀態(tài)，則在節(jié)點i附近網(wǎng)絡(luò)熵的定義如下：

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

我們選取不同時刻的網(wǎng)絡(luò)流量矩陣T1和T2，最終得到節(jié)點i附近的網(wǎng)絡(luò)熵變率為

在網(wǎng)絡(luò)中，大部分流量總是聚集在少量節(jié)點附近［18］，這些節(jié)點附近的流量變化對節(jié)點產(chǎn)生的影響越大，這些節(jié)點也被稱為關(guān)鍵節(jié)點。以網(wǎng)絡(luò)熵變率為指標(biāo)，可以在網(wǎng)絡(luò)中快速、準(zhǔn)確地找到這些關(guān)鍵節(jié)點。

3.2 MixR算法

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

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

得到的是最終的節(jié)點重要性指標(biāo)，值越大的元素對應(yīng)的節(jié)點越重要。

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

算法：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 使用的數(shù)據(jù)集

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

Abilene 網(wǎng)絡(luò)和GEANT 網(wǎng)絡(luò)的拓撲結(jié)構(gòu)分別見圖2和圖3。

圖3 GEANT網(wǎng)絡(luò)的拓撲結(jié)構(gòu)

4.2 實驗方法

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

4.3 結(jié)果分析

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

表1 Abilene網(wǎng)絡(luò)的節(jié)點重要性變化情況

表2 GEANT網(wǎng)絡(luò)的節(jié)點重要性變化情況

結(jié)合網(wǎng)絡(luò)拓撲觀察節(jié)點的重要性變化，我們可以發(fā)現(xiàn)，雖然網(wǎng)絡(luò)中節(jié)點的重要性是在不斷變化，網(wǎng)絡(luò)中仍然還是存在一個節(jié)點的重要區(qū)域。在Abilene 網(wǎng)絡(luò)中，在下午六點至七點這個時間，重要節(jié)點大多數(shù)都集中于右邊的區(qū)域（圖2 加粗區(qū)域）。在GEANT網(wǎng)絡(luò)中，在早上八點至九點這段時間，重要節(jié)點大多數(shù)都集中于中間的區(qū)域（圖3 加粗區(qū)域）。

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

表3 Abilene網(wǎng)絡(luò)的前六名節(jié)點排序結(jié)果

表4 GEANT網(wǎng)絡(luò)的前六名節(jié)點排序結(jié)果

圖4 兩個網(wǎng)絡(luò)上的SIR模型實驗結(jié)果

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

5 結(jié)語

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