基于重要度貢獻的無標度網(wǎng)絡節(jié)點評估方法*

尹榮榮, 尹學良,崔夢頔, 徐英函

1(燕山大學信息科學與工程學院,河北秦皇島066004)

2(河北省特種光纖與光纖傳感重點實驗室,河北秦皇島066004)

無標度網(wǎng)絡[1]是度分布服從冪律分布的一種復雜網(wǎng)絡,被廣泛應用于智慧城市、環(huán)境監(jiān)測、火災探測和醫(yī)療保險等多個領域.研究表明:相比于隨機網(wǎng)絡,在面臨網(wǎng)絡的隨機攻擊時,無標度網(wǎng)絡具有更好的抗毀性.可對于網(wǎng)絡的蓄意攻擊,無標度網(wǎng)絡卻顯得非常脆弱.因此,針對無標度網(wǎng)絡的節(jié)點重要度評估問題[2]就顯得尤為重要.通過節(jié)點重要度評估,能夠在規(guī)模龐大、結構復雜的網(wǎng)絡中準確、快速地找到關鍵節(jié)點,并通過對關鍵節(jié)點的重點保護,以提高整個網(wǎng)絡的可靠性.

節(jié)點的中心性[3]是衡量節(jié)點重要性的常用方法,其中,度指標[4]是最基本的中心性指標,但是未考慮到節(jié)點的全局重要性,無法找到橋接節(jié)點這樣的關鍵節(jié)點.與其相比,介數(shù)指標[5,6]利用節(jié)點到達網(wǎng)絡其余節(jié)點的最短路徑數(shù)目,從全局角度評價節(jié)點的重要性,能夠有效判斷出網(wǎng)絡中的橋接節(jié)點.但該方法的時間復雜度較高,不適用于大型網(wǎng)絡.也有學者提出了一些新的網(wǎng)絡中心性指標:文獻[7]基于節(jié)點在整個網(wǎng)絡中位置的重要性,利用K核分解的方法提出了節(jié)點重要度評估指標,該指標相比于度、介數(shù)更能準確識別網(wǎng)絡中影響力最大的節(jié)點,且時間復雜度低,但并不適用于存在多個傳播源的復雜網(wǎng)絡.文獻[8]提出了一種基于生成樹數(shù)目的節(jié)點刪除法,定義最重要的節(jié)點為刪除該節(jié)點使得生成樹數(shù)目最小,但此方法沒有考慮到相鄰節(jié)點的影響,使得評估結果不準確.文獻[9]綜合考慮了節(jié)點效率、節(jié)點度值和相鄰節(jié)點重要度貢獻,提出一種重要度評價矩陣來確定復雜網(wǎng)絡關鍵節(jié)點的方法,認為節(jié)點間最直接、最重要的依賴關系存在于鄰接節(jié)點之間,卻忽視了相互依賴程度高的非鄰接節(jié)點.文獻[10]則在中心度和節(jié)點刪除法的基礎上提出了連通中心度來度量復雜網(wǎng)絡中節(jié)點的影響力,該方法同時考慮了節(jié)點在網(wǎng)絡結構中位置的重要性以及節(jié)點對網(wǎng)絡局部連通性的影響,較全面地刻畫了節(jié)點的重要程度,但是其復雜度較高.

雖然以上方法都能有效找出網(wǎng)絡中的核心節(jié)點,但是關鍵節(jié)點排序問題不能僅局限于網(wǎng)絡中的核心節(jié)點,有一類處于結構洞位置的節(jié)點同樣值得我們關注.結構洞是 Burt[11]研究社會網(wǎng)絡中競爭關系時提出的經(jīng)典社會學理論,結構洞體現(xiàn)了兩個節(jié)點間的非冗余關系,例如,對于3個節(jié)點A,B,C來說,如果A和B關聯(lián),B和C關聯(lián),但是A和C不關聯(lián),此時A和C之間存在一個結構洞,并且擁有較多結構洞的網(wǎng)絡節(jié)點更有利于信息的傳播.在復雜網(wǎng)絡中,處于結構洞位置的節(jié)點并不一定是網(wǎng)絡的核心節(jié)點,但是因為具有結構洞的特征,使得其在網(wǎng)絡信息傳輸中發(fā)揮重大作用,成為網(wǎng)絡的關鍵節(jié)點.文獻[12]基于結構洞指數(shù)構建了節(jié)點的重要性矩陣,通過考慮3個節(jié)點之間的結構關系來確定節(jié)點的重要性,克服了單獨分析各個節(jié)點重要性的不足.文獻[13]提出一種基于節(jié)點及其鄰域結構洞的評估節(jié)點重要度的方法,該方法綜合考慮了節(jié)點的鄰居數(shù)量及其與鄰居間的拓撲結構,有利于發(fā)現(xiàn)在具有強社團結構下最具影響力的節(jié)點.文獻[14]提出一種基于改進結構洞的節(jié)點重要度排序方法,該方法無需考慮網(wǎng)絡的全局結構信息,僅利用節(jié)點的度和近鄰信息就能有效識別出整個網(wǎng)絡中的關鍵節(jié)點.

當前,對于單獨利用結構洞特征或中心性特征來評估節(jié)點重要度的研究已較為深入,但對于綜合考慮結構洞和中心性特征的研究目前并不多.文獻[15]結合結構洞和接近中心性得到節(jié)點結構洞的影響矩陣,從全局和局部的角度綜合評估節(jié)點的重要程度,但計算網(wǎng)絡接近中心性時,其復雜度較高.文獻[16,17]分別提出了基于多屬性決策的節(jié)點重要度排序方法,通過融合結構洞與節(jié)點的度、介數(shù)、信息指數(shù)、接近中心性、流介數(shù)中心性、子圖中心性等評價指標,避免了節(jié)點重要度評估的片面性.但算法均復雜,且易造成標準不統(tǒng)一的情況.文獻[18]引入了排序?qū)W習的方法,利用ListNet的排序?qū)W習方法,融合介數(shù)中心性、結構洞的約束系數(shù)等7個指標,得到一種綜合多指標評價節(jié)點重要度的方法.此方法判定出的關鍵節(jié)點具有較高的傳播能力,對于現(xiàn)實復雜網(wǎng)絡中的實用性較強,但是算法仍較為復雜.基于以上考慮,本文針對無標度網(wǎng)絡的節(jié)點重要度評估問題,利用構建節(jié)點重要度貢獻矩陣的思想,提出一種節(jié)點重要度排序的新方法.該方法利用相鄰節(jié)點的結構洞重要性指標值和K核重要性指標值得到節(jié)點間的重要度貢獻關系,同時,以節(jié)點自身K核重要性表征節(jié)點的全局位置信息,在分析網(wǎng)絡局部重要性的基礎上,結合全局重要性,使得節(jié)點的重要度評價更加全面,節(jié)點重要度評估結果也更為準確.通過在無標度網(wǎng)絡中的仿真分析,驗證了該方法的準確性和有效性.并且與其他算法比較,在應對網(wǎng)絡的蓄意攻擊時,此方法較為有效,且時間復雜度較低,適用于大規(guī)模的無標度網(wǎng)絡中節(jié)點重要度的評估.

1 節(jié)點重要度評估方法

本文將利用構建節(jié)點重要度貢獻矩陣的思想,融合網(wǎng)絡的結構洞特征和中心性特征.本文運用K核重要性表征節(jié)點在網(wǎng)絡信息傳播中所起的作用,將相鄰節(jié)點的結構洞重要性指標和K核重要性指標表征相鄰節(jié)點的重要度貢獻,體現(xiàn)節(jié)點的局部重要性.同時,節(jié)點自身的K核重要性體現(xiàn)節(jié)點在網(wǎng)絡中的全局位置信息,綜合相鄰節(jié)點間的重要度貢獻和節(jié)點自身的位置信息,最終得到節(jié)點的重要度.

1.1 基于結構洞的重要度貢獻比例關系

網(wǎng)絡是由節(jié)點和邊組成的統(tǒng)一整體,節(jié)點并非孤立存在,節(jié)點的重要度必然受到相鄰節(jié)點的影響,這種節(jié)點間的影響關系可以通過節(jié)點間的重要度貢獻的形式進行描述.但是與以往研究的重要度貢獻關系不同,這里在研究相鄰節(jié)點間的重要度貢獻關系時將引入結構洞特征,利用節(jié)點間的結構洞重要性來確定節(jié)點對其相鄰節(jié)點的重要度貢獻比例.

設圖G=(V,E)是一個無自環(huán)的無向網(wǎng)絡,共有n個節(jié)點、m條邊,其中,V={υ1,υ2,…,υn}是網(wǎng)絡中所有節(jié)點的集合,E={e1,e2,…,em}且E?V×V是節(jié)點間邊的集合.鄰接矩陣記為An×n=(aij)n×n,其中,

則節(jié)點i的度可以記為

結合節(jié)點的度,節(jié)點i的鄰接度可表示為

其中,Γ(i)為節(jié)點i的鄰居的集合.

網(wǎng)絡的約束系數(shù)可以衡量網(wǎng)絡中節(jié)點形成結構洞時所受到的相鄰節(jié)點的約束情況,是測量結構洞的一種指標.網(wǎng)絡的約束系數(shù)越小,結構洞程度越大,節(jié)點就越重要.約束系數(shù)可表示為

其中,q為節(jié)點i和節(jié)點j的共同鄰居.考慮到節(jié)點度和節(jié)點鄰居的拓撲結構對該節(jié)點的影響,可以將pij記為

因此可得出,節(jié)點i的結構洞重要性指標Li為節(jié)點i的約束系數(shù)與網(wǎng)絡中所有節(jié)點的約束系數(shù)的比值,即:

將網(wǎng)絡中所有的節(jié)點j按照一定的比例值將自身的重要度貢獻分配給與其相鄰節(jié)點i,然后將網(wǎng)絡中的全部節(jié)點對其鄰居節(jié)點的重要度貢獻比例值均在矩陣中表示出來,再結合網(wǎng)絡的鄰接矩陣An×n=(aij)n×n,就形成了節(jié)點重要度貢獻矩陣,記作矩陣LC:

1.2 基于重要度貢獻的節(jié)點重要度評價

節(jié)點的局部信息和全局信息是評價節(jié)點重要度的兩個關鍵因素.節(jié)點重要度貢獻矩陣LC從節(jié)點的結構洞重要性入手,反映了相鄰節(jié)點間的影響關系,在一定程度上可表征節(jié)點的局部相鄰信息.節(jié)點的K核指標考慮的是節(jié)點在整個網(wǎng)絡中的信息傳播的影響力,是依據(jù)網(wǎng)絡的中心性特征來評估節(jié)點重要性.相比于節(jié)點效率、介數(shù)等中心性指標,其時間復雜度低,適合用于大型網(wǎng)絡,可表征節(jié)點的全局位置信息.這里引入混合度分解的方法[19]獲取K核指標.

在獲知K核指標后,可得出節(jié)點i的K核重要性Mi:

利用節(jié)點的結構洞重要性構建的節(jié)點重要度貢獻矩陣LC,已經(jīng)從一定程度上反映了相鄰節(jié)點間的重要度貢獻比例關系,考慮到節(jié)點的K核重要性表征了節(jié)點的位置信息,于是,可通過融合相鄰節(jié)點的K核重要性指標值優(yōu)化LC中的重要度貢獻比例值,得到更為全面體現(xiàn)相鄰節(jié)點間重要度貢獻關系的節(jié)點重要度評價矩陣HC:

運用節(jié)點重要性評價矩陣HC中相鄰節(jié)點間的重要度貢獻關系,再結合節(jié)點自身的K核重要性,即可得到節(jié)點i的重要度Ci:

通過公式(10)可知,Ci由節(jié)點i的所有相鄰節(jié)點的重要度貢獻值之和與節(jié)點i的K核重要性指標值的乘積構成,說明一個節(jié)點的重要度取決于該節(jié)點自身的K核重要性指標值以及相鄰節(jié)點K核重要性指標值和結構洞重要性指標值,它綜合了節(jié)點的全局重要性和局部重要性,全面評估了節(jié)點的重要度,提高了評估的準確性.

1.3 算法流程

基于重要度貢獻的節(jié)點重要度評估方法,綜合考慮相鄰節(jié)點的K核重要性指標和結構洞重要性指標來確定相鄰節(jié)點的重要度貢獻,獲得節(jié)點重要度評價矩陣HC.在此基礎上,結合節(jié)點自身的K核重要性得到節(jié)點的重要度Ci,運用此方法綜合全局和局部兩個方面對復雜網(wǎng)絡中節(jié)點的重要度進行評估,其評估結果較為準確.節(jié)點重要度評估方法具體步驟如圖1所示.

2 仿真分析

本文選擇具有代表性的BA無標度拓撲網(wǎng)絡[20]進行仿真分析,并進行了如下3類實驗:實驗1運用30個節(jié)點的網(wǎng)絡結構進行驗證,說明所提出方法的有效性;實驗 2模擬網(wǎng)絡的蓄意攻擊,進一步驗證所提方法在不同網(wǎng)絡規(guī)模下的有效性(重點對比100個節(jié)點的小規(guī)模網(wǎng)絡以及1 000個節(jié)點的大規(guī)模網(wǎng)絡中的情況);實驗3統(tǒng)計各方法進行節(jié)點重要度評估的運行時間,驗證所提方法的計算效率.

2.1 算法有效性分析

本次仿真假設將節(jié)點隨機分布在500m×500m的方形區(qū)域,節(jié)點數(shù)目設定為30個,拓撲圖如圖2所示.首先,利用本文方法與其他算法可以得到各節(jié)點的節(jié)點重要度,評估結果見表 1.下面結合拓撲圖進行分析,將本文方法與其他算法進行對比.

通過分析拓撲圖(如圖 1所示)與無標度網(wǎng)絡節(jié)點重要度評估結果(見表 1)可知:節(jié)點v11,v22,v27的連接度均為 7,但顯然它們的重要程度不一樣,v23的連接度雖然只有5,但它卻處在網(wǎng)絡信息傳輸?shù)年P鍵位置,重要程度明顯高于v11,v22,v27,因此,僅依靠節(jié)點的連接度無法準確評估節(jié)點重要性.采用鄰域結構洞法判定關鍵節(jié)點,雖然此方法通過分析節(jié)點的度及其鄰域結構改進了結構洞指標,但是并未考慮到節(jié)點的中心性特征,如拓撲圖所示:雖然v23比v27存在較多的結構洞,但是v27的連接度卻比v23的連接度大.重要度矩陣法雖然結合了網(wǎng)絡的局部屬性和全局屬性,但是此方法并未從結構洞的角度考慮關鍵節(jié)點,有些結構洞的關鍵節(jié)點對于在網(wǎng)絡中的重要度很大,如節(jié)點v11,通過拓撲圖可以看出此節(jié)點擁有較多結構洞.介數(shù)方法雖然能夠很好地體現(xiàn)在網(wǎng)絡信息傳輸過程中的關鍵程度,但是一些位置重要程度相近的節(jié)點,如v14,v19,v24,仍需進一步結合節(jié)點的局部信息來評估,并且此方法的時間復雜度高.節(jié)點刪除法中,由于刪除節(jié)點v1,v6,v7,v19,v21,導致網(wǎng)絡不再連通,使得刪除這些節(jié)點后生成樹數(shù)目為 0,相應的節(jié)點重要度為 1,從而無法進一步區(qū)分這些節(jié)點的重要度.但是由拓撲圖可看出,這些節(jié)點的重要程度明顯不同.

Table 1 Node importance evaluation results in the scale-free network表1 無標度網(wǎng)絡節(jié)點重要度評估結果

本文所提出的方法則克服了以上方法的不足,它綜合節(jié)點中心性和結構洞兩個角度,同時綜合考慮節(jié)點的位置信息(全局重要性)和相鄰節(jié)點的影響(局部重要性),通過此方法可提高評估節(jié)點重要度準確性,顯著地區(qū)分關鍵節(jié)點.表1中,通過本方法判定出的前10個關鍵節(jié)點與其他方法判定出的關鍵節(jié)點大致相同,各方法節(jié)點重要度排序因為側重點不同存在差異.如通過評估結果可看出,節(jié)點v22的重要度最大.依據(jù)拓撲圖,節(jié)點v22的連接度較大,則K核重要性較大,且擁有較多結構洞,同時與其相連的v23,v27,v28均具有較大連接度,可體現(xiàn)出此節(jié)點處于網(wǎng)絡傳輸信息的重要位置,屬于重要的橋接節(jié)點.從表 1還看出,本方法進一步區(qū)分了v14,v19,v24和v1,v6,v7,v19,v21這些節(jié)點的重要程度,克服了介數(shù)法和節(jié)點刪除法的不足.通過對比,本文所提方法是有效的,可提高評估節(jié)點重要程度的精度,能顯著區(qū)分無標度網(wǎng)絡中特殊節(jié)點間的重要程度.

2.2 在網(wǎng)絡的蓄意攻擊中進一步驗證

為進一步驗證本方法的準確性,模擬網(wǎng)絡的蓄意攻擊,即有針對性地移除網(wǎng)絡中重要的節(jié)點,可利用蓄意攻擊前后網(wǎng)絡最大連通分支節(jié)點數(shù)的變化,分析網(wǎng)絡遭受攻擊后對網(wǎng)絡魯棒性的影響.首先,統(tǒng)計在不同規(guī)模(節(jié)點總數(shù)從 50～1000)的網(wǎng)絡結構下,移除由這幾種算法各自判斷出的前 10%的關鍵節(jié)點后,網(wǎng)絡最大連通分支節(jié)點數(shù)占網(wǎng)絡總節(jié)點數(shù)的比例.如圖3所示.

由圖3可知,隨著網(wǎng)絡規(guī)模的增大,移除網(wǎng)絡的前10%的關鍵節(jié)點對于網(wǎng)絡連通性的影響程度也隨之變大.這表明關鍵節(jié)點的有效評估不僅對小規(guī)模網(wǎng)絡魯棒性有重要影響,對大規(guī)模無標度網(wǎng)絡更為重要.并且在不同網(wǎng)絡規(guī)模下,移除本文方法所判斷出的前 10%的關鍵節(jié)點,網(wǎng)絡的最大連通分支占網(wǎng)絡總節(jié)點數(shù)的比例總是小于重要度矩陣法,說明此方法判斷出的關鍵節(jié)點對于網(wǎng)絡的魯棒性影響更大.同時,此方法與鄰域結構洞法、介數(shù)法、節(jié)點刪除法相比,對于網(wǎng)絡的連通性影響程度較為接近.

為進一步區(qū)分幾種方法判斷出的關鍵節(jié)點對網(wǎng)絡連通性的影響程度,下面分別討論在小規(guī)模網(wǎng)絡(100個節(jié)點)以及大規(guī)模網(wǎng)絡(1 000個節(jié)點)下,依次移除前10%的關鍵節(jié)點后對于網(wǎng)絡連通性的影響.

圖4給出了在100個節(jié)點的小規(guī)模無標度網(wǎng)絡中,依次移除各方法評估出的前10%的關鍵節(jié)點,網(wǎng)絡最大連通分支節(jié)點數(shù)的變化情況.

通過分析圖 4的變化趨勢可知,與其他算法相比,本文方法的網(wǎng)絡最大連通分支節(jié)點數(shù)下降速度最快,當前6個關鍵節(jié)點失效時,本文方法的最大連通分支節(jié)點數(shù)已經(jīng)少于50個(原網(wǎng)絡規(guī)模的1/2),而其他算法中的最大連通分支節(jié)點數(shù)仍多于 50個.因此,相對其他算法而言,若依據(jù)本文方法判斷出的關鍵節(jié)點對小規(guī)模網(wǎng)絡實施蓄意攻擊,網(wǎng)絡結構將快速瓦解.從而表明,本文方法對小規(guī)模無標度網(wǎng)絡中節(jié)點的重要性能夠進行有效評估.

圖5給出了在1 000個節(jié)點的大規(guī)模無標度網(wǎng)絡中,依次移除各方法評估出的前10%的關鍵節(jié)點,網(wǎng)絡最大連通分支節(jié)點數(shù)的變化情況.

由圖5可知,對于規(guī)模為1 000的無標度網(wǎng)絡,甚至只需移除各種方法判斷出的前4%(40個)的關鍵節(jié)點,就足以使整個網(wǎng)絡崩潰.這進一步驗證了對于大規(guī)模無標度網(wǎng)絡而言,關鍵節(jié)點對于網(wǎng)絡魯棒性的影響更為明顯.并且在前 4%的關鍵點移除過程中,與其他算法相比,依次移除用本文方法得到的關鍵節(jié)點,網(wǎng)絡最大連通分支節(jié)點數(shù)下降速度最快,明顯優(yōu)于重要度矩陣法和鄰域結構洞法,且略優(yōu)于介數(shù)法和節(jié)點刪除法.為此,下面進一步分析在1 000個節(jié)點的網(wǎng)絡規(guī)模下,依次移除前10個關鍵節(jié)點后的網(wǎng)絡最大連通分支變化情況,如圖6所示.

由圖6可見,依次移除各方法評估出的前10個關鍵節(jié)點,本文方法中的最大連通分支節(jié)點數(shù)的下降速度明顯優(yōu)于其他算法,在移除10個關鍵節(jié)點后,網(wǎng)絡最大連通分支節(jié)點數(shù)已經(jīng)降至500(原網(wǎng)絡規(guī)模的1/2)以下;介數(shù)法和節(jié)點刪除法的網(wǎng)絡最大連通分支節(jié)點數(shù)介于 600～700之間;重要度矩陣法和鄰域結構洞法的網(wǎng)絡最大連通分支節(jié)點數(shù)介于800～900之間.因此,相對其他算法而言,若依據(jù)本文方法判斷出的關鍵節(jié)點對大規(guī)模網(wǎng)絡展開蓄意攻擊,只需攻擊極少量的關鍵節(jié)點,網(wǎng)絡結構便會快速瓦解,從而表明本文方法對大規(guī)模無標度網(wǎng)絡中節(jié)點的重要性也能夠進行有效評估.

綜上所述,無論無標度網(wǎng)絡規(guī)模如何變化,相比于其他算法,本文方法判斷出的關鍵節(jié)點對于網(wǎng)絡的連通性影響更為明顯.當然,依據(jù)此方法對網(wǎng)絡中的關鍵節(jié)點進行針對性的保護,便能有效地抵御網(wǎng)絡的蓄意攻擊,增強網(wǎng)絡的魯棒性.因此,通過在網(wǎng)絡蓄意攻擊中的仿真過程,進一步驗證了本文方法的有效性.

2.3 算法效率分析

在微機上運行MATLAB程序,分別用本文方法、鄰域結構洞法、介數(shù)法、重要度矩陣法、節(jié)點刪除法對不同規(guī)模的無標度網(wǎng)絡進行節(jié)點重要度評估,統(tǒng)計出運行的時間如圖7所示.

隨著網(wǎng)絡規(guī)模的擴大,本文方法的運行時間與鄰域結構洞法的運行時間基本相同,且明顯少于另外 3種算法,評估400個節(jié)點的重要度時本文方法運行時間為重要度矩陣法的16.5%,為介數(shù)法的4.3%,為節(jié)點刪除法的3.1%.這說明本文提出的節(jié)點重要度評估方法是有效的,同時對于大型的網(wǎng)絡具有理想的計算能力.

3 結 論

針對無標度網(wǎng)絡節(jié)點重要度評估的問題,提出了一種基于節(jié)點間重要度貢獻關系來確定無標度網(wǎng)絡中的關鍵節(jié)點的新方法.經(jīng)過理論分析及仿真分析算法效率可知:該方法的時間復雜度低,適用于大型網(wǎng)絡的節(jié)點重要度評估.仿真實驗分析表明:該方法可行有效,能夠找到網(wǎng)絡中同時具有中心性和結構洞特征的關鍵節(jié)點,克服其他算法的不足,使得評估節(jié)點重要度更加準確.依據(jù)該方法得到的節(jié)點重要度排序?qū)W(wǎng)絡進行蓄意攻擊,可以使網(wǎng)絡結構快速瓦解.尤其是大型網(wǎng)絡,僅攻擊少量關鍵節(jié)點即可損毀整個網(wǎng)絡.因此,利用該方法識別出的關鍵節(jié)點也可有效地幫助我們設計網(wǎng)絡的防護策略,提高網(wǎng)絡的抗毀性.