隨機網(wǎng)絡(luò)的連通率研究

楊宇騏，朱 磊

(中國人民解放軍理工大學(xué) 通信工程學(xué)院，江蘇 南京 210007)

?

隨機網(wǎng)絡(luò)的連通率研究

楊宇騏，朱 磊

(中國人民解放軍理工大學(xué) 通信工程學(xué)院，江蘇 南京 210007)

隨機圖是一種簡單并且可用于抽象現(xiàn)實社會多種實際系統(tǒng)的網(wǎng)絡(luò)。與其他網(wǎng)絡(luò)模型不同，隨機圖的構(gòu)造方式?jīng)Q定其節(jié)點具有對等性，且網(wǎng)絡(luò)中可能存在孤立節(jié)點和子圖。對隨機圖尤其是其連通性的研究有助于更深入地了解具有隨機連接特性及節(jié)點對等特性的真實網(wǎng)絡(luò)。文章采用理論與仿真相結(jié)合的方法，重點研究隨機圖的連通性和隨機圖連通率的計算方法，揭示了隨機圖在演化過程中的形態(tài)變化，表明隨機圖中樹結(jié)構(gòu)的廣泛存在。研究還發(fā)現(xiàn)，在巨大連通子圖形成前，隨機圖的子圖大小呈冪律分布。本研究結(jié)果為復(fù)雜網(wǎng)絡(luò)相關(guān)的實證研究和性質(zhì)復(fù)雜的網(wǎng)絡(luò)相變態(tài)研究提供了理論依據(jù)。

隨機圖；連通率；子圖

0 引言

自20世紀(jì)60年代ERD?S P和RéNYI A提出隨機圖模型[1]以來，隨機圖理論一度成為研究復(fù)雜網(wǎng)絡(luò)的基本理論。其研究焦點多集中于自身統(tǒng)計特性的描述，例如子圖的平均大小、巨大連通子圖的存在條件，以及構(gòu)圖規(guī)則的改進[2]等方面。在隨機圖中，任意兩個節(jié)點間以一定的概率直接相連，人們期望以此作為自然界一些網(wǎng)絡(luò)的基本抽象，例如人際關(guān)系網(wǎng)絡(luò)、病毒傳播網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等[3-5]。但大規(guī)模實證研究表明自然界多數(shù)實際網(wǎng)絡(luò)均屬于無標(biāo)度網(wǎng)絡(luò)[6](節(jié)點的度分布為冪律分布)，與隨機圖有較大差別。隨機圖簡單的構(gòu)造方式?jīng)Q定了其自身缺少更精確的模擬真實網(wǎng)絡(luò)的結(jié)構(gòu)，無法單純地通過研究隨機圖來獲得眾多實際網(wǎng)絡(luò)的拓?fù)浣y(tǒng)計特征和動力學(xué)特征。然而，從統(tǒng)計學(xué)的角度考慮，網(wǎng)絡(luò)的連通情況仍可通過對隨機圖的研究窺見。

現(xiàn)代社會中，人們每時每刻都處于或正與各種各樣的復(fù)雜系統(tǒng)建立聯(lián)系。一個很自然的思考是一個個體與另外一個個體建立聯(lián)系的概率的大小。由于受研究方法和網(wǎng)絡(luò)拓?fù)鋸?fù)雜程度的限制，傳統(tǒng)有關(guān)網(wǎng)絡(luò)連通情況的研究往往關(guān)注網(wǎng)絡(luò)的連通子圖[7-8],忽略網(wǎng)絡(luò)節(jié)點間連通情況的微觀考慮。此外，對隨機圖子圖的研究主要針對子圖的平均規(guī)模，缺少子圖大小分布的定量描述，尤其對巨大連通子圖即將形成的相變態(tài)[9-10]研究較少。本文以隨機圖為研究對象，提出并研究了隨機圖的連通率，對子圖中迂回路由的存在情況進行了假設(shè)和驗證，并基于仿真試驗提出了相變態(tài)中子圖大小的分布。所得研究結(jié)論可有效地應(yīng)用于現(xiàn)實網(wǎng)絡(luò)系統(tǒng)的規(guī)劃、建設(shè)與分析中。

1 連通率與隨機圖

定義連通率(Interconnection Rate，IR)為網(wǎng)絡(luò)中連通(直接連接或多跳轉(zhuǎn)接)的節(jié)點對數(shù)與總節(jié)點對數(shù)之比，如圖1(b)所示。給定網(wǎng)絡(luò)拓?fù)洌隳茌^容易地得到該網(wǎng)絡(luò)的連通率。對于由分散節(jié)點組成的網(wǎng)絡(luò)，連通率為0，對于連通網(wǎng)絡(luò)，連通率為1。圖的最小生成樹以最小的邊數(shù)達到全連通，是最高效的全連通網(wǎng)絡(luò)。如圖1(a)、(c)、(d)所示。

圖1 連通率示意圖

隨機圖[1]定義為一個含有N個節(jié)點的網(wǎng)絡(luò)，其中任意兩個節(jié)點有連邊的概率為p，總的連邊數(shù)L=N(N-1)p/2。從網(wǎng)絡(luò)結(jié)構(gòu)演化的角度又可表述為，每一時刻一個新節(jié)點加入網(wǎng)絡(luò)，新節(jié)點以概率p與每一個已存在的節(jié)點建立連邊。隨機圖的度分布為泊松分布[11]，節(jié)點的平均度z=2L/N=(N-1)p。若p很小，只有當(dāng)節(jié)點數(shù)N很大即網(wǎng)絡(luò)規(guī)模很大時才會有較大的z，大的節(jié)點數(shù)和大的節(jié)點度數(shù)看似矛盾，在隨機圖網(wǎng)絡(luò)中卻有著此般緊密的聯(lián)系。從構(gòu)造方式可以看出，隨機圖的一個重要特點是節(jié)點之間關(guān)系的平等性，節(jié)點的度集中于平均度z附近，這是許多其他復(fù)雜網(wǎng)絡(luò)模型(如無標(biāo)度網(wǎng)絡(luò)模型)不具有的性質(zhì)。對于節(jié)點關(guān)系對等的隨機圖，若網(wǎng)絡(luò)規(guī)模足夠大或者重復(fù)試驗次數(shù)較多，網(wǎng)絡(luò)的連通率在統(tǒng)計意義上等價于網(wǎng)絡(luò)中任意兩個節(jié)點之間相互連通的概率，由此能將隨機圖的網(wǎng)絡(luò)層次與節(jié)點層次有效地結(jié)合。

在對隨機圖的研究中，無論p的取值和隨機圖規(guī)模如何變化，當(dāng)網(wǎng)絡(luò)的邊數(shù)L與節(jié)點數(shù)N滿足L=2N(即z≈4)時,總有IR=0.961 3。這等同于如果每一個節(jié)點平均與其余4個節(jié)點直接相連，則該節(jié)點將以0.961 3的概率與網(wǎng)絡(luò)中任意一個節(jié)點連通。若L/N進一步增大，則連通的概率也會相應(yīng)增大。事實上，隨機圖的平均路徑長度[12]LER≈1+ln(1/p)/ln(z)，當(dāng)p=0.001，z=4時，得LER≈6，這似乎與著名的“六度分離”[13]有著相似的結(jié)論。

2 隨機圖的連通率

2.1 不含迂回路由的情況

(1)

其中，右端的參數(shù)n不同于i，代表連通路徑上的中介節(jié)點數(shù)。在p確定的情況下，式(1)右端第二項是N的函數(shù)，取對數(shù)得：

(2)

整理得：

f(N)=p[1+(N-2)f(N-1)],(f(2)=p)

(3)

帶入式(1)得：

IRna=1-e-f(N)

(4)

式(4)即為不含迂回路由的情況下節(jié)點間的連通率，根據(jù)前述隨機圖的性質(zhì)，此連通率也為網(wǎng)絡(luò)的連通率。

從演化角度講，在實現(xiàn)連通前，隨機圖經(jīng)歷了兩種形態(tài)。第一種形態(tài)是網(wǎng)絡(luò)由許多規(guī)模較小的連通子圖組成，第二種形態(tài)是網(wǎng)絡(luò)中一個巨大連通子圖和一些較小的連通子圖并存[14]。本文認(rèn)為在巨大連通子圖形成前的第一種形態(tài)，子圖普遍呈樹結(jié)構(gòu)，即不含迂回路由。此觀點將在仿真試驗部分得到驗證。下面討論第二種形態(tài)下的連通率。

2.2 存在巨大連通子圖的情況

在隨機圖中,巨大連通子圖所含節(jié)點數(shù)占網(wǎng)絡(luò)節(jié)點總數(shù)的比例S為[9]:

S=1-e-zS

(5)

巨大連通子圖本身是一棵樹的可能性非常小(小于pSN-1)，所以幾乎一定存在迂回路由，而與巨大連通子圖共存的小連通子圖中是否存在迂回路由值得思考。考慮圖2所示的場景，節(jié)點C的加入帶來了兩條邊(虛線所示)，使節(jié)點A與B之間多了一條迂回路徑。但事實是當(dāng)節(jié)點C加入網(wǎng)絡(luò)時，與巨大連通子圖相連的概率為P1=1-(1-p)SN，與子圖AB相連的概率為P2=1-(1-p)2，P1?P2，所以根據(jù)實際推斷原理，圖2所示場景在實際中幾乎是不會發(fā)生的。或者說，在網(wǎng)絡(luò)中隨機選擇一條邊，極有可能位于巨大連通子圖中而非網(wǎng)絡(luò)的其他部分。基于該結(jié)論，可以判定當(dāng)巨大連通子圖存在時，小連通子圖不含迂回路由。

圖2 新節(jié)點加入時的小概率事件

在巨大連通子圖形成后，從網(wǎng)絡(luò)中隨機選取兩個節(jié)點計算連通率，存在以下3種情況：

綜上，巨大連通子圖形成后網(wǎng)絡(luò)的連通率為：

(6)

2.3 網(wǎng)絡(luò)的相變態(tài)

前述給出了隨機圖的連通率在兩種狀態(tài)下的計算方法，計算的根據(jù)為子圖中不含迂回路由即子圖呈樹結(jié)構(gòu)的假設(shè)。然而在隨機圖的演化過程中還存在一種中間狀態(tài)，在這種狀態(tài)下，子圖聚合，以一種突變的方式形成巨大連通子圖，該滲流狀態(tài)被稱為隨機圖的相變態(tài)[15]，研究表明巨大連通子圖形成的相變點為z=1[16]。對相變態(tài)的量化分析較困難，相關(guān)文獻也較少。本文通過大量試驗研究了隨機圖相變態(tài)的子圖大小分布，發(fā)現(xiàn)在雙對數(shù)坐標(biāo)下，相變態(tài)的子圖大小符合冪律分布，如圖3所示，分布圖像呈倒置的煙斗形。

圖3 相變態(tài)的子圖節(jié)點數(shù)分布

子圖大小的冪律分布表明，相變態(tài)中規(guī)模較小的子圖占大多數(shù)，但仍有少量規(guī)模相對很大的子圖，這種子圖大小的分布是極不均勻的。本文用帶指數(shù)拖尾的冪律分布y=10αxβex/γ對該狀態(tài)的子圖大小分布進行擬合，其中x表示子圖中的節(jié)點數(shù)，y表示具有x個節(jié)點的子圖數(shù)，γ表示拖尾長度。擬合結(jié)果如表1所示。

表1 不同p值下相變態(tài)子圖大小分布的參數(shù)擬合值

3 仿真試驗

通過前文的理論分析，得到了一些關(guān)于隨機圖連通率和隨機圖形態(tài)的重要結(jié)論。本文采用仿真試驗的方式對上述結(jié)論進行驗證，主要給出了p=0.005時仿真試驗的結(jié)果(其余結(jié)果與之相似)，試驗結(jié)果取1 000次平均。對隨機圖連通率的仿真如圖4和5所示。其中實線部分為理論值，在相變態(tài)之前和之后的連通率分別由式(4)和式(6)計算得出。圖4中，仿真結(jié)果和理論值能夠較好地吻合，表明了連通率計算公式的正確性，也間接證明了前述假設(shè)的正確性，即隨機圖的小子圖基本為樹結(jié)構(gòu)，不含迂回路由。特別地，在式(6)中令N=801 (此時L=2N)得IR=0.961 3，這為本文第2節(jié)中的發(fā)現(xiàn)提供了理論依據(jù)。

圖4 連通率理論和仿真值對比

圖5 相變態(tài)的連通率

圖5顯示了相變態(tài)(這里取定范圍為z∈(0.85,1.15))連通率的仿真值，顯然用式(4)或式(6)來計算網(wǎng)絡(luò)相變態(tài)的連通率會存在很大誤差。結(jié)合本文關(guān)于相變態(tài)子圖大小分布的結(jié)論并根據(jù)表1的參數(shù)擬合值，得到相變態(tài)的連通率理論值，如圖6中虛線所示。仿真結(jié)果與理論值吻合較好，證明了本文關(guān)于相變態(tài)子圖大小分布結(jié)論的正確性及擬合方法的可行性。

圖6 利用相變態(tài)子圖大小分布得到的連通率理論值

圖7 隨機圖網(wǎng)絡(luò)的連通情況變化示意

根據(jù)前述分析和試驗，可以清晰地描述隨機圖或者具有節(jié)點對等特征的網(wǎng)絡(luò)的演化過程，如圖7所示：網(wǎng)絡(luò)初始階段只含少量孤立節(jié)點，隨著新節(jié)點的不斷加入，連接逐漸增多，子圖出現(xiàn)；子圖漸漸增多，規(guī)模也在擴大，但基本都是樹形結(jié)構(gòu)；子圖規(guī)模繼續(xù)增加，出現(xiàn)了數(shù)量可觀的小子圖和少數(shù)相對較大的子圖，子圖大小服從冪律分布，網(wǎng)絡(luò)演化進入相變態(tài)；相變態(tài)的時間很短，眾多子圖很快互連為巨大連通子圖，巨大連通子圖不斷擴大，小子圖仍呈樹結(jié)構(gòu)并逐漸并入巨大連通子圖中；最后，網(wǎng)絡(luò)連通。

4 結(jié)論

現(xiàn)實世界存在很多具有隨機連接特性的網(wǎng)絡(luò)或系統(tǒng)，在一定程度上可抽象為隨機圖，并且由于隨機圖節(jié)點的對等地位，其在對等網(wǎng)絡(luò)研究方面具有重要意義。傳統(tǒng)的隨機圖理論對網(wǎng)絡(luò)演化過程中的連通情況尤其是節(jié)點層次的連通情況研究較少。本文通過對隨機圖連通率的研究,給出了隨機圖連通率的計算方法；通過對小子圖中不存在迂回路由的假設(shè)及驗證，說明了隨機圖中樹結(jié)構(gòu)的廣泛存在；此外，通過試驗發(fā)現(xiàn)并驗證了相變態(tài)的子圖大小滿足冪律分布，進一步清晰勾勒了隨機圖的演化過程，即同規(guī)模子圖狀態(tài)、短暫且子圖大小成冪律分布的相變態(tài)、巨大連通子圖存在并不斷擴大的狀態(tài)、連通狀態(tài)。本文研究成果對真實網(wǎng)絡(luò)尤其對于對等網(wǎng)絡(luò)的研究、規(guī)劃和建設(shè)具有重要意義。不過本文仍存在許多不足之處，如連通率定義的簡單性可能帶來計算中的不確定因素，從而掩蓋了隨機圖演化過程中的其他重要性質(zhì)；對隨機圖相變態(tài)子圖大小的擬合存在一定誤差。如何將連通率的計算擴展到其他網(wǎng)絡(luò)模型，并將其有效地應(yīng)用在如通信網(wǎng)絡(luò)等實證研究方面是下一階段研究的方向。

[1] ERD?S P,RéNYI A.On random graphs[J].Publ Math Debrecen,1959(6): 1-14.

[2] ACHLIOPTAS D,D’SOUZA R M,SPENCER J.Explosive percolation in random networks[J].Science,2009,323(5920): 1453-1455.

[3] KADUSHIN C.Understanding social networks: theories,concepts,and finding[M].Oxford University Press,USA,2012.

[4] BALTHROP J,FORREST S,NEWMAN M E J,et al.Technological networks and the spread of computer viruses[J].Science,2004,304(5670): 527-529.

[5] 熊煒,李清泉.高速公路場景中車用自組織網(wǎng)絡(luò)的節(jié)點度[J].電子與信息學(xué)報,2010,32(9): 2033-2038.

[6] KRAPIVSKY P L,REDNER S,LEYVRAZ F.Connectivity of growing random networks[J].Phys.Rev.Lett.,2000,85(21): 4629-4632.

[8] 黃斌,吳春旺,鄭豐華,等.復(fù)雜網(wǎng)絡(luò)中隨機圖模型研究[J].計算機工程與科學(xué),2014,36(7): 1377-1383.

[9] NEWMAN M E J,STROGATZ S H,WATTS D J.Random graph with arbitrary degree distributions and their applications[J].Phys.Rev.E,2001,64(2-2):359-382.

[10] 盧友軍,許道云.隨機圖G(n,p)中k-團的相變性質(zhì)[J].貴州大學(xué)學(xué)報(自然科學(xué)版),2013,30(6): 86-90.

[11] 譚利,侯振挺.一類無標(biāo)度隨機圖的度序列[J].應(yīng)用數(shù)學(xué)學(xué)報,2011,34(3): 440-447.

[12] 汪小帆,李翔,陳關(guān)榮.復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用[M].北京:清華大學(xué)出版社,2006.

[13] MILGRAM S.The small world problem[J].Psychology Today,1967,2(1):185-195.

[14] NEWMAN M E J,WATTS D J,STROGATZ S H.Random graph models of social networks[C].Proceedings of the National Academy of the Sciences of the United States of America,2002,99: 2566-2572.

[15] 王彬.隨機圖中的兩種相變[D].天津: 南開大學(xué),2011.

[16] MOLLOY M,REED B,MOLLOY M.The size of the largest component of a random graph on a fixed degree sequence[J].Combinatorica,1998,7(3):295-305.

Research on interconnection rate of random network

Yang Yuqi，Zhu Lei

(Department of Communication Engineering,PLA University of Science and Technology,Nanjing 210007,China)

Random graphs can be used to describe a lot of complex systems in our society.Due to its generation algorithm,a random graph may contain isolated nodes or components,and nodes are equipotent in it.Many empirical researches show that the real world networks are most scale-free,however,the random graph still works in helping us to further understand many features of these networks,especially the connectivity.In this article,we mainly define and study the interconnection rate of the random graph.We come up with the calculation method of the interconnection rate of a random graph,which reveals the variety of the graph shape,indicating the ubiquitous tree structures in the graph.Besides,this study shows that the component size obeys power-lower form at the phase transition state,which provides theoretical basis for the study of the phase transition of component size in a random graph.

random graph; interconnection rate; component

N941

A DOI：10.19358/j.issn.1674-7720.2016.19.017

楊宇騏，朱磊.隨機網(wǎng)絡(luò)的連通率研究[J].微型機與應(yīng)用，2016,35(19)：56-59.

2016-05-05)

楊宇騏(1991-)，男，碩士研究生在讀，主要研究方向：復(fù)雜網(wǎng)絡(luò)。

朱磊 (1973-)，通信作者，男，博士，教授，主要研究方向：通信網(wǎng)絡(luò)規(guī)劃與管理。E-mail:zhulei_paper@126.com。