具有任意度分布的隨機(jī)圖及其應(yīng)用

1、具有任意度分布的隨機(jī)圖及其應(yīng)用M.E.J. Newman, S.H. Strogatz, and D.J. Watts, Phys. Rev. E64, 026118 (2001)近來關(guān)于社交網(wǎng)絡(luò)和互聯(lián)網(wǎng)的結(jié)構(gòu)的工作已經(jīng)集中關(guān)注具有與在過去廣泛研究的泊松度分布顯著不同的頂點(diǎn)度的分布的圖。在本文中，我們?cè)敿?xì)地開發(fā)具有任意度分布的隨機(jī)圖的理論。除了簡(jiǎn)單的無向，單向圖，我們考查定向和二分圖的屬性。在其他結(jié)果中，我們得到精確表達(dá)式，其中巨分量首先形成的相變的位置，平均分量大小，巨分量的大?。ㄈ绻械脑挘?，距離隨機(jī)選擇的頂點(diǎn)一定距離的頂點(diǎn)的平均數(shù)量，以及圖中頂點(diǎn)-頂點(diǎn)距離的平均。我們將我們的理論應(yīng)用于一

2、些真實(shí)世界的圖形，包括科學(xué)家和財(cái)富1000強(qiáng)公司董事的全球網(wǎng)絡(luò)和協(xié)作圖。我們證明，在某些情況下隨機(jī)圖與適當(dāng)?shù)捻旤c(diǎn)度分布預(yù)測(cè)是令人驚訝的準(zhǔn)確性的現(xiàn)實(shí)世界的行為，而在其他人有一個(gè)可衡量的理論與現(xiàn)實(shí)之間的差異，可能表明網(wǎng)絡(luò)中的額外的社會(huì)結(jié)構(gòu)的存在不被隨機(jī)圖捕獲。1、介紹。隨機(jī)圖1是點(diǎn)或頂點(diǎn)的集合，具有線或邊，其隨機(jī)連接它們的對(duì)圖1（a）。隨機(jī)圖的研究有悠久的歷史。從二十世紀(jì)五十年代和二十世紀(jì)六十年代Erdo和Re'nyi的有影響力的工作開始，隨機(jī)圖論已經(jīng)發(fā)展成為現(xiàn)代離散數(shù)學(xué)的支柱之一，并產(chǎn)生了大量的結(jié)果，它們?cè)S多非常巧妙，描述了圖形的統(tǒng)計(jì)特性，例如組件尺寸的分布，巨分量（giantcompo

3、nent）的存在和大小以及典型的頂點(diǎn)-頂點(diǎn)距離。在幾乎所有這些研究中，已經(jīng)假設(shè)兩個(gè)頂點(diǎn)之間的邊的存在或不存在與任何其它邊的存在或不存在無關(guān)，使得每個(gè)邊可以被認(rèn)為以獨(dú)立的概率 p存在。如果在圖中存在 N個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)平均連接 z條邊，則顯然p = z / （N-1） 是很平常的，其對(duì)于大的 N通常由z / N近似。連接到任何特定頂點(diǎn)的邊的數(shù)量被稱為該頂點(diǎn)的度k,并且具有由下式給出的概率分布pkiN A1八一二以=5»（15-其中第二等式在大 N的極限中變得精確。這種分布我們認(rèn)為是泊松分布：普通隨機(jī)圖頂點(diǎn)度具有泊松分布，這是一個(gè) 關(guān)鍵點(diǎn)，正如我們現(xiàn)在解釋的。隨機(jī)圖形不僅僅是一個(gè)數(shù)學(xué)玩

4、具；它們已廣泛用作各種類型的現(xiàn)實(shí)世界網(wǎng)絡(luò)的模型，特別是在流行病學(xué)中。疾病通過社區(qū)的傳播強(qiáng)烈依賴于感染該疾病的人和對(duì)其感染的人之間的接觸模式。該模式可以描述為網(wǎng)絡(luò)，其中個(gè)體由能夠 通過邊傳播疾病的頂點(diǎn)和接觸表示。被稱為易感/感染/恢復(fù)模型的大類流行病學(xué)模型5-7經(jīng)常使用所謂的完全混合近似，這是假設(shè)接觸是隨機(jī)和不相關(guān)的，即它們形成隨機(jī)圖。然而，隨機(jī)圖表證明具有作為這種現(xiàn)實(shí)世界現(xiàn)象的模型的嚴(yán)重缺點(diǎn)。雖然很難通過實(shí)驗(yàn)確定疾病傳播的聯(lián)系網(wǎng)絡(luò)的結(jié)構(gòu)8,已經(jīng)對(duì)其他社會(huì)網(wǎng)絡(luò)進(jìn)行了研究，例如各種社區(qū)內(nèi)的友誼網(wǎng)絡(luò)9-11,網(wǎng)絡(luò)電話呼叫12,13,航空公司時(shí)間表14和電網(wǎng)15,以及物理或生物系統(tǒng)網(wǎng)絡(luò)，包括神經(jīng)網(wǎng)絡(luò)1

5、5,聚合物的結(jié)構(gòu)和構(gòu)象空間 16,17 ，代謝途徑18,19和食物網(wǎng)20,21。發(fā)現(xiàn)13,14在許多這些網(wǎng)絡(luò)中的頂點(diǎn)度的分布與泊松分布-通常是巨大的不同-可測(cè)量不同-這強(qiáng)烈暗示，如其他地方22所強(qiáng)調(diào)的，這樣的網(wǎng)絡(luò)，我們會(huì)錯(cuò)過，如果我們用普通（泊松）隨機(jī)圖來近似它們。（圖1: （a）隨機(jī)圖的示意圖，圓表示頂點(diǎn)，線表示邊。（ b）有向隨機(jī)圖，即其中每個(gè)邊僅在一個(gè)方向上延伸的另一個(gè)廣泛研究的網(wǎng)絡(luò)是互聯(lián)網(wǎng)，其結(jié)構(gòu)已經(jīng)吸引了非常大量的細(xì)查，學(xué)術(shù)和其他方面，從1993年開始疾速上升到公眾可見度。世界各地的網(wǎng)頁可以被認(rèn)為是一個(gè)圖形和它們之間的超鏈接作為邊。經(jīng)驗(yàn)研究23-26已經(jīng)表明，該圖具有頂點(diǎn)度的分布，其

6、是嚴(yán)重偏斜的并且具有指數(shù)在-2和-3之間的脂肪（哥律）尾。（互聯(lián)網(wǎng)的基礎(chǔ)物理結(jié)構(gòu)也具有這種類型的度分布）這種分布不同于泊松，因此我們預(yù)期簡(jiǎn)單的隨機(jī)圖給出網(wǎng)絡(luò)的結(jié)構(gòu)性質(zhì)的非常差的近似。然而， 網(wǎng)絡(luò)在另一方面與隨機(jī)圖不同：它是定向的。網(wǎng)絡(luò)上的鏈接從一個(gè)頁面到另一個(gè)頁面只在一個(gè)方向上引導(dǎo)參見圖1（b）。如Broder等人26,這對(duì)一個(gè)頁面從另一個(gè)頁面的典型可訪問性有重大的實(shí)際影響，這種效果也不會(huì)被簡(jiǎn)單的（無向） 隨機(jī)圖模型捕獲。已經(jīng)吸引細(xì)查的另一類網(wǎng)絡(luò)是協(xié)作網(wǎng)絡(luò)類。這種網(wǎng)絡(luò)的例子包括公司董事會(huì)28-31,公司共同所有權(quán)網(wǎng)絡(luò)32,科學(xué)家33-37和電影演員15的合作。除了具有強(qiáng)非泊松度分布14,36,

7、這些網(wǎng)絡(luò)具有二分體結(jié)構(gòu)；在圖上存在兩種不同類 型的頂點(diǎn)，其中鏈接僅在不同種類的頂點(diǎn)之間運(yùn)行38,參見圖2。例如，在電影演員的情況下，兩種類型的頂點(diǎn)是電影和演員，并且網(wǎng)絡(luò)可以表示為具有在每個(gè)電影和出現(xiàn)在其中的演員之間運(yùn)行的邊的圖形。研究人員還考慮了這個(gè)圖 的投影到僅僅演員的單一空間，也稱為單模網(wǎng)絡(luò)38。在這樣的投影中，兩個(gè)演員被認(rèn)為是連接的，如果他們一起出現(xiàn)在電影中。然而，單模式網(wǎng)絡(luò)的構(gòu)造涉及丟棄包含在原始二分網(wǎng)絡(luò)中的一些信息，并且出于這個(gè)原因，更期望使用完全二分體結(jié)構(gòu)來模型化協(xié)作網(wǎng)絡(luò)?？紤]到目前在這里描述的許多圖的結(jié)構(gòu)的高度關(guān)注39,并且給定它們與在過去研究的普通隨機(jī)圖的實(shí)質(zhì)性差異,如果我們可

8、以推廣數(shù)學(xué)的隨機(jī)圖到非泊松度分布，以及定向和二分圖。在本文中，我們只是這樣做，詳細(xì)說明了每個(gè) 這些圖類型的統(tǒng)計(jì)屬性如何可以精確計(jì)算在大圖規(guī)模的限制下。我們還舉例說明了我們的理論應(yīng)用于一些真實(shí)世界網(wǎng) 絡(luò)的建模，包括 www和協(xié)作圖。(圖2:二分圖的示意圖(左)，例如電影和出現(xiàn)在其中的演員的圖。在這個(gè)小圖中，我們有四個(gè)電影，標(biāo)記為1到4,和11個(gè)演員，標(biāo)記為 A到K,邊將每個(gè)電影連接到演員的演員。在圖片的右半部分，我們顯示了11個(gè)演員的圖形的單模式投影。)展2、具有任意度分布的隨機(jī)圖。在本節(jié)中，我們開發(fā)了一種公式，用于計(jì)算各種數(shù)量，包括局部和全局的大型單向無向圖，其頂點(diǎn)的度具有任意概率分布。在所有

9、方面，除了它們的度分布之外，這些圖被假定為完全隨機(jī)的。這意味 著所有頂點(diǎn)的度是從指定分布繪制的獨(dú)立的相同分布的隨機(jī)整數(shù)。對(duì)于這些度的給定選擇，也稱為“度序列”，從具 有該度序列的所有圖的集合中隨機(jī)均勻地選擇圖。在本文中計(jì)算的所有屬性在以這種方式生成的圖的集合上被平均。在大圖規(guī)模的限制中，等價(jià)過程是僅研究一個(gè)特定度序列，在具有該序列的所有圖上均勻地平均，其中選擇該序列以盡可能接近期望的概率分布。后一個(gè)過程可以被認(rèn)為是隨機(jī)圖的“微規(guī)則集合"，其中前者是一個(gè)“規(guī)范集合”。對(duì)任意度分布的隨機(jī)圖一些結(jié)果是已知的：在兩個(gè)美麗的最近的論文40,41, Molloy和Reed已經(jīng)得出了巨分量首次出現(xiàn)

10、的相變位置的公式，以及巨分量的大小。(這些結(jié)果是在微規(guī)模集合內(nèi)計(jì)算的，但同樣適用于大系統(tǒng)大小限制 中的規(guī)范)。本文中提出的公式給出了這些結(jié)果的另一種推導(dǎo)，也提供了一個(gè)獲得其他感興趣的量的框架，其中一些 我們計(jì)算。在第三和第四章中，我們將公式擴(kuò)展到有向圖(例如萬維網(wǎng))和二分圖(例如協(xié)作圖)的情況。A生成函數(shù)。我們的方法基于生成函數(shù)42,對(duì)于我們的目的其中最根本的，是生成函數(shù)Go(X)的頂點(diǎn)度k的概率分布。假設(shè)我們有一個(gè)不可分無向圖-一個(gè)熟人網(wǎng)絡(luò)，例如大的 N, N個(gè)頂點(diǎn)。 我們定義行口二E PkJ其中pk是圖上隨機(jī)選擇的頂點(diǎn)具有度 k的概率。假設(shè)分布 pk正確地歸一化，因此GO(1)=L對(duì)于這里

11、考慮的所有生成函數(shù)也是如此，只有一些重要的例外，我們將在適當(dāng)?shù)狞c(diǎn)注釋。因?yàn)楦怕史植际菤w一化的和正定的，Go(x)對(duì)于所有|x| W1也是絕對(duì)收斂的，因此在該區(qū)域中沒有奇點(diǎn)。本文的所有計(jì)算將局限于|x| E1的區(qū)域。函數(shù)Go(x)以及實(shí)際上任何概率生成函數(shù)具有許多屬性將證明在后續(xù)開發(fā)中有用的。導(dǎo)數(shù)。概率pk由G0的第k階導(dǎo)數(shù)給出1仆I內(nèi)=RkJ因此一個(gè)函數(shù)Go(x)概括包含離散概率分布 pk的所有信息，我們說函數(shù) Go(x) “生成”概率分布 p-矩。由生成函數(shù)生成的概率分布的平均值-例如，在G0(x)的情況下的頂點(diǎn)的平均度 z由下式給出：z =(k)= E kpk=G.(5)k因此，如果我們可

12、以計(jì)算生成函數(shù)，我們也可以計(jì)算它生成的概率分布的平均值。也可以從更高的導(dǎo)數(shù)計(jì)算更高的分布矩。一般來說，我們有r d yt 吁型3T卜H g。Lj嘉。如果通過給定生成函數(shù)生成對(duì)象的屬性k的分布，則通過該生成函數(shù)的 m次哥生成對(duì)對(duì)象的 m次獨(dú)立實(shí)現(xiàn)之G0(x)2可以擴(kuò)展為間總和為k的分布。例如，如果我們從大圖中隨機(jī)選擇 m個(gè)頂點(diǎn)，則這些頂點(diǎn)的度的和的分布由 G0(x)m生成。為了看到為什么會(huì)這樣，考慮只有兩個(gè)頂點(diǎn)的簡(jiǎn)單情況。單個(gè)頂點(diǎn)的生成函數(shù)的平方=PqP(A° + (PM+PlPo*JK+ 3p/PiPi+9o)M+ (廣或a+Pi/b+Pmi+PaPo)工？+*一 很清楚，該表達(dá)式中

13、 xn的哥的系數(shù)正好是所有乘積 Pj Pk的和，使得j + k = n ,因此正確地給出兩個(gè)頂點(diǎn)的度的和為n 的概率。簡(jiǎn)單地說服自己，這個(gè)屬性也擴(kuò)展到生成函數(shù)的所有更高的哥。所有這些屬性將用于本文中給出的推導(dǎo)。對(duì)我們來說另一個(gè)重要的量是通過隨機(jī)選擇的邊到達(dá)的頂點(diǎn)的度分布。這樣的邊以與該頂點(diǎn)的度成比例的概率到 達(dá)頂點(diǎn)，因此頂點(diǎn)具有與 kpk成比例的度的概率分布。正確歸一化的分布由? w a(K)- =x£機(jī) 5k生成。如果我們從隨機(jī)選擇的頂點(diǎn)開始并沿著該頂點(diǎn)的每個(gè)邊到達(dá)k個(gè)最近鄰居，則到達(dá)的每個(gè)頂點(diǎn)具有由該函數(shù)剩余輸出邊生成的分布，除以 x的一次哥，以允許對(duì)于我們到達(dá)的邊。因此，輸出邊

14、的分布由函數(shù)生成GQ) =Gg)其中z是平均頂點(diǎn)度，如前所述。這些輸出邊中的任何一個(gè)連接到我們開始的原始頂點(diǎn)或者其任何其他直接鄰居的概 率為N,，因此可以在大 N的極限中被忽略。因此，利用上述生成函數(shù)的“哥”屬性，用于原始頂點(diǎn)的第二鄰居的數(shù)目的概率分布的生成函數(shù)可以被寫為k類似地，第三最近鄰的分布由G0(G(G(x)生成，等等。第二鄰居的平均數(shù)Z2是z3= G0(Gi(x)=G；(1)G；(1) = G；(1)> (11)ILJjt I其中我們已經(jīng)利用了事實(shí)：Gi(1)=1.(可能有人試圖推測(cè)，由于第一相鄰的平均數(shù)是G0(1),等式(5),以及第二相鄰的平均數(shù)是 G0(1),方程(11)

15、,那么第m個(gè)鄰居的平均數(shù)應(yīng)該由在 x = 1時(shí)評(píng)估的Go的第m個(gè)導(dǎo)數(shù)給出，然而，如第二章F所示，這個(gè)猜想是錯(cuò)誤的。)B例子。為了使事情更具體，我們立即介紹一些具體圖表的例子來說明如何進(jìn)行這些計(jì)算。(a) Poisson分布圖。這種類型的圖形的最簡(jiǎn)單的例子是其中度分布是二項(xiàng)式的，或者是在大N極限中的泊松。這種分布產(chǎn)生了許多數(shù)學(xué)家研究的標(biāo)準(zhǔn)隨機(jī)圖，并在第一章中討論。 在該圖中任何兩個(gè)頂點(diǎn)之間的邊的存在的概率p = z /N對(duì)于所有頂點(diǎn)是相同的，并且 Go(X)由XG式彳)=2 I Jp*( 1 尸)WT/=(1-(12) k I其中最后的等式適用于極限N- 8。然后平凡的表明頂點(diǎn)的平均度確實(shí)是G0

16、(1) = z.,度的概率分布由pk = zke7/k!給出，這是普通泊松分布。還要注意對(duì)于這種特殊情況，我們有G1(x)=G0(x),使得在一個(gè)頂點(diǎn)的輸出邊的分布是相同的，不管我們是通過隨機(jī)選擇一個(gè)頂點(diǎn)到達(dá)那里，或者隨機(jī)選擇邊。這個(gè)屬性是泊松分布隨機(jī)圖所特有的，這就是為 什么這種隨機(jī)圖的理論特別簡(jiǎn)單的原因。(b)指數(shù)分布圖。也許下一個(gè)最簡(jiǎn)單的類型圖是頂點(diǎn)度具有指數(shù)分布的圖pk = (l-e-UK)ek/K,(13)其中K是常數(shù)。此分布的生成函數(shù)是GOU) = (1-<I/K)S u=-, (14)a=o1 xeG(幻=1Uk1 一 e(15)具有指數(shù)度分布的圖的示例在第五章A中給出。(

17、c)嘉律分布圖。最近對(duì)www網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)的屬性的興趣導(dǎo)致我們調(diào)查頂點(diǎn)度具有哥律分布的圖的屬性。這樣 的圖形已經(jīng)討論由 Baraba's與同事22,23和Aiello等人13。在本文中，我們將看到度分布由下式給出的圖pk = CkTek/K for AMI,(16)其中C,七和K是常數(shù)。包含指數(shù)截止的原因有兩個(gè)：首先許多真實(shí)世界的圖似乎顯示出這個(gè)截止有7它使得分布可歸一化，而不只是 2 >2o14,36;第二，對(duì)所常數(shù)C通過歸一化的要求而固定，得到 crLXe-g) 一 1 人一 - kfKPk=1 fbr 上三 I,L。勺(17)其中Lin(x)是x的第n個(gè)多重對(duì)數(shù)函數(shù)。對(duì)于那

18、些不熟悉這個(gè)函數(shù)的人來說，它對(duì)于我們的目的的突出特征在于，對(duì)于所有n,在x = 0處是零并且在0Ex<1的范圍內(nèi)是實(shí)數(shù)，有限和單調(diào)遞增。它也隨著n的增加而減小，并且對(duì)于n<1僅在x= 1處具有極點(diǎn)，盡管其在 n = 1下具有有效的分析延續(xù)，其在x = 1處取值，(n)。將式(17)代入式(2)在極限設(shè)一00中，參考文獻(xiàn),我們發(fā)現(xiàn)具有這種度分布的圖的生成函數(shù)是Gg)=-.13和23中考慮的情況-簡(jiǎn)化為d3=而，(IS)(19)函數(shù)Gi (x)由下式給出l必)(20)因此，例如，隨機(jī)選擇的頂點(diǎn)的鄰居的平均數(shù)量是(21J第二鄰居的平均數(shù)為甘 LiT_2(e2 = G£ 1)=(

19、22)(d)具有任意指定度分布的圖。在某些情況下，我們希望模擬具有已知度分布的特定現(xiàn)實(shí)世界圖-因?yàn)槲覀兛梢灾苯訙y(cè)量它們。引言中描述的許多圖屬于此類別。對(duì)于這些圖，我們知道具有度k的頂點(diǎn)的確切數(shù)目nk ,因此我們可以以有限多項(xiàng)式的形式寫下該概率分布的精確生成函數(shù)(23)其中分母中的和確保生成函數(shù)被正確地歸一化。例如，假設(shè)在一個(gè)1000人的社區(qū)中，每個(gè)人知道0和5之間的其他人,每個(gè)類別的確切人數(shù)，從零到五： 86,150,363,238,109,54。然后，該分布將由多項(xiàng)式生成(24)86+ 150x 4- 363/ +4-109x4 + 54，1000C分量大小。我們現(xiàn)在可以計(jì)算我們的圖形的一些

20、感興趣的屬性。首先讓我們考慮圖中連接分量的大小分布。設(shè)H1(x)是用于通過選擇隨機(jī)邊并且通過其到其端點(diǎn)之一而到達(dá)的分量大小的分布的生成函數(shù)。我們明確排除H(x)巨分量，如果有一個(gè)；巨分量在下面分開處理。因此，除了當(dāng)我們恰好處于巨分量出現(xiàn)的相變時(shí)，典型的分量大小是有限的，并且包含邊的閉環(huán)的分量的機(jī)會(huì)為N",其在大N的極限中可以忽略。意味著由H1(x)生成的分量的分布可以用圖3表示;每個(gè)組件都是樹狀結(jié)構(gòu)，包括我們通過初始邊到達(dá)的單個(gè)站點(diǎn)，加上任何數(shù)量(包括零)的其他樹狀集群，具有相同的大小分布，通過單個(gè)邊連接到它。如果我們用 qk表示初始站點(diǎn)有k個(gè)邊出現(xiàn)的概率，而不是我們沿著其進(jìn)大小的生

21、成函數(shù)是H0(x)=xG0(HJ(x)t(27)(25)來的邊，那么，利用第二方q噌aq即上斕加好遒即評(píng)F +然而，qk只是生成函數(shù) G（x）,式（9）中的xk的系數(shù)，因此等式（25）也可以寫Hl（x）=xGl（Hl（x）.（26）（圖3:通過隨機(jī)選擇的邊達(dá)到的頂點(diǎn)的連接分量的求和原理 示意圖。每個(gè)這樣的分量（左手側(cè)）的概率可以表示為僅有 單個(gè)頂點(diǎn)，有連接到一個(gè)其它分量的單個(gè)頂點(diǎn)或兩個(gè)其他分 量的概率的和（右手側(cè)），以及等等。整個(gè)和可以以閉合形 式如式（26）表不）如果我們從一個(gè)隨機(jī)選擇的頂點(diǎn)開始，那么我們?cè)诿總€(gè)邊的結(jié)束處有一個(gè)這樣的分量離開該頂點(diǎn)，因此整個(gè)分量因此，原則上給定函數(shù) Go（x）

22、和Gi（x）,我們可以對(duì)Hi（x）解出方程（26）,并代入式（27）得到H0（x）。然后我們可以通過取H0的s階導(dǎo)數(shù)找到隨機(jī)選擇的頂點(diǎn)屬于大小為s的分量的概率。實(shí)際上，不幸的是，這通常是不可能的；方程（26）是一個(gè)復(fù)雜且經(jīng)常抽象的方程，很少有一個(gè)已知的解。另一方面，我們注意到，H1（x）（以及s階導(dǎo)數(shù)）的泰勒展開100個(gè)導(dǎo)數(shù)。否則，可以通過數(shù)值迭代和從方中的xs的系數(shù)僅由方程（27）的s+ 1次迭代精確給出，從Hi=1開始，使得由Ho（x）產(chǎn)生的分布可以在有限時(shí)間內(nèi)精確 地計(jì)算有限階數(shù)。使用當(dāng)前的符號(hào)操作程序，很可能以這種方式推導(dǎo)前Ps：-dz(28)程（4）通過數(shù)值微分計(jì)算的簇大小的分布來找

23、到近似解。由于數(shù)值導(dǎo)數(shù)的直接估計(jì)容易出現(xiàn)機(jī)器精度問題，我們建議 通過Cauchy公式的數(shù)值積分來評(píng)估導(dǎo)數(shù)，給出簇大小的概率分布 I d'Hop = ="s s dzs43。通過使用最大可能輪廓獲得最佳數(shù)值精度，條件是其不包含生成函數(shù)的極點(diǎn)。這個(gè)條件滿足的最大輪廓一般是單位圓 憶|=1 （見第二章A）,我們建議將這個(gè)輪廓用于公式（28）。使用這種方法可以毫無困難地找到函數(shù)的一千個(gè)導(dǎo)數(shù)D平均分量大小，相變和巨分量。雖然通常不可能在圖上找到用于集群大小的完全分布的閉合形式表達(dá)式，但是我們可以從等式（26）和（27）中找到集群的平均屬性的閉合形式表達(dá)式。例如，對(duì)于在圖中沒有巨分量的情

24、況，隨 機(jī)選擇的頂點(diǎn)所屬的分量的平均大小以正常方式通過<$=%=1+G/.(29)從方程（26）可得因此片+ ,(30)1+Z| - Z7(3D其中z產(chǎn)z是頂點(diǎn)的鄰居的平均數(shù)， Z2是第二鄰居的平均數(shù)。我們看到,G；（l）=l.這一點(diǎn)標(biāo)志著巨分量首先出現(xiàn)的相變。將方程（2）和（9）代入方程2 k（k-2）pk = 0.這個(gè)表達(dá)式發(fā)散當(dāng)（32）（32）,我們也可以寫相變的條件為(33)實(shí)際上，由于當(dāng)邊加到圖中時(shí)這個(gè)總和單調(diào)增加，因此,當(dāng)且僅當(dāng)這個(gè)和是正的時(shí)，巨分量存在。這個(gè)結(jié)果是由Molloy和Reed 40通過不同的方法得到的。同樣可以從等式（31）導(dǎo)出的等價(jià)且直觀的合理說法是，當(dāng)且僅當(dāng)

25、z2>4時(shí)，巨分量存在。我們的生成函數(shù)形式仍然有效，當(dāng)在圖中有一個(gè)巨分量,但是由定義,Ho（x）然后生成的分量大小的概率分布除1-S,其中S是巨分了巨分量。這意味著 H0（1）不再是單位，因?yàn)樗鼘?duì)于迄今為止考慮的其他生成函數(shù)，而是替換取值量占據(jù)的圖的分?jǐn)?shù)。我們可以使用它來從等式(26)和(27)計(jì)算巨分量的大小，從而:S=lGo ,其中u三Hi(1)是最小的非負(fù)實(shí)數(shù)解 =G ().(34)(35)這個(gè)結(jié)果是由 Molloy和Reed 41用不同的方法推導(dǎo)出來的。平均分量大小的正確的一般表達(dá)式，如果有一個(gè)，除去(形式無限)巨分量，是2 ZU甘世“ ) +,-1 -GZ/if)當(dāng)不存在巨分量

26、(S = 0, u = 1)時(shí)，等價(jià)于等式(31)。=1 4I -S I - G；3(36)例如，在具有泊松度分布的普通隨機(jī)圖中，我們有 Go(jr) = G|(戈)=巴二口-1)式(12),因此我們簡(jiǎn)單地發(fā)現(xiàn)1-S = u是u = G0 (u)的一個(gè)解，或等效地5=1(37)平均分量大小由下式給出=,(38)這些都是眾所周知的結(jié)果1。-對(duì)于具有純哥律分布的圖具有KT的的等式(17), S由等式(34)給出，其中u是最小的非負(fù)實(shí)數(shù)解Li1。1)(39)對(duì)于所有的飛<2,這給出u = 0,并且因此S = 1,這意味著隨機(jī)選擇的頂點(diǎn)屬于巨分量的概率趨于1當(dāng)kt8。對(duì)于T> 2的圖，屬于

27、巨分量的概率嚴(yán)格小于1,即使對(duì)于無窮大ko換句話說，T <2巨分量基本上填充整個(gè)圖形，但> > 2不是。這些2果是由 Aiello等人通過不同的方法得到的13。E群集大小分布的漸近形式。關(guān)于生成函數(shù)系數(shù)的漸進(jìn)性質(zhì)的各種結(jié)果是已知的，其中一些可以有用地應(yīng)用于由H0(x)生成的簇大小Ps的分布。接近相變，我們期望分布Ps的尾部表現(xiàn)為(40)其中常數(shù)口和s可以從H0(x)的性質(zhì)計(jì)算如下。截止參數(shù)s*與生成函數(shù)的收斂半徑| x * |簡(jiǎn)單地相關(guān)42,44,根據(jù)爐=6.(41)收斂半徑|x*|等于最靠近原點(diǎn)的 H0(x)中的奇異點(diǎn)的位置 x*的大小。從等式(27),我們看到這樣的奇點(diǎn)可

28、以通過 G0(x)中的單項(xiàng)或通過 H1(x)中的單項(xiàng)而產(chǎn)生。然而，由于已知G0(x)中的第一奇點(diǎn)在單位圓外(Sec.IIA),并且當(dāng)我們進(jìn)入相變時(shí)，H1(x)中的第一奇點(diǎn)傾向于 x = 1 (見下文)，因此，充分接近相變，最接近原點(diǎn)的H0(x)中的奇點(diǎn)也是H1(x)中的奇點(diǎn)。有了這個(gè)結(jié)果，x*很容易計(jì)算。雖然我們通常不具有用于 H1(x)的閉合表達(dá)式，但是很容易導(dǎo)出它的反函數(shù)。將w = H1(x)和x =H/(x)代入式(26)并重新排列，我們發(fā)現(xiàn)Gi(w)感興趣的奇異點(diǎn)對(duì)應(yīng)于 H(w)的導(dǎo)數(shù)為零的點(diǎn) w* ,這是它的一個(gè)解G|(u*)-w*G；(h*) = 0,(43)那么x* (并且因此s

29、*)由等式(42)給出。注意，不能保證等式(43)具有有限解，并且如果不是，則Ps通常不會(huì)遵循等式(40)的形式。當(dāng)我們正好處于系統(tǒng)的相變時(shí)，我們有G1(1) =G；(1)=1,因此方程(43)的解給出w* = x* = 1-我們使用上述結(jié)果-和s*一 0°。我們可以使用在轉(zhuǎn)變時(shí) x* = 1的事實(shí)來計(jì)算指數(shù) 口的值如下。通過在等式(42)中放置w = 1 + &來擴(kuò)展 H1(w)關(guān)于w*= 1 ,我們發(fā)現(xiàn)I + Q= I - 彳I )9 + 0(?),(44)其中我們?cè)谙嘧儠r(shí)使用 Gi (1) =G；(1) =1,只要G；(1) #0,這通常不是，這意味著H1(x)以及H0

30、(x)具有形式0(工)(1一X)“as x1,(45)其中P=1/2o該指數(shù)與指數(shù)a如下相關(guān)。等式(40)意味著H0(x)可以寫成形式0 1H"o(G=> V+cSSaes/sxs+ 6(a),(46)其中C是常數(shù)，并且假定最后(誤差)項(xiàng)Ma)遠(yuǎn)小于第二項(xiàng)。該表達(dá)式中的第一項(xiàng)是有限多項(xiàng)式，因此在有限平面上沒有奇異點(diǎn)；奇異性存在于第二項(xiàng)中。使用該方程，指數(shù) P可以寫為lim 1 + (x 1)lim limTEE Jr-# |i=Jim lim -1-1 x r(3 of, Inx)In jf I'(2 a Inx) "(47)其中用積分來代替總和，因?yàn)閍變大，

31、并且F(v,u)是不完全的函數(shù)。以指定的順序取極限并重新排列a ,得到(4g)不考率度分布，除了在G；(1)消失的特殊情況下見式(44)。結(jié)果a = 3/2已知為普通泊松隨機(jī)圖1,但不是其他度分布。F鄰居數(shù)和平均路徑長(zhǎng)度。我們現(xiàn)在轉(zhuǎn)向計(jì)算距離隨機(jī)選擇的頂點(diǎn)m個(gè)步長(zhǎng)的鄰居的數(shù)目。如第二章A所示，第一和第二最近鄰的I率分布由函數(shù)G0( x)和G0(G1(x)。通過擴(kuò)展，第m個(gè)鄰居的分布由Go(GGi(x)生成,其中函數(shù)G1的m-1次迭代作用于其自身。如果我們將 G(m)(x)定義為第m個(gè)鄰居的這個(gè)生成函數(shù)，那么我們有for m= 1,(49)然后，第m階最近鄰居的平均數(shù) zm是(50)隨著初始條件

32、乙=z =G0(1),這就告訴我們(51)從該結(jié)果，我們可以對(duì)圖上兩個(gè)隨機(jī)選擇的頂點(diǎn)之間的最短路徑的典型長(zhǎng)度進(jìn)行估計(jì)。當(dāng)?shù)竭_(dá)該距離的頂點(diǎn)的鄰居的總數(shù)等于圖上的頂點(diǎn)的數(shù)目時(shí)，即，當(dāng)152)使用公式(51),這給了我們1)一可)+ 工；一 Inz；ln(z2/Z)(53)在N AA4和Z2 AA4的常見情況下，這減少到InGVAzi)ln(z3 /z i)+ 1.(54)這個(gè)結(jié)果只是近似的，有兩個(gè)原因。首先，用于推導(dǎo)它的條件僅是近似;確切的答案取決于圖的詳細(xì)結(jié)構(gòu)。第二，它假設(shè)所有頂點(diǎn)都可以從隨機(jī)選擇的起始頂點(diǎn)到達(dá)。一般來說，這不會(huì)是真的。對(duì)于沒有巨分量的圖形，肯定不是真的, 方程(54)是無意義的

33、。但是，即使有一個(gè)巨分量，通常不是這種情況：它填充整個(gè)圖。因此，通過將等式(54)中的N替換為NS,可以給出£的更好近似，其中 S是巨分量占據(jù)的圖的分?jǐn)?shù)，如在第二章盡管存在這樣的缺點(diǎn)，但是存在方程(54)的許多顯著特征。(1)其表明對(duì)于所有隨機(jī)圖的平均頂點(diǎn)-頂點(diǎn)距離，無論度分布如何，應(yīng)當(dāng)根據(jù)D中。=A + BlnN對(duì)數(shù)地與大小 N成比例，其中A和B是常數(shù)。這個(gè)結(jié)果當(dāng)然是眾所周知的許多特殊情況。(2)其展示出作為全局屬性的平均距離可以僅根據(jù)第一和第二最近鄰的平均數(shù)的知識(shí)來計(jì)算，這是本地屬性。因 此，可以通過在諸如熟人網(wǎng)絡(luò)之類的圖形上的純本地測(cè)量并且根據(jù)它們來經(jīng)驗(yàn)地測(cè)量這些數(shù)字，以確定頂

34、點(diǎn)之間的預(yù)期平均距離。至少對(duì)于一些網(wǎng)絡(luò)，這給出了令人驚訝的真實(shí)平均距離的良好估計(jì)（3）其展示出僅第一和第二最近鄰的平均數(shù)對(duì)于平均距離的計(jì)算是重要的,3小并且因此具有完全不同的頂點(diǎn)度分布但是具有相同的Zi和Z2的值的兩個(gè)隨機(jī)圖將具有相同的平均距離。對(duì)于之前討論的純理論示例圖的情況，我們不能對(duì)Z1和Z2進(jìn)行經(jīng)驗(yàn)測(cè)量，但是我們?nèi)匀豢梢允褂霉剑?4）來計(jì)算。在普通（泊松）隨機(jī)圖的情況下，例如我們從等式（12）中發(fā)現(xiàn)4 = z, Z2=Z2,并且1= In N / In z,這是這種類型的圖的標(biāo)準(zhǔn)結(jié)果1。對(duì)于具有根據(jù)截?cái)喔缍啥确植嫉膱D,等式（17）乙和Z2由等式（21）和（22）給出，并且平均頂點(diǎn)-

35、頂點(diǎn)距離5"+皿1（2-1與/口7 1（27力1mLi_式已心）/口一（小勺T(55)In Af+ ln1）/=ln（7-2）/（r-l）-l + L 注意，對(duì)于任何t3,該表達(dá)式不具有有限正實(shí)數(shù)值，指示必須為度分布指定有限截止 義的平均頂點(diǎn)-頂點(diǎn)距離。(56)氐以在這樣的圖上獲得良好定G仿真結(jié)果。作為對(duì)本節(jié)結(jié)果的檢查，我們對(duì)具有各種頂點(diǎn)度分布的隨機(jī)圖進(jìn)行了廣泛的計(jì)算機(jī)模擬。這樣的圖形是相對(duì)直接生成的。首先，我們生成一組N個(gè)隨機(jī)數(shù)ki以表示圖中N個(gè)頂點(diǎn)的度數(shù)。這些可以被認(rèn)為是從它們各自的頂點(diǎn)出現(xiàn)的邊的“ stubs”。然后我們隨機(jī)選擇這些存根的對(duì)，并將圖上的邊連接起來。很容易看出，這

36、將生成具有給定的頂點(diǎn)度集合的所有圖形，具有相等的概率。唯一小的陷阱是度數(shù)的和 Z ki必須是偶數(shù)，因?yàn)樘砑拥綀D中的每個(gè)i邊必須具有兩端。這不又t設(shè)計(jì)。如果集合ki使得和為奇數(shù)，我們只需將其丟棄并生成一個(gè)新集合。實(shí)際上，如果適用可以使用變換方法來生成表示具有任何期望的概率分布的頂點(diǎn)度的整數(shù)，或者可以不使用舍棄或混合方法45。例如，可以使用如下的兩步混合變換/舍棄方法來生成服從等式（17）的哥律加截止形式的度。首先,我們生成隨機(jī)整數(shù) k至1的分布與e*K成比例的，使用變換46A =1一 K 1口（ 1 一尸兒(57)其中r是均勻分布在0士1范圍內(nèi)的隨機(jī)實(shí)數(shù)。第二，我們用概率k接受這個(gè)數(shù)字，其中“接

37、受”是指如果數(shù)字不被接受，我們丟棄它并根據(jù)等式（57）產(chǎn)生另一個(gè)，重復(fù)該過程直到一個(gè)被接受。在圖4中，我們顯示了對(duì)于 七和父的各種不同值, 分量的大小的結(jié)果。在同一圖上，我們還顯示了由方程（對(duì)于根據(jù)式（17）分布的頂點(diǎn)度的無向單分布圖的模擬中的巨 34）和（35）的數(shù)值解導(dǎo)出的相同量的期望值。如圖所示，（圖4:具有根據(jù)等式（17）分布的頂點(diǎn)度的隨機(jī)圖中的巨分量 的大小作為針對(duì)指數(shù) T的五個(gè)不同值的截止參數(shù)設(shè)的函數(shù)。點(diǎn) 是來自N = 1000000個(gè)頂點(diǎn)的圖的數(shù)值模擬的結(jié)果，實(shí)線是無 限圖的理論值，方程（34）和（35）。模擬結(jié)果上的誤差條小 于數(shù)據(jù)點(diǎn)。）3、有向圖。我們現(xiàn)在轉(zhuǎn)向具有任意度分布的有向圖。有向圖的示例是萬維網(wǎng)，因?yàn)樵趙eb上的兩個(gè)頁面之間的每個(gè)超鏈接僅在一個(gè)方向上。網(wǎng)絡(luò)具有遵循哥律的度分布，如第一章所述。在有向圖中，不可能B的邊（有向），這不一定意有向圖引入了一個(gè)微妙的，不存在于無向的，當(dāng)我們應(yīng)用我們的生成函數(shù)形式時(shí)變得重要。 談?wù)摗胺至俊?即一組連接的頂點(diǎn) -因?yàn)榧词鬼旤c(diǎn) A