利用節點效率評估地理網格網絡的魯棒性*

王蕾蕾，林中材，潘佳慶，楊孔慶，鄒衛東

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

1 引 言

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

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

2 復雜網絡功能魯棒性的評定

2．1問題的提出

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

2．2網絡中關鍵節點的評價標準

2．3 理論基礎

設圖G=(V，L)是一個無自環的無向網絡，其中V={v1，v2，…，vn}是網絡中所有節點的集合;L={l1，l2，…，ln}且L∈V×V是節點邊的集合。

定義1節點度是指與該節點直接相連的節點的數目，目前普遍認為節點的重要性與其度值有很大的關系，所以節點的度值能直接反應節點在整個網絡中的影響力。

定義3節點效率是指節點與網絡中其他節點之間距離倒數之和的平均值，即

從Ik的定義中可以看出，節點效率表達了節點到網絡中其他所有節點的平均難易程度，網絡中節點效率越高，表明該節點向其他節點傳輸信息越容易，所消耗的資源越少，該節點越重要。

3 模型的建立［7］

本文主要研究的是與地理距離有關的網絡。考慮到很多現實的網絡都具有馬太效應，所以在構建模型時不但要考慮空間地理因素的影響也要考慮馬太效應的影響，即節點間的連接主要考慮節點本身度的大小以及節點間的地理距離。為探討這兩個因素的影響，在模型中引進參數α來調節控制節點的度權重與地理距離權重的比重。該模型的構建具體分以下幾個步驟：

(1)初始網絡：給定大小為L×L正方形二維網格，給定m0個節點隨機嵌入在網格的格點上，這m0個節點全連接(m0選取遠遠小于網格格點數);

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

(3)其一：在許多自然過程和科學領域中，高斯形式普遍存在，因此在考慮空間地理距離的影響時，我們取高斯函數作為地理距離的權重函數(PiD)：

設某時刻網絡有N(t)個節點，其中第j個節點被待增加的第i個節點連接的距離權重連接概率為：

其二：考慮節點度權重連接概率(PBA)：

設某時刻網絡有N(t)個節點，其中第j個節點被待增加的第i個節點連接的度權重連接概率為：

綜合考慮地理距離權重和節點度權重，引進調節參數α(0≤α≤1)使得節點間的連接概率為：

由(3)式知，當參數α從0增大到1可由嵌入式無標度網絡漸進過度到嵌入式指數網絡。若連接概率完全由地理距離權重決定，當最近臨連接時(A=1)，網絡的度分布滿足指數分布，所以當A=1，α從0逐漸增大到1時，網絡的度分布是從冪律分布逐漸過渡到指數分布，如圖1;α當 =1時，A從1逐漸增大到100時，其分布逐漸偏離指數分布，如圖2。

4計算機模擬的結果及分析

Fig1：度分布圖，A=1，α =0，0．5，1．網絡總節點數N=10000，L=100，m0=4，m=3．每個數據點是在給定參數下重復生成80次網絡并對度分布求平均后的結果(除非特別聲明，以下數據也是如此生成)

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

Fig3：節點效率分布圖：A=1，α =0，0．5，1．

Fig4：節點效率分布圖：α =1，A=1，20，30，100．

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

Fig5：最大節點效率Imαx隨A的變化情況。

Fig6：最大節點效率Imαx隨α的變化情況。

節點效率的最大值Imαx對網絡的拓撲性質有很大影響，例如實際中的發電站，離附近居民的平均距離越短，為居民提供最大方便的同時所消耗的資源就越少。從圖5可以看出，對于給定的α，隨著A的增大，節點效率的最大值Imαx相應減小，當A＞60時，節點效率的最大值Imαx趨于穩定。這是因為當A＞60時，節點的連接幾乎不受地理距離的影響，度分布更加均勻，節點到達其他節點的難以程度更加接近，節點效率分布也更加均勻。從圖6可以看出，對于給定的A，隨著參數α的增大，節點效率的最大值Imαx逐漸減小。這是因為隨著參數α的增大，地理距離所占的比重增加，馬太效應減弱。本來度大的節點增加的概率減少，導致度大的節點的度減小，其鄰居個數也相應減少，導致該節點到達其他節點的距離增大，節點效率減小．

Fig7：節點效率攻擊，直到網絡不連通時網絡節點的打擊規模f隨參數A的變化。

Fig8：節點效率攻擊，當α=1，A=100時和隨機攻擊作比較

從圖7中可以看出，α固定，隨著參數A的增大，網絡能夠承受的打擊次數在不斷增加。當A＞50，網絡能夠承受的打擊次數基本趨于穩定，這是因為隨著參數A的增大，節點的連接范圍基本不受地域的限制，節點效率分布更加均勻。當網絡連接概率PD=1時，即網絡節點的連接全部由地理連接概率決定，參數A＞30時，采用節點效率進行攻擊，網絡能夠承受的打擊次數和隨機攻擊相當，如圖8。這說明加入地理距離連接概率的網絡更接近真實網絡，這與自然科學中高斯形式普遍存在相吻合。

5 結 論

本文采用節點效率指標對網絡節點的重要性進行評估，既考慮了節點失效的局部影響性，又考慮了節點失效的全局影響性。基于本文所研究的模型，實驗結果分析表明，節點效率分布和度分布基本一致，采用刪除節點效率高的節點，直到網絡不連通時的打擊規模與度指標也基本一致，但和隨機攻擊相比卻具有較大的優越性。所以在類似本文構建的與地理距離有關的網格網絡時，我們可以用度這個簡單又重要的指標對網絡節點的重要性進行衡量。但并不代表度可以代替節點效率來衡量網絡節點的重要性。例如度大的根節點，到達其他節點的平均距離并不一定小，節點效率不一定大。總的來說，本文研究的與地理距離有關的網絡對蓄意攻擊魯棒性較低，對隨機攻擊具有較強的容錯性，這與網絡魯棒性評定的經典結論［8，9］是一致的，這也證明了利用節點效率衡量節點重要性的有效性。

［1］周璇，張鳳鳴，周衛平，鄒偉．物理學報，Acta PhysSin-Vol61，No19(2012)190201

［2］郭世澤，陸哲明．復雜網絡基礎理論［M］．科學出版社，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］王林，戴冠．復雜網絡的Scale－free性、Scale－free現象及其控制［M］．北京：科學出版社，2009：137

［7］陳進良．與地域相關的類BA模型的構造及其應用［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