楊宇騏，朱磊

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

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

　　關鍵詞：隨機圖；連通率；子圖

0引言

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

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

1連通率與隨機圖

　　定義連通率(Interconnection Rate，IR)為網絡中連通（直接連接或多跳轉接）的節點對數與總節點對數之比，如圖1(b)所示。給定網絡拓撲，便能較容易地得到該網絡的連通率。對于由分散節點組成的網絡，連通率為0，對于連通網絡，連通率為1。圖的最小生成樹以最小的邊數達到全連通，是最高效的全連通網絡。如圖1(a)、(c)、(d)所示。

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

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

2隨機圖的連通率

　　2.1不含迂回路由的情況

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

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

　　整理得：

　　帶入式(1)得：

　　式(4)即為不含迂回路由的情況下節點間的連通率，根據前述隨機圖的性質，此連通率也為網絡的連通率。

　　從演化角度講，在實現連通前，隨機圖經歷了兩種形態。第一種形態是網絡由許多規模較小的連通子圖組成，第二種形態是網絡中一個巨大連通子圖和一些較小的連通子圖并存［14］。本文認為在巨大連通子圖形成前的第一種形態，子圖普遍呈樹結構，即不含迂回路由。此觀點將在仿真試驗部分得到驗證。下面討論第二種形態下的連通率。

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

　　在隨機圖中, 巨大連通子圖所含節點數占網絡節點總數的比例S為［9］:

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

　　在巨大連通子圖形成后，從網絡中隨機選取兩個節點計算連通率，存在以下3種情況：

　　(1)兩個節點均位于巨大連通子圖中，可能的節點對數為節點連通；

　　(2)只有一個節點在巨大連通子圖中，可能的節點對數為

　　，節點不連通；

　　(3)兩個節點均不在巨大連通子圖中，可能的節點對數為根據上述對不含迂回路由情況下網絡連通率的討論，其中連通的節點對數為。

　　綜上，巨大連通子圖形成后網絡的連通率為：

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

　　2.3網絡的相變態

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

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

3仿真試驗

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

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

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

4結論

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

　　參考文獻

　　［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］ 熊煒, 李清泉. 高速公路場景中車用自組織網絡的節點度［J］. 電子與信息學報, 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.

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

　　［8］ 黃斌, 吳春旺, 鄭豐華, 等. 復雜網絡中隨機圖模型研究［J］. 計算機工程與科學, 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團的相變性質［J］. 貴州大學學報(自然科學版), 2013, 30(6): 86-90.

　　［11］ 譚利, 侯振挺. 一類無標度隨機圖的度序列［J］. 應用數學學報, 2011, 34(3): 440-447.

　　［12］ 汪小帆, 李翔, 陳關榮. 復雜網絡理論及其應用［M］. 北京:清華大學出版社,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］. 天津: 南開大學, 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.