基于重要度貢獻的無標度網絡節點評估方法*

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

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

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

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

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

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

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

1 節點重要度評估方法

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

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

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

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

則節點i的度可以記為

結合節點的度,節點i的鄰接度可表示為

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

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

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

因此可得出,節點i的結構洞重要性指標Li為節點i的約束系數與網絡中所有節點的約束系數的比值,即:

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

1.2 基于重要度貢獻的節點重要度評價

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

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

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

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

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

1.3 算法流程

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

2 仿真分析

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

2.1 算法有效性分析

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

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

Table 1 Node importance evaluation results in the scale-free network表1 無標度網絡節點重要度評估結果

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

2.2 在網絡的蓄意攻擊中進一步驗證

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

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

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

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

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

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

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

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

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

2.3 算法效率分析

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

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

3 結 論

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