復雜網絡中隨機圖模型研究

黃 斌，吳春旺，鄭豐華,藺 冰

(1.成都信息工程學院數學學院， 四川 成都 610225;2.成都信息工程學院網絡工程學院，四川 成都 610225;3.成都信息工程學院計算中心和網絡輿情研究所，四川 成都 610225)

1 引言

近十多年來，隨著對復雜網絡研究熱潮的興起，隨機圖成為一種重要的復雜網絡模型，常常稱作隨機網絡或隨機圖[1，2]。人們對復雜網絡的魯棒性、傳播動力學等的研究，常常會用到隨機圖，即需要生成隨機圖模型。Erd?s P和Rényi A最早研究隨機圖時，他們對隨機圖的本質做了大量的研究[3]。 隨機圖包含兩個最基本的隨機圖模型[4～6]：第一種隨機圖模型是對給定的n個頂點的空圖，任選兩個頂點，兩個頂點連邊的概率為p所得到的一個圖；而第二種隨機圖模型是隨機選擇具有M條邊和n個頂點的一個圖。第一種隨機圖模型是由Gilbert E N首先提出的[7]，而第二種隨機圖模型是由Erd?s P和 Rényi A 提出的[4]，人們在不至于混淆的前提下，提及隨機圖是這兩種模型中的一種。時至今日，隨機圖又被稱為ER(Erd?s-Rényi)圖。自從隨機圖建立以來, 對隨機圖的研究就從未停止過，隨著對隨機圖研究的深入，隨機圖的理論和應用得到極大的發展，如隨機圖的連通性[3]、隨機圖的著色[8]及色數[9，10]等等。

在復雜網絡研究中，生成隨機圖的加邊的概率小于其閾值時生成圖是不連通的[3]，這對進一步研究產生了一定的困難，也不便于用隨機圖模仿現實中的網絡，而現實世界的絕大多數網絡都是連通的，如互聯網、電力網、交通網等。另外，隨機圖模型生成算法一般都是用加邊的思想[11]，而用去邊的思想生成隨機圖的方法很少有人研究，Gilbert E N在其文章中只是一筆帶過[7], 并未做進一步的研究和說明，時至今日也沒有用去邊的方法建立隨機圖模型的算法。本文基于完全圖(任意兩個頂點均有邊相連接的簡單圖稱為完全圖，記為Kn)的生成子圖的思想，給出了以去邊的方式生成隨機圖的方法，說明用去邊的方法也能夠生成隨機圖。進一步提出生成連通圖的近似隨機圖算法，通過數值實驗驗證了算法的有效性和適用性。本文所涉及的圖(或網絡的拓撲結構)均為：無權、無向的簡單圖(簡單圖是沒有重邊和環的圖)。

2 去邊的方式生成隨機圖

隨機圖模型對隨機圖理論及其應用和復雜網絡的研究非常重要，以往的隨機圖模型的生成方式均是以加邊的方式生成隨機圖。由于任意一個簡單圖都是完全圖的生成子圖[12]，因此可以用完全圖的生成子圖來構造一個新的圖，即去邊隨機圖生成算法。

2.1 算法

算法1去邊隨機圖生成算法。

步驟1給定n個頂點的完全圖Kn。

步驟2給定概率q, 對Kn中選定的每一條邊以相同的概率q去邊。

步驟3當去掉的邊數達到E時就停止,E代表去掉的邊數目，E=qn(n-1)/2。其中，q代表“去邊”概率，p代表“加邊”概率，p+q=1。

對有固定的n個節點的空圖，如果以概率p隨機加邊，則生成的圖最后有pn(n-1)/2條邊；而對有n個頂點的完全圖，共有n(n-1)/2條邊，當以概率q去邊時，共去掉qn(n-1)/2條邊，此時生成子圖的邊的數目為：n(n-1)/2-qn(n-1)/2=(n(n-1)/2)(1-q)=pn(n-1)/2。因此,無論是加邊還是去邊，只要加邊概率p和去邊q滿足：p+q=1，則生成的圖，在頂點數目相同的前提下，得到的隨機圖的邊的數目也是相同的。無論是加邊還是去邊均具有隨機性，因此這兩種方法生成的是具有相同性質的隨機圖。

2.2 數值實驗

以“加邊”的方式生成的圖是隨機圖，如果以“去邊”的方法得到的圖的統計特性與“加邊”的方式得到的圖的統計特征完全相同，那么以“去邊”的方法生成的也是隨機圖。在刻畫隨機圖的統計特性上，平均聚類系數[13]、平均路徑長度[14]和度分布[15]是最常用的三種參數[16]。在下面的數值實驗中，計算出以這兩種方法得到的圖的平均路徑長度、聚類系數和度分布等統計結果，以此驗證 “去邊”的方法得到的也是隨機圖。在本文的實驗中，計算結果是50次實驗的平均，即在相同的條件下, 對每種方法(如加邊的方法)生成50個圖，計算統計數值的平均值，去邊也一樣。

實驗1取節點數目為n=3000，然后改變p、q的值，其中p代表加邊概率，q代表去邊概率，要求p+q=1。

從表1可以看到，這兩類圖的平均聚類系數、平均路徑長度、平均度、最大度、最小度非常接近，其中聚類系數、平均路徑長度、平均度和最大度的最大相對誤差為3.7%，最小相對誤差為零，對于表1最后一列的最小度，除了最小度取3和4外，其它的最大相對誤差為0.86%，而最小度3和4的相對誤差較大的原因是有效位數太少(表1中度的取值為整數)。另外隨機性也是造成誤差的原因。

Table 1 Statistical features of the two classes of graphs,fixed vertices number of the graphs are 3 000表1 兩類圖的統計特性，其中圖的節點數目固定為3 000

注：度數取整數。

在對隨機圖的研究中，隨機圖的度分布曲線符合泊松分布是隨機圖的一個十分重要的標志。在接下來的實驗中，比較兩種不同方式得到的圖(即以加邊方法得到的隨機圖和以去邊方法得到的圖)的度分布曲線，說明兩類圖的度分布是相同的。在圖1的實驗中，圖的節點數目仍然為n=3000，但只給出了p=0.005、q=0.995(圖1a),p=0.05、q=0.95(圖1b),p=0.5、q=0.5(圖1c)的度分布曲線，由于其它度分布曲線結果完全類似，就沒有一一給出了。

Figure 1 Degree distribution of the graphs with fixed vertices number圖1 頂點數目固定圖的度分布

在圖1的實驗中，以加邊的方式得到的隨機圖，其度分布曲線滿足泊松分布，隨機圖的度分布曲線在其峰值〈k〉處呈現指數下降[3,16]。而以去邊的方式得到的生成子圖的度分布曲線(空心圈)同樣也是在其峰值〈k〉處呈現指數下降。

從以上的實驗結果可以看到，在圖的頂點數目不改變的前提下，改變加邊和去邊的概率，只要p+q=1，加邊和去邊的圖的統計性質相同。

實驗2改變生成圖的節點數目，而加邊概率和去邊概率不變，觀察兩類圖的統計特征。節點數目n分別取為1 000、1 500、2 000、2 500、3 500不同的值，同樣p代表加邊概率，q代表去邊概率，要求p+q=1。

在表2的結果中，平均聚類系數和平均路徑長度的最大相對誤差為0.09%，最小相對誤差為零；而平均度、最大度和最小度的最大相對誤差為1.8%，最小相對誤差同樣為零。根據表2計算平均度、最大度和最小度的相對誤差較大的原因，除了隨機性之外，還因為度的取值為整數，使有效位數較少。因此，表2中的兩類圖的這些統計數值是十分接近的。

Table 2 Statistical features of the two graphs with changed vertices number表2 兩類圖的統計特性，其中改變圖的節點數目

在圖2中同樣只給出了n=1000(圖2a)、n=2000(圖2b)、n=3500(圖2c)的度分布曲線，其結果仍然是：以去邊的方式得到的生成子圖的度分布曲線(空心圈)與隨機圖一樣也是在其峰值〈k〉處呈現指數下降。

Figure 2 Degree distribution of the graphs with changed vertices number圖2 頂點數目改變時圖的度分布

從以上實驗我們可以得到如下結論：

(1)從表1和表2中都可以看出，無論是以加邊方式還是去邊方式所生成得到的圖，其統計結果：最大度、最小度、聚集系數、平均最短路徑和平均度的相對誤差是很小的。

(2)圖1、圖2顯示以這兩種方法生成的圖的度分布曲線均為鐘型曲線，在其峰值〈k〉處呈現指數下降。

(3)在生成隨機圖時應該選擇相對工作量較少的生成方法。以加邊方式生成隨機圖，最終需要添加pn(n-1)/2條邊。當p>0.5時，顯然，用去邊的方式生成的隨機圖，工作量更少，將更加方便和高效，反之亦然。

綜上所述，可以得到如下結論：“去邊隨機圖生成算法”也是生成隨機圖的一種方法。只要p+q=1,無論是以概率p加邊得到的圖，還是以概率q去邊的方式得到的圖，得到的是性質相同的圖，即用“去邊隨機圖生成算法”也可以得到隨機圖，這給隨機圖的生成方式提供了一種新的思路和算法。

3 連通隨機圖生成算法

復雜網絡模型是研究復雜網絡的基礎，因此對網絡模型的研究是復雜網絡很重要的內容。無論是在1998年Watts D J和Strogatz S H引入了小世界網絡模型，稱為WS網絡模型[14],還是在1999年Barabasi A L和Albert R提出了無標度網絡模型，又稱為BA網絡模型[15]，這兩種極其重要的復雜網絡模型，均用到隨機化的思想。在生成BA網絡模型時，網絡模型生成算法中，新添加的邊一個端點是以一定的概率與老節點相連；而WS網絡模型是使用隨機化重連的思想得到的。而隨機圖本身也是很重要的一種復雜網絡模型，人們借用隨機圖的生成方式可以得到隨機網絡模型，又稱為隨機圖。

3.1 算法

對于隨機圖，當n→∞時(n為圖的頂點數目)，如果加邊概率p大于某個臨界值pc∝lnn/n，那么幾乎每一個隨機圖都是連通的。換言之，當連邊概率p小于其臨界值時，得到的圖往往是不連通的[16]。在復雜網絡的研究中，當想得到一個平均度為4(這是常用的復雜網絡平均度)的隨機網絡時，無論網絡的節點數目是100還是10 000，甚至節點數目更多，此時的加邊概率均小于閾值pc，這時得到的往往是不連通的隨機圖。當連邊概率p小于連通閾值pc，又希望得到連通的隨機圖(要求p≥2/n，當p<2/n時生成的網絡始終都是不連通的)，那么目前人們的做法往往是以下三種：

(1)取不連通隨機圖中最大的連通分支。如在計算隨機圖的平均最短路徑時,由于圖不連通，無法計算整個隨機圖的平均最短路徑，其中一種方法就是取整個網絡中的最大連通分支的平均最短路徑來代替整個隨機圖的平均最短路徑。此方法的缺點是求解一個圖的最大連通分支勢必會增加運算量；同時，從網絡節點數上來比較，就已經使得所選擇最大連通分支與整個圖必然是有差別的。

(2)多次重復：即當連邊概率p較小時，生成的圖不連通，就進行多次重復。每生成一個隨機圖，檢查其連通性，若不連通，再以相同的概率再次生成一個隨機圖，直到生成一個連通的圖為止。這種做法的缺點是顯然的，因為當p很小時，重復的次數很多，甚至無法得到一個連通的圖。

(3)提高連邊概率p：若以概率p連邊，無法得到連通的隨機圖，就提高p的值。如果是想得到以概率p連邊的隨機圖，在提高p的值后，顯然違背了初衷。

通過上面的分析，以上三種方法均具有明顯的缺點。那么，有沒有可能，以較小的概率p(p小于連通閾值)生成一個連通的隨機圖或者近似的隨機圖呢？下面就給出一個生成連通的“隨機”圖的算法。之所以在隨機這兩個字加上引號，是因為現在還無法證明它究竟有多么接近隨機圖。從實驗數據上可以說明，以此算法生成的圖一定是連通的，同時在很多性質上是接近于隨機圖的，特別是當p接近pc時。下面算法2的中心思想是不去掉圖的割邊(割邊：設e1是圖G的一條邊，若ω(G-e1)>ω(G)，則稱e1為G的割邊。其中ω(G)為圖G的連通分支數目，G-e1的意思是在圖G中去掉邊e1)，因此將此算法稱為“連通隨機圖生成算法”。

算法2連通隨機圖生成算法

步驟1給定n個頂點的完全圖Kn；

步驟2給定概率q,對Kn中選定的每一條邊以相同的概率q去邊，要求選定的邊不是割邊；

步驟3當去掉的邊數達到E時就停止,其中E代表去掉的邊數目，E=qn(n-1)/2，(其中q≤(n-2)/n)。

其中，q≤(n-2)/n，因為樹是邊數最少的連通圖，換言之，對有n個頂點的圖，只要邊的數目小于n-1,則此圖一定不連通[12]。任意一棵樹的點邊關系是：e=n-1，其中e代表的是樹的邊的數目，n代表的是樹的頂點數目[12]。在要生成連通圖的前提下，以去邊的方式，所去掉的邊的數目不能超過E，而E=qn(n-1)/2，故有E≤n(n-1)/2-(n-1)，又因為E=qn(n-1)/2，故q≤(n-2)/n。因為最初的完全圖是連通的，當去邊概率q≤(n-2)/n且去邊時確保不去割邊，則生成子圖一定是連通的。算法2的時間復雜度是O(n4)，其中n代表圖的頂點數目。

3.2 數值實驗

接下來的實驗中，比較加邊的方式生成的隨機圖和去邊的方法生成的隨機圖的連通性。

實驗3取p1≈pc，其余的p2、p3、p4均小于pc(其中p1>p2>p3>p4)。

從表3可知，當pi小于pc(i=2,3,4)時，用加邊的方式生成的隨機圖均不連通(其中不連通的結論是根據50次實驗結果得到。如果超過25次生成的圖均為不連通的，那么稱為不連通。如果在50次的生成實驗中，有大于或等于25個圖是連通的，那么最終結論是連通的，見表3的最后一列)；而一切用去邊的方法生成的圖均為連通的，即在50次的實驗中，每次得到的圖均為連通的。當加邊概率接近閾值pc時，以去邊的方式得到的圖(qi=1-pi)與加邊得到的隨機圖在統計特性：聚類系數、平均路徑長度等十分接近(參看p1、q1、p2、q2的結果)，但隨著去邊概率的加大，兩類圖統計特性的計算結果相差越來越大(參看p3、q3、p4、q4的結果)，也即在確保圖的連通性的同時，損失了隨機性。

Table 3 Statistical features, when pi≤pc,qi≥qc,n=3000表3 當pi≤pc,qi≥qc時圖的統計特性(n=3000)

對于度分布的實驗，其中p1=0.0027,q1=0.9973(圖3a),p2=0.0025,q2=0.9975(圖3b),p3=0.002,q3=0.998(圖3c)。

Figure 3 Degree distribution of the graphs when pi≤pc,qi≥qc圖3 當pi≤pc,qi≥qc時圖的度分布

在圖3中，以去邊的方式得到的生成子圖和隨機圖(加邊方法得到的圖)一樣也是在其峰值〈k〉處呈現指數下降，但當去邊概率取值很大時(如：p4=0.001,q4=0.999)度分布相差較大，這里雖然沒有畫出圖像，但從表3可以得到這一結果。

從以上實驗我們可以得到如下結論：

(1)當去邊概率q≤(n-2)/n時，以“連通隨機圖生成算法”生成的圖一定連通，即用算法2生成的圖一定連通。

(2)當去邊概率越接近qc(qc=1-pc)時，以去邊的方法得到的圖的性質越接近隨機圖。因此，在復雜網絡的研究中，如果人們希望生成一個低密度的隨機圖，當加邊概率小于連通閾值時，得到的是不連通的圖，但使用“連通隨機圖生成算法”，得到的一定是連通圖。

(3)算法2與算法1相比較只增加了一個條件：要求選定的邊不是割邊。當去邊概率q≤(n-2)/n時，生成子圖邊的數目一定大于或等于(n-1)，當滿足條件后所得的圖一定是連通的。

4 結束語

隨機圖的生成，無論對隨機圖理論還是復雜網絡的研究，都是很重要的內容。本文基于完全圖的生成子圖，得到了一種生成隨機圖的另一種方法(算法1)，即“去邊隨機圖生成算法”，從理論分析和具體實驗都說明以去邊的方式生成的圖與加邊的方式生成的隨機圖是具有相同性質的圖，即都是隨機圖。顯然這為生成隨機圖提供了一種新的思路和一個新的算法。如果當加邊概率p>0.5時，用“去邊隨機圖生成算法”——算法1生成隨機圖的效率比用以往加邊的方法生成隨機圖的效率更高。在生成隨機圖時，當加邊概率小于閾值pc，用加邊的方法得到的隨機圖往往是不連通的，這對得到連通的隨機圖帶來了極大的不便。此時如果選擇不去割邊的隨機圖生成算法，即“連通隨機圖生成算法”——算法2可以得到連通的近似隨機圖，這無疑對復雜網絡的研究提供了一個新的途徑。

由于任意一個靜態的復雜網絡的拓撲結構(無環和重邊的圖)都可以認為是一個完全圖的生成子圖，因此基于完全圖的生成子圖，可以得到任意一種復雜網絡模型，這一工作有待進一步研究。

[1] Newman M E J. Random graphs as models of networks[M]∥Handbook of Graphs and Networks, Weinheim:Wiley, 2003.

[2] Dorogovtsev S N, Goltsev A V,Mendes J F F. Critical phenomena in complex networks[J]. Reviews of Modern Physics, 2008,80(4):1275-1335.

[3] Bollobás B. Random graphs[M].2nd ed. Cambridge:Cambridge University Press,2001.

[4] Erd?s P,Rényi A.On random graphs[J]. Publicationes Mathematicae Debrecen,1959(6):290-297.

[5] Erd?s P. Graph theory and probability[J]. Canadian Journal of Mathematics, 1959(11):34-38.

[6] Bollobás B. Modern graph theory[M]. New York:Springer, 1998.

[7] Gilbert E N. Random graphs[J].Ann. Math. Stat. 1959,30(4):1141-1144.

[8] Bollobás B, Thomason A G. Random graphs of small order[J].Annals of Discrete Mathematics, 1985,28:47-97.

[9] Luczak T.The chromatic number of random graphs[J]. Combinatorica, 1991,11(1):45-54.

[10] Achlioptas D,Naor A,Peres Y.Rigorous location of phase transitions in hard optimization problems[J]. Nature, 2005,435:759-764.

[11] Nobari S, Lu X, Karras P,et al. Fast random graph generation[C]∥Proc of the 14th International Conference on Extending Database Technology,2011:331-342.

[12] Zhang Xian-di, Li Zheng-liang. Graph theory and its applications[M]. Beijing:Higher Education Press, 2005. (in Chinese)

[13] Holland P W, Leinhardt S. Transitivity in structural models of small groups[J]. Comparative Group Studies, 1971,2(2):107-124.

[14] Watts D J, Strogatz S H. Collective dynamics of ‘small-world’ networks[J]. Nature, 1998(393):440-442.

[15] Barabasi A L, Albert R. Emergence of scaling in random networks[J]. Science, 1999,286(5439):509-512.

[16] Wang Xiao-fan, Li Xiang, Chen Guan-rong. Complex networks theory and its applications[M]. Beijing:Tsinghua University Press, 2006.(in Chinese)

附中文參考文獻：

[12] 張先迪, 李正良. 圖論及其應用[M]. 北京:高等教育出版社, 2005.

[16] 汪小帆, 李翔, 陳關榮. 復雜網絡理論及其應用[M]. 北京:清華大學出版社, 2006.