利用節(jié)點(diǎn)效率評(píng)估地理網(wǎng)格網(wǎng)絡(luò)的魯棒性*

王蕾蕾，林中材，潘佳慶，楊孔慶，鄒衛(wèi)東

(集美大學(xué) 理學(xué)院，福建 廈門 361021)

1 引 言

自1999年美國(guó)圣母大學(xué)物理系Barabási教授及其博士生Albert提出網(wǎng)絡(luò)的無(wú)標(biāo)度性質(zhì)以后，復(fù)雜網(wǎng)絡(luò)理論發(fā)展迅速且應(yīng)用廣泛，從Internet到WWW網(wǎng)絡(luò)，從大型電力網(wǎng)絡(luò)到全球交通網(wǎng)絡(luò)，從科研合作網(wǎng)絡(luò)到各種經(jīng)濟(jì)、政治、社會(huì)關(guān)系網(wǎng)絡(luò)等。隨著復(fù)雜網(wǎng)絡(luò)研究的深入，復(fù)雜網(wǎng)絡(luò)的抗毀性研究的重大意義和應(yīng)用價(jià)值日益凸顯出來(lái)，由于網(wǎng)絡(luò)的抗毀性與系統(tǒng)的可靠性密切相關(guān)［1］，而大部分復(fù)雜網(wǎng)絡(luò)是由少數(shù)集散節(jié)點(diǎn)主控的系統(tǒng)。因此，確定合理的評(píng)估指標(biāo)，發(fā)掘網(wǎng)絡(luò)中的重要節(jié)點(diǎn)具有重要的實(shí)用價(jià)值，尤其是對(duì)各種具體的實(shí)際網(wǎng)絡(luò)，更能針對(duì)性的分析網(wǎng)絡(luò)性質(zhì)，制定正確的策略和措施。

評(píng)價(jià)復(fù)雜網(wǎng)絡(luò)中節(jié)點(diǎn)重要性的方法很多，但其本質(zhì)均是源于圖論以及基于圖的數(shù)據(jù)挖掘，對(duì)應(yīng)于圖論中的關(guān)鍵節(jié)點(diǎn)和關(guān)鍵邊問(wèn)題［2］。本文研究的是與地理距離有關(guān)的網(wǎng)格網(wǎng)絡(luò)，采用節(jié)點(diǎn)效率指標(biāo)來(lái)衡量網(wǎng)絡(luò)節(jié)點(diǎn)的重要性。用節(jié)點(diǎn)效率對(duì)節(jié)點(diǎn)重要性進(jìn)行評(píng)估既考慮了網(wǎng)絡(luò)的局部影響性，又考慮了網(wǎng)絡(luò)的全局影響性。在一定攻擊策略下，文獻(xiàn)［1］通過(guò)度量網(wǎng)絡(luò)不連通時(shí)失效節(jié)點(diǎn)的比例來(lái)衡量網(wǎng)絡(luò)功能的魯棒性。文獻(xiàn)［3］和文獻(xiàn)［4］采用網(wǎng)絡(luò)中連通節(jié)點(diǎn)所占的比例和節(jié)點(diǎn)對(duì)之間最短路徑的分布來(lái)衡量網(wǎng)絡(luò)的魯棒性，認(rèn)為連通節(jié)點(diǎn)的比例值越大，節(jié)點(diǎn)之間最短路徑越短，該網(wǎng)絡(luò)的可靠性越強(qiáng)。文獻(xiàn)［5］用最大連通圖的相對(duì)大小和平均路徑長(zhǎng)度L與去除節(jié)點(diǎn)數(shù)占原始網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的比例f的關(guān)系來(lái)度量網(wǎng)絡(luò)的魯棒性。文獻(xiàn)［6］以節(jié)點(diǎn)刪除造成全網(wǎng)絡(luò)效率下降程度來(lái)度量網(wǎng)絡(luò)的魯棒性．本文采用文獻(xiàn)［1］提出的度量網(wǎng)絡(luò)不連通時(shí)失效節(jié)點(diǎn)的比例來(lái)衡量與地理距離有關(guān)的網(wǎng)格網(wǎng)絡(luò)的魯棒性。通過(guò)實(shí)驗(yàn)分析驗(yàn)證其有效性和可行性。

2 復(fù)雜網(wǎng)絡(luò)功能魯棒性的評(píng)定

2．1問(wèn)題的提出

隨著科學(xué)技術(shù)的發(fā)展，交通工具的不斷推陳出新，速度變得越來(lái)越快，世界變得越來(lái)越小，人類越來(lái)越希望自然界以簡(jiǎn)單清晰的姿態(tài)呈現(xiàn)出來(lái)，例如沿著一條公路少過(guò)幾個(gè)路口，少等幾個(gè)紅綠燈、少換幾次交通工具就能到達(dá)目的地;如何確定一個(gè)城市中交警的執(zhí)勤點(diǎn)，保證能在有效的時(shí)間內(nèi)到達(dá)報(bào)警點(diǎn)或成功攔截逃犯;如何為商場(chǎng)、大型超市選址，在滿足更多市民需求的同時(shí)獲取最大商業(yè)價(jià)值等。節(jié)點(diǎn)效率表達(dá)了一個(gè)節(jié)點(diǎn)與其他節(jié)點(diǎn)的平均接近程度。節(jié)點(diǎn)效率越高，表明在最短路徑上經(jīng)過(guò)其他節(jié)點(diǎn)的個(gè)數(shù)就越少，向其他節(jié)點(diǎn)傳播信息越容易。從節(jié)點(diǎn)效率的意義可以看出節(jié)點(diǎn)效率指標(biāo)能較好的評(píng)估這方面的問(wèn)題。本文研究的是與地理距離有關(guān)的網(wǎng)絡(luò)，而帶權(quán)重連接的嵌入式無(wú)標(biāo)度網(wǎng)絡(luò)模型(Weighted Lattice Embedded Scale－free(WLESF))正好能體現(xiàn)這一類網(wǎng)絡(luò)。因此，我們可把實(shí)體紅綠燈、路口、公交車站牌、車站、機(jī)場(chǎng)等看做網(wǎng)絡(luò)中的節(jié)點(diǎn)，其路徑看做節(jié)點(diǎn)與節(jié)點(diǎn)之間的邊。

2．2網(wǎng)絡(luò)中關(guān)鍵節(jié)點(diǎn)的評(píng)價(jià)標(biāo)準(zhǔn)

2．3 理論基礎(chǔ)

設(shè)圖G=(V，L)是一個(gè)無(wú)自環(huán)的無(wú)向網(wǎng)絡(luò)，其中V={v1，v2，…，vn}是網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合;L={l1，l2，…，ln}且L∈V×V是節(jié)點(diǎn)邊的集合。

定義1節(jié)點(diǎn)度是指與該節(jié)點(diǎn)直接相連的節(jié)點(diǎn)的數(shù)目，目前普遍認(rèn)為節(jié)點(diǎn)的重要性與其度值有很大的關(guān)系，所以節(jié)點(diǎn)的度值能直接反應(yīng)節(jié)點(diǎn)在整個(gè)網(wǎng)絡(luò)中的影響力。

定義3節(jié)點(diǎn)效率是指節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)之間距離倒數(shù)之和的平均值，即

從Ik的定義中可以看出，節(jié)點(diǎn)效率表達(dá)了節(jié)點(diǎn)到網(wǎng)絡(luò)中其他所有節(jié)點(diǎn)的平均難易程度，網(wǎng)絡(luò)中節(jié)點(diǎn)效率越高，表明該節(jié)點(diǎn)向其他節(jié)點(diǎn)傳輸信息越容易，所消耗的資源越少，該節(jié)點(diǎn)越重要。

3 模型的建立［7］

本文主要研究的是與地理距離有關(guān)的網(wǎng)絡(luò)?？紤]到很多現(xiàn)實(shí)的網(wǎng)絡(luò)都具有馬太效應(yīng)，所以在構(gòu)建模型時(shí)不但要考慮空間地理因素的影響也要考慮馬太效應(yīng)的影響，即節(jié)點(diǎn)間的連接主要考慮節(jié)點(diǎn)本身度的大小以及節(jié)點(diǎn)間的地理距離。為探討這兩個(gè)因素的影響，在模型中引進(jìn)參數(shù)α來(lái)調(diào)節(jié)控制節(jié)點(diǎn)的度權(quán)重與地理距離權(quán)重的比重。該模型的構(gòu)建具體分以下幾個(gè)步驟：

(1)初始網(wǎng)絡(luò)：給定大小為L(zhǎng)×L正方形二維網(wǎng)格，給定m0個(gè)節(jié)點(diǎn)隨機(jī)嵌入在網(wǎng)格的格點(diǎn)上，這m0個(gè)節(jié)點(diǎn)全連接(m0選取遠(yuǎn)遠(yuǎn)小于網(wǎng)格格點(diǎn)數(shù));

(2)網(wǎng)絡(luò)進(jìn)入演化階段：在每一單位時(shí)間網(wǎng)絡(luò)都增加一個(gè)新的節(jié)點(diǎn)，并嵌入到二維正方形網(wǎng)格中，且每個(gè)網(wǎng)格最多只能有一個(gè)節(jié)點(diǎn)，直到嵌入的節(jié)點(diǎn)布滿整個(gè)二維網(wǎng)格。每個(gè)新增節(jié)點(diǎn)在網(wǎng)格上的位置是隨機(jī)選取的，且這個(gè)新增的節(jié)點(diǎn)與原有網(wǎng)絡(luò)中的m(m≤m0)個(gè)節(jié)點(diǎn)相連(禁止重復(fù)連接和自身連接)，連接的概率取決于這兩個(gè)節(jié)點(diǎn)間的地理距離和待連接節(jié)點(diǎn)的度，具體按下面的第(3)步驟進(jìn)行;

(3)其一：在許多自然過(guò)程和科學(xué)領(lǐng)域中，高斯形式普遍存在，因此在考慮空間地理距離的影響時(shí)，我們?nèi)「咚购瘮?shù)作為地理距離的權(quán)重函數(shù)(PiD)：

設(shè)某時(shí)刻網(wǎng)絡(luò)有N(t)個(gè)節(jié)點(diǎn)，其中第j個(gè)節(jié)點(diǎn)被待增加的第i個(gè)節(jié)點(diǎn)連接的距離權(quán)重連接概率為：

其二：考慮節(jié)點(diǎn)度權(quán)重連接概率(PBA)：

設(shè)某時(shí)刻網(wǎng)絡(luò)有N(t)個(gè)節(jié)點(diǎn)，其中第j個(gè)節(jié)點(diǎn)被待增加的第i個(gè)節(jié)點(diǎn)連接的度權(quán)重連接概率為：

綜合考慮地理距離權(quán)重和節(jié)點(diǎn)度權(quán)重，引進(jìn)調(diào)節(jié)參數(shù)α(0≤α≤1)使得節(jié)點(diǎn)間的連接概率為：

由(3)式知，當(dāng)參數(shù)α從0增大到1可由嵌入式無(wú)標(biāo)度網(wǎng)絡(luò)漸進(jìn)過(guò)度到嵌入式指數(shù)網(wǎng)絡(luò)。若連接概率完全由地理距離權(quán)重決定，當(dāng)最近臨連接時(shí)(A=1)，網(wǎng)絡(luò)的度分布滿足指數(shù)分布，所以當(dāng)A=1，α從0逐漸增大到1時(shí)，網(wǎng)絡(luò)的度分布是從冪律分布逐漸過(guò)渡到指數(shù)分布，如圖1;α當(dāng) =1時(shí)，A從1逐漸增大到100時(shí)，其分布逐漸偏離指數(shù)分布，如圖2。

4計(jì)算機(jī)模擬的結(jié)果及分析

Fig1：度分布圖，A=1，α =0，0．5，1．網(wǎng)絡(luò)總節(jié)點(diǎn)數(shù)N=10000，L=100，m0=4，m=3．每個(gè)數(shù)據(jù)點(diǎn)是在給定參數(shù)下重復(fù)生成80次網(wǎng)絡(luò)并對(duì)度分布求平均后的結(jié)果(除非特別聲明，以下數(shù)據(jù)也是如此生成)

Fig2：度分布圖，α =1，A=1，20，30，100．

Fig3：節(jié)點(diǎn)效率分布圖：A=1，α =0，0．5，1．

Fig4：節(jié)點(diǎn)效率分布圖：α =1，A=1，20，30，100．

對(duì)比圖1和圖3、圖2和圖4，我們可以看出，度分布和節(jié)點(diǎn)效率分布基本一致，即A=1時(shí)，隨著參數(shù)α從0到1，節(jié)點(diǎn)效率分布從冪律分布逐漸過(guò)渡到指數(shù)分布。當(dāng)α=1，即節(jié)點(diǎn)的連接完全由地理距離概率決定時(shí)，參數(shù)A從1增大到100，節(jié)點(diǎn)效率分布逐漸偏離指數(shù)分布。這是因?yàn)楣?jié)點(diǎn)度的大小與節(jié)點(diǎn)效率的大小有直接關(guān)系。節(jié)點(diǎn)的度越大，其鄰居節(jié)點(diǎn)就越多，該節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的距離越短，節(jié)點(diǎn)效率就越高。當(dāng)參數(shù)A=100時(shí)，節(jié)點(diǎn)的連接范圍基本不受地理距離的限制，由地理連接概率可以看出，節(jié)點(diǎn)與其臨近的節(jié)點(diǎn)連接的概率更大，節(jié)點(diǎn)距離減小，節(jié)點(diǎn)效率變大，從而導(dǎo)致不存在節(jié)點(diǎn)效率較小的節(jié)點(diǎn)，如圖4。

Fig5：最大節(jié)點(diǎn)效率Imαx隨A的變化情況。

Fig6：最大節(jié)點(diǎn)效率Imαx隨α的變化情況。

節(jié)點(diǎn)效率的最大值Imαx對(duì)網(wǎng)絡(luò)的拓?fù)湫再|(zhì)有很大影響，例如實(shí)際中的發(fā)電站，離附近居民的平均距離越短，為居民提供最大方便的同時(shí)所消耗的資源就越少。從圖5可以看出，對(duì)于給定的α，隨著A的增大，節(jié)點(diǎn)效率的最大值Imαx相應(yīng)減小，當(dāng)A＞60時(shí)，節(jié)點(diǎn)效率的最大值Imαx趨于穩(wěn)定。這是因?yàn)楫?dāng)A＞60時(shí)，節(jié)點(diǎn)的連接幾乎不受地理距離的影響，度分布更加均勻，節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的難以程度更加接近，節(jié)點(diǎn)效率分布也更加均勻。從圖6可以看出，對(duì)于給定的A，隨著參數(shù)α的增大，節(jié)點(diǎn)效率的最大值Imαx逐漸減小。這是因?yàn)殡S著參數(shù)α的增大，地理距離所占的比重增加，馬太效應(yīng)減弱。本來(lái)度大的節(jié)點(diǎn)增加的概率減少，導(dǎo)致度大的節(jié)點(diǎn)的度減小，其鄰居個(gè)數(shù)也相應(yīng)減少，導(dǎo)致該節(jié)點(diǎn)到達(dá)其他節(jié)點(diǎn)的距離增大，節(jié)點(diǎn)效率減小．

Fig7：節(jié)點(diǎn)效率攻擊，直到網(wǎng)絡(luò)不連通時(shí)網(wǎng)絡(luò)節(jié)點(diǎn)的打擊規(guī)模f隨參數(shù)A的變化。

Fig8：節(jié)點(diǎn)效率攻擊，當(dāng)α=1，A=100時(shí)和隨機(jī)攻擊作比較

從圖7中可以看出，α固定，隨著參數(shù)A的增大，網(wǎng)絡(luò)能夠承受的打擊次數(shù)在不斷增加。當(dāng)A＞50，網(wǎng)絡(luò)能夠承受的打擊次數(shù)基本趨于穩(wěn)定，這是因?yàn)殡S著參數(shù)A的增大，節(jié)點(diǎn)的連接范圍基本不受地域的限制，節(jié)點(diǎn)效率分布更加均勻。當(dāng)網(wǎng)絡(luò)連接概率PD=1時(shí)，即網(wǎng)絡(luò)節(jié)點(diǎn)的連接全部由地理連接概率決定，參數(shù)A＞30時(shí)，采用節(jié)點(diǎn)效率進(jìn)行攻擊，網(wǎng)絡(luò)能夠承受的打擊次數(shù)和隨機(jī)攻擊相當(dāng)，如圖8。這說(shuō)明加入地理距離連接概率的網(wǎng)絡(luò)更接近真實(shí)網(wǎng)絡(luò)，這與自然科學(xué)中高斯形式普遍存在相吻合。

5 結(jié) 論

本文采用節(jié)點(diǎn)效率指標(biāo)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的重要性進(jìn)行評(píng)估，既考慮了節(jié)點(diǎn)失效的局部影響性，又考慮了節(jié)點(diǎn)失效的全局影響性?；诒疚乃芯康哪Ｐ?，實(shí)驗(yàn)結(jié)果分析表明，節(jié)點(diǎn)效率分布和度分布基本一致，采用刪除節(jié)點(diǎn)效率高的節(jié)點(diǎn)，直到網(wǎng)絡(luò)不連通時(shí)的打擊規(guī)模與度指標(biāo)也基本一致，但和隨機(jī)攻擊相比卻具有較大的優(yōu)越性。所以在類似本文構(gòu)建的與地理距離有關(guān)的網(wǎng)格網(wǎng)絡(luò)時(shí)，我們可以用度這個(gè)簡(jiǎn)單又重要的指標(biāo)對(duì)網(wǎng)絡(luò)節(jié)點(diǎn)的重要性進(jìn)行衡量。但并不代表度可以代替節(jié)點(diǎn)效率來(lái)衡量網(wǎng)絡(luò)節(jié)點(diǎn)的重要性。例如度大的根節(jié)點(diǎn)，到達(dá)其他節(jié)點(diǎn)的平均距離并不一定小，節(jié)點(diǎn)效率不一定大?？偟膩?lái)說(shuō)，本文研究的與地理距離有關(guān)的網(wǎng)絡(luò)對(duì)蓄意攻擊魯棒性較低，對(duì)隨機(jī)攻擊具有較強(qiáng)的容錯(cuò)性，這與網(wǎng)絡(luò)魯棒性評(píng)定的經(jīng)典結(jié)論［8，9］是一致的，這也證明了利用節(jié)點(diǎn)效率衡量節(jié)點(diǎn)重要性的有效性。

［1］周璇，張鳳鳴，周衛(wèi)平，鄒偉．物理學(xué)報(bào)，Acta PhysSin-Vol61，No19(2012)190201

［2］郭世澤，陸哲明．復(fù)雜網(wǎng)絡(luò)基礎(chǔ)理論［M］．科學(xué)出版社，2012：247

［3］Morohosi H 2012 Mathematics and Computers in Simulation 81 551

［4］Nair A，Vidal JM 2011 International Journal of Production Research 49 1391

［5］Albert R，Jeong H，Barabási A L，Attack and error tolerance in complex networksNature，2000，406：387 ～482

［6］王林，戴冠．復(fù)雜網(wǎng)絡(luò)的Scale－free性、Scale－free現(xiàn)象及其控制［M］．北京：科學(xué)出版社，2009：137

［7］陳進(jìn)良．與地域相關(guān)的類BA模型的構(gòu)造及其應(yīng)用［D］．2011：23

［8］Paul H，Seth B 2008 Proc．of the 41st Annual Hawaii International Conference on System Sciences Hawaii，January 7－10，2008 p1

［9］Albert D J，Strogatz SH 1998 Nature A 393 440