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

楊宇騏，朱 磊

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

?

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

楊宇騏，朱 磊

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

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

隨機(jī)圖；連通率；子圖

0 引言

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

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

1 連通率與隨機(jī)圖

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

圖1 連通率示意圖

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

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

2 隨機(jī)圖的連通率

2.1 不含迂回路由的情況

(1)

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

(2)

整理得：

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

(3)

帶入式(1)得：

IRna=1-e-f(N)

(4)

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

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

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

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

S=1-e-zS

(5)

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

圖2 新節(jié)點(diǎn)加入時(shí)的小概率事件

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

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

(6)

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

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

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

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

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

3 仿真試驗(yàn)

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

圖4 連通率理論和仿真值對(duì)比

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

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

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

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

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

4 結(jié)論

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

[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] 熊煒,李清泉.高速公路場(chǎng)景中車(chē)用自組織網(wǎng)絡(luò)的節(jié)點(diǎn)度[J].電子與信息學(xué)報(bào),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ī)圖模型研究[J].計(jì)算機(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] 盧友軍,許道云.隨機(jī)圖G(n,p)中k-團(tuán)的相變性質(zhì)[J].貴州大學(xué)學(xué)報(bào)(自然科學(xué)版),2013,30(6): 86-90.

[11] 譚利,侯振挺.一類(lèi)無(wú)標(biāo)度隨機(jī)圖的度序列[J].應(yīng)用數(shù)學(xué)學(xué)報(bào),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] 王彬.隨機(jī)圖中的兩種相變[D].天津: 南開(kāi)大學(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

楊宇騏，朱磊.隨機(jī)網(wǎng)絡(luò)的連通率研究[J].微型機(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。