陳 前 王昌達(dá)

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

1 引言

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

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

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

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

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

2 相關(guān)概念

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

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

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

2.2 基于網(wǎng)絡(luò)拓?fù)涞闹行男远攘糠椒?/h3>

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

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

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

2.3 半局部中心性方法

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

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

圖1 擁有七個(gè)節(jié)點(diǎn)的有向圖

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

圖2 Abilene網(wǎng)絡(luò)的拓?fù)浣Y(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 時(shí)，Rényi 熵和Tsallis 熵就退化成香農(nóng)熵；當(dāng)α＞1 時(shí)，由于p 值的范圍是0～1 之間，p 值越小，pa的值越趨近于0，此時(shí)高概率事件的分布相比于低概率事件更明顯，因此主要體現(xiàn)的是高概率事件的分布狀態(tài)；當(dāng)α＜0 時(shí)，主要體現(xiàn)的是低概率事件的分布狀態(tài)。

2.5 SIR模型

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

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

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

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

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

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

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

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

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

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

3.2 MixR算法

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

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

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

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

算法：MixR算法

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

輸出：Ranknode

1）For i=1 to N do

2） For j=1 to N do

4 實(shí)驗(yàn)

4.1 使用的數(shù)據(jù)集

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

Abilene 網(wǎng)絡(luò)和GEANT 網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)分別見圖2和圖3。

圖3 GEANT網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)

4.2 實(shí)驗(yàn)方法

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

4.3 結(jié)果分析

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

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

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

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

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

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

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

圖4 兩個(gè)網(wǎng)絡(luò)上的SIR模型實(shí)驗(yàn)結(jié)果

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

5 結(jié)語

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