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

尹榮榮, 尹學(xué)良,崔夢頔, 徐英函

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

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

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

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

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

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

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

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

1.1 基于結(jié)構(gòu)洞的重要度貢獻比例關(guān)系

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

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

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

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

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

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

其中,q為節(jié)點i和節(jié)點j的共同鄰居.考慮到節(jié)點度和節(jié)點鄰居的拓?fù)浣Y(jié)構(gòu)對該節(jié)點的影響,可以將pij記為

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

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

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

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

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

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

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

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

1.3 算法流程

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

2 仿真分析

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

2.1 算法有效性分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法效率分析

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

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

3 結(jié) 論

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