確定性復(fù)雜網(wǎng)絡(luò)的穩(wěn)定性受隨機(jī)打擊影響的研究

暢興平，夏清華

（襄樊學(xué)院物理與電子工程學(xué)院 襄樊 441053）

1 引言

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

2 確定性復(fù)雜網(wǎng)絡(luò)模型

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

確定性復(fù)雜網(wǎng)絡(luò)的構(gòu)造方法如下[1]：

（1）從n=0開始，即從一個(gè)節(jié)點(diǎn)出發(fā)；

（2）當(dāng)n=1時(shí)，在第一個(gè)節(jié)點(diǎn)下方的兩邊對(duì)稱地分布兩個(gè)節(jié)點(diǎn)，且使這兩個(gè)節(jié)點(diǎn)與第一個(gè)節(jié)點(diǎn)相連；

（3）當(dāng)n=2時(shí)，用相同的方法，在新生長(zhǎng)出來的兩個(gè)節(jié)點(diǎn)的下方分別再對(duì)稱生長(zhǎng)出兩個(gè)節(jié)點(diǎn)。且這4個(gè)節(jié)點(diǎn)再與第一個(gè)節(jié)點(diǎn)相連。

依照這種方法不斷地生長(zhǎng)下去，就得到了一個(gè)確定性的網(wǎng)絡(luò)?？芍麄€(gè)網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)為N(n)=2n+1-1，總邊數(shù)為E(n)=(n-1)2n+1+2，也可以求得節(jié)點(diǎn)增長(zhǎng)和邊的增長(zhǎng)關(guān)系為 ΔE(n)=E(n)-E(n-1)=ng[N(n)-N(n-1)=ngΔN(n)，其平均度為

由圖2可以看出，隨著網(wǎng)絡(luò)的不斷增長(zhǎng)，確定性復(fù)雜網(wǎng)絡(luò)模型的平均路徑長(zhǎng)度近似為2，為一個(gè)衡量，且網(wǎng)絡(luò)的平均路徑長(zhǎng)度總體較小。

此外，確定性復(fù)雜網(wǎng)絡(luò)的群系數(shù)與網(wǎng)絡(luò)大小的關(guān)系[1]如圖3所示。

圖2 平均路徑長(zhǎng)度與網(wǎng)絡(luò)大小的關(guān)系

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

3 隨機(jī)打擊對(duì)確定性復(fù)雜網(wǎng)絡(luò)的穩(wěn)定性影響

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

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

3.1 在隨機(jī)打擊下平均路徑長(zhǎng)度的變化

確定性復(fù)雜網(wǎng)絡(luò)的構(gòu)造是很規(guī)則的，并且有很強(qiáng)的層次感，假設(shè)i代表層數(shù)，則經(jīng)過n次迭代以后可得：第i行第j個(gè)節(jié)點(diǎn)的路徑為，整個(gè)網(wǎng)絡(luò)的平均路徑長(zhǎng)度為，n層網(wǎng)絡(luò)的總節(jié)點(diǎn)數(shù)N(n)=2n+1-1。打擊掉第i層第j個(gè)節(jié)點(diǎn)后，網(wǎng)絡(luò)的平均路徑長(zhǎng)度為：

顯而易見，只要知道第幾層，幾個(gè)節(jié)點(diǎn)，很容易就可以求得打擊節(jié)點(diǎn)后的確定性復(fù)雜網(wǎng)絡(luò)的平均路徑長(zhǎng)度，這個(gè)值是隨著i值和打擊節(jié)點(diǎn)個(gè)數(shù)變化的。在隨機(jī)打擊中，利用的是隨機(jī)因子，并且隨機(jī)數(shù)不同，打擊后的節(jié)點(diǎn)的表達(dá)式也有相對(duì)應(yīng)的變化，但都和i有關(guān)系。

利用計(jì)算機(jī)編程進(jìn)行模擬，再根據(jù)上面講的打擊思路對(duì)網(wǎng)絡(luò)進(jìn)行打擊，可得到一系列的數(shù)據(jù)。打擊后的節(jié)點(diǎn)數(shù)N與平均路徑長(zhǎng)度L的關(guān)系如圖6和圖7所示。

圖6中橫坐標(biāo)是確定性復(fù)雜網(wǎng)絡(luò)的層數(shù)n，縱坐標(biāo)是平均路徑長(zhǎng)度。從圖中可以看到，平均路徑長(zhǎng)度從1.99996到1.99991，幾乎沒有變化，也可以說確定性復(fù)雜在隨機(jī)打擊下平均路徑長(zhǎng)度并沒有受到很大影響。而網(wǎng)絡(luò)層的多少對(duì)平均路徑長(zhǎng)度的影響只是輕微的，總的效果沒有發(fā)生什么改變。圖7是n=21和n=13兩種情況下的n和L的關(guān)系圖，由圖可以得到，網(wǎng)絡(luò)層越多，節(jié)點(diǎn)數(shù)越大，網(wǎng)絡(luò)越穩(wěn)定，抗毀性越強(qiáng)。

圖8是確定性復(fù)雜網(wǎng)絡(luò)的f與L的關(guān)系圖，其中f是打擊的節(jié)點(diǎn)數(shù)與總節(jié)點(diǎn)數(shù)的比值。由圖可知，隨著f的增加，平均路徑長(zhǎng)度L逐漸減小，變化范圍從1.8267到1.9983，范圍很小，因此確定性復(fù)雜網(wǎng)絡(luò)是比較穩(wěn)定的。

3.2 在隨機(jī)打擊下群系數(shù)的變化

群系數(shù)同平均路徑長(zhǎng)度一樣，是衡量復(fù)雜網(wǎng)絡(luò)穩(wěn)定性的另一個(gè)非常重要的量，同樣的方法可求得n層迭代以后的群系數(shù)。

第i層第j個(gè)節(jié)點(diǎn)的群系數(shù)：

總?cè)合禂?shù)C為：

顯而易見，只要知道n、i和打擊的節(jié)點(diǎn)數(shù)，就可以很容易地得到打擊后的群系數(shù)。

圖9中橫坐標(biāo)是確定性復(fù)雜網(wǎng)絡(luò)的層數(shù)n，縱坐標(biāo)是群系數(shù)C。從圖中可以看出群系數(shù)幾乎是一條直線，在0.951附近，所以確定性復(fù)雜在隨機(jī)打擊下群系數(shù)并沒有受到很大影響。

由圖10可知，網(wǎng)絡(luò)節(jié)點(diǎn)多的群系數(shù)大，節(jié)點(diǎn)小的群系數(shù)小。但它們受隨機(jī)打擊后的群系數(shù)C并沒有受到很大的影響，還是比較穩(wěn)定的。

圖10 n=20和n=13時(shí)確定性復(fù)雜網(wǎng)絡(luò)在隨機(jī)打擊下C的變化

4 結(jié)束語

在隨機(jī)打擊下，確定性復(fù)雜網(wǎng)絡(luò)的平均路徑長(zhǎng)度和群系數(shù)都能保持很好的穩(wěn)定性，沒有因隨機(jī)打擊而受到很大的干擾，所以確定性復(fù)雜網(wǎng)絡(luò)對(duì)于隨機(jī)打擊具有很強(qiáng)的穩(wěn)定性。

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 杜海峰，李樹茁.小世界網(wǎng)絡(luò)與無標(biāo)度網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)研究.物理學(xué)報(bào)，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