楊宇騏，朱磊

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

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

　　關(guān)鍵詞：隨機(jī)圖；連通率；子圖

0引言

　　自20世紀(jì)60年代ERDS P和RNYI A提出隨機(jī)圖模型［1］以來，隨機(jī)圖理論一度成為研究復(fù)雜網(wǎng)絡(luò)的基本理論。其研究焦點(diǎn)多集中于自身統(tǒng)計(jì)特性的描述，例如子圖的平均大小、巨大連通子圖的存在條件，以及構(gòu)圖規(guī)則的改進(jìn)［2］等方面。在隨機(jī)圖中，任意兩個節(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ò)均屬于無標(biāo)度網(wǎng)絡(luò)［6］(節(jié)點(diǎn)的度分布為冪律分布)，與隨機(jī)圖有較大差別。隨機(jī)圖簡單的構(gòu)造方式?jīng)Q定了其自身缺少更精確的模擬真實(shí)網(wǎng)絡(luò)的結(jié)構(gòu)，無法單純地通過研究隨機(jī)圖來獲得眾多實(shí)際網(wǎng)絡(luò)的拓?fù)浣y(tǒng)計(jì)特征和動力學(xué)特征。然而，從統(tǒng)計(jì)學(xué)的角度考慮，網(wǎng)絡(luò)的連通情況仍可通過對隨機(jī)圖的研究窺見。

　　現(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é)點(diǎn)間連通情況的微觀考慮。此外，對隨機(jī)圖子圖的研究主要針對子圖的平均規(guī)模，缺少子圖大小分布的定量描述，尤其對巨大連通子圖即將形成的相變態(tài)［910］研究較少。本文以隨機(jī)圖為研究對象，提出并研究了隨機(jī)圖的連通率，對子圖中迂回路由的存在情況進(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)對數(shù)與總節(jié)點(diǎn)對數(shù)之比，如圖1(b)所示。給定網(wǎng)絡(luò)拓?fù)?，便能較容易地得到該網(wǎng)絡(luò)的連通率。對于由分散節(jié)點(diǎn)組成的網(wǎng)絡(luò)，連通率為0，對于連通網(wǎng)絡(luò)，連通率為1。圖的最小生成樹以最小的邊數(shù)達(dá)到全連通，是最高效的全連通網(wǎng)絡(luò)。如圖1(a)、(c)、(d)所示。

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

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

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

　　2.1不含迂回路由的情況

　　由上述隨機(jī)圖中節(jié)點(diǎn)數(shù)和邊數(shù)的二次關(guān)系知, 當(dāng)節(jié)點(diǎn)數(shù)N較小時，邊數(shù)L也相對較小，假設(shè)此時網(wǎng)絡(luò)中尚不含迂回路由，即任意兩個節(jié)點(diǎn)間不連通或只有一條通路，此時子圖呈樹結(jié)構(gòu)。在網(wǎng)絡(luò)不含迂回路由的情況下，兩節(jié)點(diǎn)不直接相連的概率為1－p，不通過2跳相連的概率為(1－p2)A1N－2,…, 不通過i(1≤i≤N－2)跳相連的概率為(1－pi)Ai－1N－2(其中Aba表示從a個節(jié)點(diǎn)中選出b個的排列數(shù))。所以無迂回路由(no alternative route)的隨機(jī)圖中任意兩節(jié)點(diǎn)的連通率IRna為：

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

　　整理得：

　　帶入式(1)得：

　　式(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ò)中一個巨大連通子圖和一些較小的連通子圖并存［14］。本文認(rèn)為在巨大連通子圖形成前的第一種形態(tài)，子圖普遍呈樹結(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］:

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

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

　　(1)兩個節(jié)點(diǎn)均位于巨大連通子圖中，可能的節(jié)點(diǎn)對數(shù)為節(jié)點(diǎn)連通；

　　(2)只有一個節(jié)點(diǎn)在巨大連通子圖中，可能的節(jié)點(diǎn)對數(shù)為

　　，節(jié)點(diǎn)不連通；

　　(3)兩個節(jié)點(diǎn)均不在巨大連通子圖中，可能的節(jié)點(diǎn)對數(shù)為根據(jù)上述對不含迂回路由情況下網(wǎng)絡(luò)連通率的討論，其中連通的節(jié)點(diǎn)對數(shù)為。

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

　　其中，為任意實(shí)數(shù)，r為非負(fù)整數(shù)。參數(shù)IRna和S分別由式(4)、(5)給出，第二個等號在N→∞的條件下嚴(yán)格成立。在連接概率p確定的情況下,式(6)是IR關(guān)于N的隱函數(shù)，可以通過先確定S再確定N的方法計(jì)算。

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

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

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

3仿真試驗(yàn)

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

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

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

4結(jié)論

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

　　參考文獻(xiàn)

　　［1］ ERDS P, RNYI A. On random graphs［J］. Publ Math Debrecen, 1959(6): 1-14.

　?。?］ 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.

　?。?］ 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.

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

　?。?］ KRAPIVSKY P L, REDNER S, LEYVRAZ F. Connectivity of growing random networks［J］. Phys. Rev. Lett., 2000,85(21): 4629-4632.

　?。?］ BOLLOBS B. Random graphs［M］. 2nd. Cambridge University Press, 2001.

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

　?。?］ 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.

　?。?0］ 盧友軍, 許道云. 隨機(jī)圖G(n,p)中k團(tuán)的相變性質(zhì)［J］. 貴州大學(xué)學(xué)報(bào)(自然科學(xué)版), 2013, 30(6): 86-90.

　?。?1］ 譚利, 侯振挺. 一類無標(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.

　?。?4］ 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.

　?。?5］ 王彬. 隨機(jī)圖中的兩種相變［D］. 天津: 南開大學(xué), 2011.

　?。?6］ 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.