復(fù)雜網(wǎng)絡(luò)中隨機(jī)圖模型研究

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

(1.成都信息工程學(xué)院數(shù)學(xué)學(xué)院， 四川 成都 610225;2.成都信息工程學(xué)院網(wǎng)絡(luò)工程學(xué)院，四川 成都 610225;3.成都信息工程學(xué)院計(jì)算中心和網(wǎng)絡(luò)輿情研究所，四川 成都 610225)

1 引言

近十多年來，隨著對(duì)復(fù)雜網(wǎng)絡(luò)研究熱潮的興起，隨機(jī)圖成為一種重要的復(fù)雜網(wǎng)絡(luò)模型，常常稱作隨機(jī)網(wǎng)絡(luò)或隨機(jī)圖[1，2]。人們對(duì)復(fù)雜網(wǎng)絡(luò)的魯棒性、傳播動(dòng)力學(xué)等的研究，常常會(huì)用到隨機(jī)圖，即需要生成隨機(jī)圖模型。Erd?s P和Rényi A最早研究隨機(jī)圖時(shí)，他們對(duì)隨機(jī)圖的本質(zhì)做了大量的研究[3]。 隨機(jī)圖包含兩個(gè)最基本的隨機(jī)圖模型[4～6]：第一種隨機(jī)圖模型是對(duì)給定的n個(gè)頂點(diǎn)的空?qǐng)D，任選兩個(gè)頂點(diǎn)，兩個(gè)頂點(diǎn)連邊的概率為p所得到的一個(gè)圖；而第二種隨機(jī)圖模型是隨機(jī)選擇具有M條邊和n個(gè)頂點(diǎn)的一個(gè)圖。第一種隨機(jī)圖模型是由Gilbert E N首先提出的[7]，而第二種隨機(jī)圖模型是由Erd?s P和 Rényi A 提出的[4]，人們?cè)诓恢劣诨煜那疤嵯?，提及隨機(jī)圖是這兩種模型中的一種。時(shí)至今日，隨機(jī)圖又被稱為ER(Erd?s-Rényi)圖。自從隨機(jī)圖建立以來, 對(duì)隨機(jī)圖的研究就從未停止過，隨著對(duì)隨機(jī)圖研究的深入，隨機(jī)圖的理論和應(yīng)用得到極大的發(fā)展，如隨機(jī)圖的連通性[3]、隨機(jī)圖的著色[8]及色數(shù)[9，10]等等。

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

2 去邊的方式生成隨機(jī)圖

隨機(jī)圖模型對(duì)隨機(jī)圖理論及其應(yīng)用和復(fù)雜網(wǎng)絡(luò)的研究非常重要，以往的隨機(jī)圖模型的生成方式均是以加邊的方式生成隨機(jī)圖。由于任意一個(gè)簡(jiǎn)單圖都是完全圖的生成子圖[12]，因此可以用完全圖的生成子圖來構(gòu)造一個(gè)新的圖，即去邊隨機(jī)圖生成算法。

2.1 算法

算法1去邊隨機(jī)圖生成算法。

步驟1給定n個(gè)頂點(diǎn)的完全圖Kn。

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

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

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

2.2 數(shù)值實(shí)驗(yàn)

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

實(shí)驗(yàn)1取節(jié)點(diǎn)數(shù)目為n=3000，然后改變p、q的值，其中p代表加邊概率，q代表去邊概率，要求p+q=1。

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

Table 1 Statistical features of the two classes of graphs,fixed vertices number of the graphs are 3 000表1 兩類圖的統(tǒng)計(jì)特性，其中圖的節(jié)點(diǎn)數(shù)目固定為3 000

注：度數(shù)取整數(shù)。

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

Figure 1 Degree distribution of the graphs with fixed vertices number圖1 頂點(diǎn)數(shù)目固定圖的度分布

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

從以上的實(shí)驗(yàn)結(jié)果可以看到，在圖的頂點(diǎn)數(shù)目不改變的前提下，改變加邊和去邊的概率，只要p+q=1，加邊和去邊的圖的統(tǒng)計(jì)性質(zhì)相同。

實(shí)驗(yàn)2改變生成圖的節(jié)點(diǎn)數(shù)目，而加邊概率和去邊概率不變，觀察兩類圖的統(tǒng)計(jì)特征。節(jié)點(diǎn)數(shù)目n分別取為1 000、1 500、2 000、2 500、3 500不同的值，同樣p代表加邊概率，q代表去邊概率，要求p+q=1。

在表2的結(jié)果中，平均聚類系數(shù)和平均路徑長(zhǎng)度的最大相對(duì)誤差為0.09%，最小相對(duì)誤差為零；而平均度、最大度和最小度的最大相對(duì)誤差為1.8%，最小相對(duì)誤差同樣為零。根據(jù)表2計(jì)算平均度、最大度和最小度的相對(duì)誤差較大的原因，除了隨機(jī)性之外，還因?yàn)槎鹊娜≈禐檎麛?shù)，使有效位數(shù)較少。因此，表2中的兩類圖的這些統(tǒng)計(jì)數(shù)值是十分接近的。

Table 2 Statistical features of the two graphs with changed vertices number表2 兩類圖的統(tǒng)計(jì)特性，其中改變圖的節(jié)點(diǎn)數(shù)目

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

Figure 2 Degree distribution of the graphs with changed vertices number圖2 頂點(diǎn)數(shù)目改變時(shí)圖的度分布

從以上實(shí)驗(yàn)我們可以得到如下結(jié)論：

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

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

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

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

3 連通隨機(jī)圖生成算法

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

3.1 算法

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

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

(2)多次重復(fù)：即當(dāng)連邊概率p較小時(shí)，生成的圖不連通，就進(jìn)行多次重復(fù)。每生成一個(gè)隨機(jī)圖，檢查其連通性，若不連通，再以相同的概率再次生成一個(gè)隨機(jī)圖，直到生成一個(gè)連通的圖為止。這種做法的缺點(diǎn)是顯然的，因?yàn)楫?dāng)p很小時(shí)，重復(fù)的次數(shù)很多，甚至無法得到一個(gè)連通的圖。

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

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

算法2連通隨機(jī)圖生成算法

步驟1給定n個(gè)頂點(diǎn)的完全圖Kn；

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

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

其中，q≤(n-2)/n，因?yàn)闃涫沁厰?shù)最少的連通圖，換言之，對(duì)有n個(gè)頂點(diǎn)的圖，只要邊的數(shù)目小于n-1,則此圖一定不連通[12]。任意一棵樹的點(diǎn)邊關(guān)系是：e=n-1，其中e代表的是樹的邊的數(shù)目，n代表的是樹的頂點(diǎn)數(shù)目[12]。在要生成連通圖的前提下，以去邊的方式，所去掉的邊的數(shù)目不能超過E，而E=qn(n-1)/2，故有E≤n(n-1)/2-(n-1)，又因?yàn)镋=qn(n-1)/2，故q≤(n-2)/n。因?yàn)樽畛醯耐耆珗D是連通的，當(dāng)去邊概率q≤(n-2)/n且去邊時(shí)確保不去割邊，則生成子圖一定是連通的。算法2的時(shí)間復(fù)雜度是O(n4)，其中n代表圖的頂點(diǎn)數(shù)目。

3.2 數(shù)值實(shí)驗(yàn)

接下來的實(shí)驗(yàn)中，比較加邊的方式生成的隨機(jī)圖和去邊的方法生成的隨機(jī)圖的連通性。

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

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

Table 3 Statistical features, when pi≤pc,qi≥qc,n=3000表3 當(dāng)pi≤pc,qi≥qc時(shí)圖的統(tǒng)計(jì)特性(n=3000)

對(duì)于度分布的實(shí)驗(yàn)，其中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 當(dāng)pi≤pc,qi≥qc時(shí)圖的度分布

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

從以上實(shí)驗(yàn)我們可以得到如下結(jié)論：

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

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

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

4 結(jié)束語

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

由于任意一個(gè)靜態(tài)的復(fù)雜網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)(無環(huán)和重邊的圖)都可以認(rèn)為是一個(gè)完全圖的生成子圖，因此基于完全圖的生成子圖，可以得到任意一種復(fù)雜網(wǎng)絡(luò)模型，這一工作有待進(jìn)一步研究。

[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)

附中文參考文獻(xiàn)：

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

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