確定性復雜網絡的穩定性受隨機打擊影響的研究

暢興平，夏清華

（襄樊學院物理與電子工程學院 襄樊 441053）

1 引言

復雜系統廣泛存在于自然界和人類社會中，如中國城市航空網絡、公交停靠站點網絡、中國百強電子銷售網絡、科研合作網等，對這些復雜系統的研究已引起人們極大的興趣。對它們穩定性的研究尤為重要，因為復雜網絡的穩定性直接影響到信息的擁塞、傳輸、抗外界干擾。如路由器分布網絡[1],我們想要信息能夠更準確、更迅速地到達目的地，就必須使它的分布網絡更優化；如果想要它受外界影響更少，則可以改變它的網絡分布模式，尋找一個更好的網絡模型來代替以前的網絡。系統網絡的好壞通常是利用這個系統網絡的穩定性來衡量的[2]。為此，本文對陳牧先生提出的確定性復雜網絡模型的穩定性利用隨機打擊進行了分析。

2 確定性復雜網絡模型

復雜網絡模型的演化過程經過了4個階段，隨機網絡（random graph）模型、小世界網絡 (small-world)模型、無標度網絡(scale-free)模型和確定性復雜網絡模型。無標度網絡模型[3]（BA模型）最接近于現實存在的網絡，因此，此模型能夠很好地模擬現實中的度取值范圍和概率分布。但是BA模型也有不足的地方[4]，其缺陷有以下幾方面：網絡的生長過程是多種多樣的，很難預測，而它忽略了增長中的復雜性；優先連接中的概率取值過于簡單；沒有考慮網絡中有向性問題及各條邊的權重；BA模型網絡生長過程采用不間斷方式，這對現實中的網絡很難做到。為了解決上述模型存在的問題，2007年，陳牧引入了一種同時擁有小世界效應和無標度特性的確定性網絡模型,如圖1所示。

確定性復雜網絡的構造方法如下[1]：

（1）從n=0開始，即從一個節點出發；

（2）當n=1時，在第一個節點下方的兩邊對稱地分布兩個節點，且使這兩個節點與第一個節點相連；

（3）當n=2時，用相同的方法，在新生長出來的兩個節點的下方分別再對稱生長出兩個節點。且這4個節點再與第一個節點相連。

依照這種方法不斷地生長下去，就得到了一個確定性的網絡。可知，整個網絡的總節點數為N(n)=2n+1-1，總邊數為E(n)=(n-1)2n+1+2，也可以求得節點增長和邊的增長關系為 ΔE(n)=E(n)-E(n-1)=ng[N(n)-N(n-1)=ngΔN(n)，其平均度為

由圖2可以看出，隨著網絡的不斷增長，確定性復雜網絡模型的平均路徑長度近似為2，為一個衡量，且網絡的平均路徑長度總體較小。

此外，確定性復雜網絡的群系數與網絡大小的關系[1]如圖3所示。

圖2 平均路徑長度與網絡大小的關系

N指確定性復雜網絡中的節點數，由圖可知當N達到一定數量后，群系數C增長緩慢且趨近于1，群系數的整體變化范圍很小。圖4是度分布與網絡大小的關系。其中，確定性復雜網絡模型的度分布（N1=2 047,N2=4 095,N3=8 191,N4=16 383）冪指數分別滿足 γ1=1.2012,γ2=1.18552,γ3=1.17146,γ4=1.15887。

3 隨機打擊對確定性復雜網絡的穩定性影響

確定性復雜網絡同時擁有小世界效應[5]和無標度特性，它的等級結構解釋了中樞節點在復雜網絡中的角色：層數越高，其中的節點度越大。這些中樞節點對于維持確定性復雜網絡的完整性起到主導作用。然而，它們直接連接的節點表現得彼此疏遠，無凝聚力，從而導致了取值較小的部分[6]。另外，這些連接數少的節點具有很大的群系數，這也意味著它們的鄰居密集連接，并形成了小的集群。每個節點與其親屬節點連接，確定性復雜網絡的抗毀性得到增強。隨機打擊是研究網絡穩定性時經常用到的一種方法，都是通過計算機模擬來實現的。本文中主要的亮點是使用了蒙特卡洛方法，這為以后復雜網絡穩定性的研究開辟了一個新穎的研究道路。

打擊的主要思路：放一個隨機粒子在確定性復雜網絡的正中間，取一個0～1之間的隨機數，讓這個粒子隨機行走，步長是1（假設節點之間的距離都是1），每走一步打擊到一個粒子，且這個粒子就不存在了，再算剩下來網絡的平均路徑長度和群系數。直到粒子碰到邊界為止。這里取n=21層網絡進行網絡穩定性分析，此時N(20)=2 097 151，L=1.99996。隨機打擊的示意如圖5所示。

3.1 在隨機打擊下平均路徑長度的變化

確定性復雜網絡的構造是很規則的，并且有很強的層次感，假設i代表層數，則經過n次迭代以后可得：第i行第j個節點的路徑為，整個網絡的平均路徑長度為，n層網絡的總節點數N(n)=2n+1-1。打擊掉第i層第j個節點后，網絡的平均路徑長度為：

顯而易見，只要知道第幾層，幾個節點，很容易就可以求得打擊節點后的確定性復雜網絡的平均路徑長度，這個值是隨著i值和打擊節點個數變化的。在隨機打擊中，利用的是隨機因子，并且隨機數不同，打擊后的節點的表達式也有相對應的變化，但都和i有關系。

利用計算機編程進行模擬，再根據上面講的打擊思路對網絡進行打擊，可得到一系列的數據。打擊后的節點數N與平均路徑長度L的關系如圖6和圖7所示。

圖6中橫坐標是確定性復雜網絡的層數n，縱坐標是平均路徑長度。從圖中可以看到，平均路徑長度從1.99996到1.99991，幾乎沒有變化，也可以說確定性復雜在隨機打擊下平均路徑長度并沒有受到很大影響。而網絡層的多少對平均路徑長度的影響只是輕微的，總的效果沒有發生什么改變。圖7是n=21和n=13兩種情況下的n和L的關系圖，由圖可以得到，網絡層越多，節點數越大，網絡越穩定，抗毀性越強。

圖8是確定性復雜網絡的f與L的關系圖，其中f是打擊的節點數與總節點數的比值。由圖可知，隨著f的增加，平均路徑長度L逐漸減小，變化范圍從1.8267到1.9983，范圍很小，因此確定性復雜網絡是比較穩定的。

3.2 在隨機打擊下群系數的變化

群系數同平均路徑長度一樣，是衡量復雜網絡穩定性的另一個非常重要的量，同樣的方法可求得n層迭代以后的群系數。

第i層第j個節點的群系數：

總群系數C為：

顯而易見，只要知道n、i和打擊的節點數，就可以很容易地得到打擊后的群系數。

圖9中橫坐標是確定性復雜網絡的層數n，縱坐標是群系數C。從圖中可以看出群系數幾乎是一條直線，在0.951附近，所以確定性復雜在隨機打擊下群系數并沒有受到很大影響。

由圖10可知，網絡節點多的群系數大，節點小的群系數小。但它們受隨機打擊后的群系數C并沒有受到很大的影響，還是比較穩定的。

圖10 n=20和n=13時確定性復雜網絡在隨機打擊下C的變化

4 結束語

在隨機打擊下，確定性復雜網絡的平均路徑長度和群系數都能保持很好的穩定性，沒有因隨機打擊而受到很大的干擾，所以確定性復雜網絡對于隨機打擊具有很強的穩定性。

1 Chen Mu,Yu Boming,Xu Peng,Chen Jun.A new deterministic complex network model with hierarchical structure.Physica A:Statistical Mechanics and its Applications,2007，385(2):307～317

2 Barabási A L,Albert R.Emergence of scaling in random networks.Science,1999（286）:509～512

3 杜海峰，李樹茁.小世界網絡與無標度網絡的社區結構研究.物理學報，2007,56(12)：6886～6893

4 Boccaletti S.Complex networks:structure and dynamics.Physics Reports,2006(424):175～38

5 Watts D J,Strogatz S H.Collective dynamics of “small-world”networks.Ature,1998（393）：440～442

6 Barbási A L,Jeong H,Jeong H,Ravasz E,et al.Evolution of the social network of scientific collaborations.Physica A,2002（311）:590～614