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

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

2(河北省特種光纖與光纖傳感重點(diǎn)實(shí)驗(yàn)室,河北秦皇島066004)

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

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

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

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

1 節(jié)點(diǎn)重要度評(píng)估方法

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

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

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

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

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

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

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

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

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

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

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

1.2 基于重要度貢獻(xiàn)的節(jié)點(diǎn)重要度評(píng)價(jià)

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

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

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

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

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

1.3 算法流程

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

2 仿真分析

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

2.1 算法有效性分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 算法效率分析

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

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

3 結(jié) 論

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