2013-07-17……2013-07-31課題學(xué)習(xí)進(jìn)度。

第四章度相關(guān)性與社團(tuán)結(jié)構(gòu)

這一章主要我主要學(xué)習(xí)了描述網(wǎng)絡(luò)的度相關(guān)性的幾種不同的方法，包括聯(lián)合概率分布，余平均度和同

配系數(shù)。另外簡(jiǎn)單了解了大規(guī)模網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)分析的幾個(gè)有代表性的算法。下面，我將本章內(nèi)的一些重點(diǎn)概

念做了整理。

先回憶度分布和平均度這兩個(gè)概念。PA表示網(wǎng)絡(luò)中度為k的節(jié)點(diǎn)占整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的比列，稱(chēng)為度分布;

<k)是平均度，表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度的平均值。

1、網(wǎng)絡(luò)具有度相關(guān)性：指網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間是否有邊相連與這兩個(gè)節(jié)點(diǎn)的度值有關(guān)。否則，就稱(chēng)網(wǎng)

絡(luò)不具有度相關(guān)性，或稱(chēng)網(wǎng)絡(luò)是中性的。

2、復(fù)雜網(wǎng)絡(luò)的社團(tuán)結(jié)構(gòu):實(shí)際網(wǎng)絡(luò)往往可以看作是由若干個(gè)社團(tuán)構(gòu)成的，每個(gè)社團(tuán)內(nèi)部的節(jié)點(diǎn)之間的連

接相對(duì)較為緊密，彳日是各個(gè)社團(tuán)之間的連接相對(duì)比較稀疏。

3、聯(lián)合概率分布：網(wǎng)絡(luò)中隨機(jī)選取的一條邊的兩個(gè)端點(diǎn)的度分別為j和k的概率，即為網(wǎng)絡(luò)中度為j的

節(jié)點(diǎn)和度為k的節(jié)點(diǎn)之間存在的邊數(shù)占網(wǎng)絡(luò)總邊數(shù)的比例：

P(j,k)=m(j,k)u(j,k)/2M,

其中，m(j,k)是度為j的節(jié)點(diǎn)和度為k的節(jié)點(diǎn)之間的連邊數(shù)；如果j=k,那么u(j,k)=2,否則u(j,k)=i.

聯(lián)合概率分布具有如下性質(zhì)：

①對(duì)稱(chēng)性,即p(j,k)=p(kj),

②歸一化，即Jjckmin,

③余度分布，即七,其中％”和牖皿分別為網(wǎng)絡(luò)中節(jié)點(diǎn)的度的最小值和最大值。

P”(k)表示網(wǎng)絡(luò)中隨機(jī)選取的一個(gè)節(jié)點(diǎn)和隨機(jī)選取的一個(gè)鄰居節(jié)點(diǎn)的度為k的概率。

4、條件概率：網(wǎng)絡(luò)中隨機(jī)選取的一個(gè)度為k的節(jié)點(diǎn)的一個(gè)鄰居的度為j的概率。它與聯(lián)合概率P(j,k)

具有如下關(guān)系：

Pc(j|k)p(k)=P(j,k)

5、判斷度相關(guān)性：一、用條件概率，如果條件概率Pqj|k)與k相關(guān)，那么就說(shuō)明節(jié)點(diǎn)度之間具有相關(guān)性,

并且網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可能具有層析結(jié)構(gòu)。如果條件概率&（j|k）與k無(wú)關(guān)，那么就說(shuō)明網(wǎng)絡(luò)沒(méi)有度相關(guān)性。二、

計(jì)算度為k的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的平均度,也稱(chēng)度為k的節(jié)點(diǎn)的余平均度，記為（kX假設(shè)節(jié)點(diǎn)i的陽(yáng)個(gè)

鄰居節(jié)點(diǎn)的度為%=1,2，…此可以計(jì)算節(jié)點(diǎn)i的余平均度，即節(jié)點(diǎn)i的木個(gè)鄰居節(jié)點(diǎn)的平均度⑷而如下：

<knn>i=￡:代

（k->（k）與條件概率和聯(lián)合概率之間具有如下關(guān)系：

〈k嶗（k）=￡匕JPcMk）=￡九內(nèi)〃

其中，（如果網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間是否有邊相連與這兩個(gè)節(jié)點(diǎn)的度值無(wú)關(guān)，也就是說(shuō)，網(wǎng)絡(luò)中隨機(jī)

選擇的一條邊的兩個(gè)端點(diǎn)的度是完全隨機(jī)的，存在此關(guān)系），如果代加〉（k）是k的增函數(shù)，那么就意味著

平均而言,獨(dú)大的節(jié)點(diǎn)傾向于與度大的節(jié)點(diǎn)連接，從而表明網(wǎng)絡(luò)是同配的；反之,如果《加〉（（<）是k的減

函數(shù)，那么就意味著平均而言，度大的節(jié)點(diǎn)傾向于與度小的節(jié)點(diǎn)連接，從而表明網(wǎng)絡(luò)是異配的；如果網(wǎng)絡(luò)不

具有度相關(guān)性,那么｛刖〉（k）是一個(gè)與k無(wú)關(guān)的常數(shù)。

6、網(wǎng)絡(luò)是同配的：指對(duì)于度相關(guān)的網(wǎng)絡(luò)，如果總體上度大的節(jié)點(diǎn)傾向于連接度大的荒點(diǎn),那么就稱(chēng)網(wǎng)

絡(luò)是度相關(guān)的，或稱(chēng)說(shuō)網(wǎng)絡(luò)是同配的。相反，如果總體上度大的節(jié)點(diǎn)傾向于連接度小的節(jié)點(diǎn)，那么就稱(chēng)網(wǎng)絡(luò)

是度負(fù)相關(guān)的，或者稱(chēng)網(wǎng)絡(luò)是異配的。

7、同配系數(shù)：用于刻畫(huà)網(wǎng)絡(luò)是同配還是異配的指標(biāo)。網(wǎng)絡(luò)是度相關(guān)的就意味著以株口為僅

之間不恒等，因此，可以通過(guò)兩者之間的差的大小刻畫(huà)網(wǎng)絡(luò)的同配或者異配程度：

<jk>>（j><k）=4理（濟(jì)-9必）

當(dāng)網(wǎng)絡(luò)為完全同配時(shí)，SA=力他,上面式子達(dá)到最大值，即為余度分布》的方差：

于是得到歸一化的相關(guān)系數(shù)，也稱(chēng)為同配系數(shù)如下：

1

顯然，re[-1,1]z如果r>0,那么網(wǎng)絡(luò)是同配的，如果r<0,那么網(wǎng)絡(luò)是異配的。卜|的大小反映了網(wǎng)絡(luò)同配

或者異配的強(qiáng)弱程度。（已有研究表明，網(wǎng)絡(luò)的同配或者異配對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和行，如魯棒性和傳播等可能有顯

著的影響。)從更為一般的角度看，同配就是指屬相相近的節(jié)點(diǎn)傾向于互相連接。

8、模塊度：是近年常用的一種衡量社團(tuán)劃分質(zhì)量的標(biāo)準(zhǔn)，其基本想法是把劃分社團(tuán)后的網(wǎng)絡(luò)與相應(yīng)的

零模型進(jìn)行比較，以度量社團(tuán)劃分質(zhì)量。

9、一個(gè)與網(wǎng)絡(luò)對(duì)應(yīng)的零模型：指與該網(wǎng)絡(luò)具有相同的性質(zhì)(如相同的邊數(shù)或者相同的度分布等)而在

其他方面完全隨機(jī)的隨機(jī)圖模型。

10、基于模塊度的社團(tuán)檢測(cè)算法：CNM算法，是一種基于貪婪算法思想的社團(tuán)結(jié)構(gòu)檢測(cè)算法。

第五章節(jié)點(diǎn)重要性與相似性

這一章重點(diǎn)介紹了無(wú)向網(wǎng)絡(luò)中判斷節(jié)點(diǎn)重要性的幾個(gè)常見(jiàn)的指標(biāo)，包括度值、介數(shù)、k-殼等；另外，這

一章還學(xué)習(xí)了HITS算法和PageRank算法的基本思想，這兩個(gè)算法最初是針對(duì)WWW中的網(wǎng)頁(yè)排序而提

出的、可用于有向網(wǎng)絡(luò)中節(jié)點(diǎn)重要性排序。最后，大概了解了了關(guān)于節(jié)點(diǎn)之間的相似性描述及其在鏈路預(yù)測(cè)

的概念。下面一一整理本章的重要知識(shí)點(diǎn)。

1、度中心性：一個(gè)節(jié)點(diǎn)的度越大就意味著這個(gè)節(jié)點(diǎn)越重要,一個(gè)包含N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，節(jié)點(diǎn)最大可

能的度值為N-1,為了便于匕瞰，對(duì)中心性指標(biāo)作歸一化處理，度為總的節(jié)點(diǎn)的歸一化的度中心值定義為：

田

2、介數(shù)中心性：是一個(gè)用于通過(guò)測(cè)量經(jīng)過(guò)某個(gè)節(jié)點(diǎn)的最短路徑的數(shù)目來(lái)刻畫(huà)節(jié)點(diǎn)重要性的指標(biāo)，簡(jiǎn)稱(chēng)

ry三

介數(shù)(BCI具體的，節(jié)點(diǎn)i的介數(shù)定義為：B。三乙內(nèi)工況，其中，仇為從節(jié)點(diǎn)5到節(jié)點(diǎn)t的最短路徑的數(shù)

目，山，為從節(jié)點(diǎn)s到節(jié)點(diǎn)t的外，條最短路徑中經(jīng)過(guò)節(jié)點(diǎn)i的最短路經(jīng)的數(shù)目。

一個(gè)包含N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，節(jié)點(diǎn)最大可能的度值為N-1,節(jié)點(diǎn)介數(shù)的最大可能值是星型網(wǎng)絡(luò)中的中

心節(jié)點(diǎn)的介數(shù)值：因?yàn)樗兴衅渌?jié)點(diǎn)對(duì)之間的最短路徑是唯一的并且都會(huì)經(jīng)過(guò)該中心節(jié)點(diǎn)，所以該節(jié)點(diǎn)

的介數(shù)就是這些最短路徑的數(shù)目，即為

(N-1)(N-2)N2-3N+2

~2=^

基于上式，一個(gè)包含N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中的節(jié)點(diǎn)i的歸一化結(jié)束定義為

2yNt

BC=-2-3/V+2乙S工i工t亞

陽(yáng)二廿六通戶j

其中c為一比例常數(shù)，A=(㈣仍然是網(wǎng)絡(luò)的鄰接矩陣。記x=四"2.…%N]T,則上面的式子可寫(xiě)成如

下矩陣形式：

X=cAx,

上式意味著X是矩陣A與特征值C7對(duì)應(yīng)的特征向量，故此稱(chēng)為特征向量中心性。

6、HITS算法：基本思想：每個(gè)網(wǎng)頁(yè)的重要性有兩種刻畫(huà)指標(biāo)——權(quán)威性和樞紐性。T殳的，一個(gè)頁(yè)

面的權(quán)威性有指向該頁(yè)面的其他頁(yè)面的樞紐值來(lái)刻畫(huà)：如果一個(gè)頁(yè)面被多個(gè)具有高樞紐值的頁(yè)面所指向，

那么該頁(yè)面就具有高得權(quán)威性。另一方面，一個(gè)頁(yè)面的樞紐值由它所指向的頁(yè)面的權(quán)威值來(lái)刻畫(huà)：如果一

個(gè)頁(yè)面指向多個(gè)具有高權(quán)威值得頁(yè)面，那么該頁(yè)面就具有高得樞紐值。

7、PageRank算法：基本思想：WWW是一個(gè)頁(yè)面的重要性取決于指向它的其他頁(yè)面的數(shù)量和質(zhì)量。

8、節(jié)點(diǎn)相似性與鏈路預(yù)測(cè)：刻畫(huà)節(jié)點(diǎn)的相似性有很多種方法，最簡(jiǎn)單的直接的就是利用節(jié)點(diǎn)的屬性。

節(jié)點(diǎn)相似性分析的一個(gè)典型的應(yīng)月就是鏈路預(yù)測(cè)，它是指如何通過(guò)已知的各種信息預(yù)測(cè)給定的網(wǎng)絡(luò)中尚

不存在連邊的兩個(gè)節(jié)點(diǎn)之間產(chǎn)生連接的可能性。這種預(yù)測(cè)包含了對(duì)未知鏈接，也稱(chēng)丟失鏈接的預(yù)測(cè)，也包

含了對(duì)未來(lái)鏈接的預(yù)測(cè)。

基于節(jié)點(diǎn)相似性進(jìn)行鏈路預(yù)測(cè)的一個(gè)基本假設(shè)就是如果兩個(gè)節(jié)點(diǎn)之箭的相似性越大，他們之間存在鏈

接的可能性就越大。

第六章隨機(jī)網(wǎng)絡(luò)模型

本章在簡(jiǎn)要介紹了完全規(guī)則的網(wǎng)絡(luò)模型之后，重點(diǎn)介紹了幾類(lèi)典型的隨機(jī)網(wǎng)絡(luò)模型，首先介紹的是

具有任意給定平均度的ER隨機(jī)圖模型及其基本拓?fù)湫再|(zhì)，接著介紹了具有任意給定度分布的廣義隨機(jī)圖

配置模型。ER隨機(jī)圖和配置模型分別可以視為0階和1階零模型，他們起著參照系的作用：我們可

以通過(guò)與適當(dāng)?shù)牧隳Ｐ妥鞅容^來(lái)分析實(shí)際網(wǎng)絡(luò)的拓?fù)湫再|(zhì)及其演化特征。總的來(lái)說(shuō)，這一張講述了基于隨

機(jī)重連而生成的與任一給定的網(wǎng)絡(luò)具有任一給定階次度相關(guān)特性的零模型。

一、規(guī)則網(wǎng)絡(luò)

1、全局耦合網(wǎng)絡(luò)：網(wǎng)絡(luò)中的任意兩個(gè)節(jié)點(diǎn)之間都有邊直接相連。如：班級(jí)的所有同學(xué)便構(gòu)成一個(gè)

全耦合網(wǎng)絡(luò)。全耦合網(wǎng)絡(luò)作為實(shí)際網(wǎng)絡(luò)模型的局限性：大型實(shí)際網(wǎng)絡(luò)都是稀疏的，它們的邊的數(shù)目一

般至多是0(N)而不是O(N?l

在具有相同節(jié)點(diǎn)數(shù)的所有網(wǎng)絡(luò)中，全耦合網(wǎng)絡(luò)具有最多的邊數(shù)、最大的聚類(lèi)系數(shù)Cgc=l和最小

的平均路徑長(zhǎng)度Lg，=l.

2、最近鄰耦合網(wǎng)絡(luò)：網(wǎng)絡(luò)中，每一個(gè)節(jié)點(diǎn)只和它周?chē)泥従庸?jié)點(diǎn)相連。如：體育游戲或者跳舞等集

體運(yùn)動(dòng)是，所有人手牽手排成一個(gè)長(zhǎng)隊(duì)或者圍成一圈。這類(lèi)網(wǎng)絡(luò)的一個(gè)重要特征就是網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)是由

節(jié)點(diǎn)之間的相對(duì)位置決定的，隨著節(jié)點(diǎn)位置的變化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)也可發(fā)生切換。

3?(網(wǎng)絡(luò)中三角形的數(shù)目)

最近鄰耦合網(wǎng)絡(luò)的聚類(lèi)系數(shù):二網(wǎng)絡(luò)中聯(lián)通三元組的數(shù)目

3?NY%

=N*4

3.(K-2)

最近鄰耦合網(wǎng)絡(luò)的平均路徑長(zhǎng)度1'"曲黃〃m/K]"N/2K。

3、星型耦合網(wǎng)絡(luò)：它有一個(gè)中心節(jié)點(diǎn)，其余的N-1個(gè)點(diǎn)斗志與這個(gè)中心點(diǎn)連接，而它們彼此之

間不連接。如：公共服務(wù)器連接個(gè)人電腦。

星型耦合網(wǎng)絡(luò)的聚類(lèi)系數(shù):,這是因?yàn)橹行墓?jié)點(diǎn)的N-1鄰居節(jié)點(diǎn)之間互不相連，從而中心節(jié)點(diǎn)

的聚類(lèi)系數(shù)為0.

2(N-1)

星型耦合網(wǎng)絡(luò)的平均路徑長(zhǎng)度％。二2一兩》2(N-8X

二、隨機(jī)圖

1、ER隨機(jī)圖具有兩種形式的定義。

定義1:具有固定邊數(shù)的ER隨機(jī)圖G(N,M):假設(shè)有大量的紐扣(N>>1)散落在地上，每次在隨

機(jī)選取的一對(duì)紐扣之間系上一根繩。重復(fù)M次后就得到一個(gè)包含N個(gè)點(diǎn)，M條邊的ER隨機(jī)圖。通常

我們希望構(gòu)造的是沒(méi)有重邊和自環(huán)的簡(jiǎn)單圖，因此，每次在選擇節(jié)點(diǎn)對(duì)時(shí)應(yīng)該選擇兩個(gè)不同的并且是沒(méi)

有變連接的節(jié)點(diǎn)對(duì)。這樣形成的隨機(jī)圖記為G(N,M1

ER隨機(jī)圖G(N,M)的構(gòu)造算法：

(1)初始化：給定N個(gè)節(jié)點(diǎn)和戴天價(jià)的邊數(shù)M.

(2)隨機(jī)連邊：

①隨機(jī)選取一對(duì)沒(méi)有邊相連的不同節(jié)點(diǎn)，并在這對(duì)節(jié)點(diǎn)之間添加一條邊。

②重復(fù)步驟①，直到在M對(duì)不同的節(jié)點(diǎn)對(duì)之間各添加了一條邊。

定義2:具有固定連邊概率的ER隨機(jī)圖G(N,p)在模型G(N,p)中不固定總的邊數(shù)，而是把N個(gè)

節(jié)點(diǎn)中任意兩個(gè)不同的節(jié)點(diǎn)之間有一條邊的概率固定為po

ER隨機(jī)圖G(N,p)的構(gòu)造箕法：

(1)初始化：給定N個(gè)節(jié)點(diǎn)以及連邊概率pe[0,l]o

(2)隨機(jī)連邊：

①選擇一對(duì)沒(méi)有邊相連的不同的節(jié)點(diǎn)。

②生成一個(gè)隨機(jī)數(shù)re(0,1X

③如果r<p,那么就在這對(duì)點(diǎn)之間添加一條邊；否則就不添加邊。

④重復(fù)步驟①?③，直至所有的節(jié)點(diǎn)對(duì)都被選擇過(guò)一次。

三、廣義隨機(jī)圖

配置模型：在配置模型中事先給定的是網(wǎng)絡(luò)的度序列｛由，丸其中非負(fù)整數(shù)d為節(jié)點(diǎn)i

的度。關(guān)于度序列，給兩個(gè)必要條件：

(1)由于網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度值之和等于網(wǎng)絡(luò)中所有邊數(shù)之和的兩倍,'工必必須為偶數(shù)并且有

(2)<N-1,i=LZ...,N,等號(hào)只有當(dāng)一個(gè)節(jié)點(diǎn)與其他所有節(jié)點(diǎn)都相連時(shí)才成立。

在上述條件的基礎(chǔ)上少許加以推廣，就可得到如下的充要條件：

定理：一個(gè)非負(fù)整數(shù)序列｛由，電，“av)是某個(gè)簡(jiǎn)單圖的度序列的充要條件為：

(1)-I為偶數(shù)；

(2)對(duì)于每個(gè)整數(shù)九均有匯七科之口匕0+匯鼠+嚴(yán)而應(yīng)為

配置模型構(gòu)造算法：

(1)初始化：根據(jù)給定度序列確定N個(gè)節(jié)點(diǎn)的度值。

ywN

(2)引出線頭：從度為先的節(jié)點(diǎn)i引出用個(gè)線頭。共有4=ik=2M個(gè)線頭，M為網(wǎng)絡(luò)的邊數(shù)。

(3)隨機(jī)配對(duì)：完全隨機(jī)地選取一對(duì)線頭，把它們連在一起，形成一條邊；再在剩余的線頭中完

全隨機(jī)地選取另一對(duì)線頭連成一條邊；以此進(jìn)行下去，直至用完所有的線頭。

四、隨機(jī)重連與零模型

1、零模型：一般地，我們把一個(gè)實(shí)際網(wǎng)絡(luò)既有相同的節(jié)點(diǎn)數(shù)和相同的某些性質(zhì)A的隨機(jī)網(wǎng)絡(luò)稱(chēng)

為該實(shí)際網(wǎng)絡(luò)的隨機(jī)化網(wǎng)絡(luò)。這里的〃某些性質(zhì)A"可以是平局度、度分布、聚類(lèi)系數(shù)等等，或者是

它們的某種組合。從統(tǒng)計(jì)學(xué)的角度看，〃具有性質(zhì)A的網(wǎng)絡(luò)G也具有某一性質(zhì)P"是一個(gè)零假設(shè)，而

為了要驗(yàn)證這一零假設(shè)是否成立，就需要與原網(wǎng)絡(luò)G具有相同規(guī)模和相同性質(zhì)A的隨機(jī)化網(wǎng)絡(luò)作為

參照系，以判斷性質(zhì)P是否為這類(lèi)隨機(jī)化網(wǎng)絡(luò)的典型特征。這類(lèi)隨機(jī)化網(wǎng)絡(luò)模型在統(tǒng)計(jì)學(xué)上稱(chēng)為零模

型。

ER隨機(jī)圖可以視為介數(shù)晶氐的零模型。有時(shí)我們需要具有更多約束條件的零模型。按照約束條

件的從少到多，可以定義如下不同階次的零模型：

(1)0階零模型：即與原網(wǎng)絡(luò)具有相同節(jié)點(diǎn)數(shù)N和邊數(shù)M的隨機(jī)化網(wǎng)絡(luò)。

(2)1階零模型：即與原網(wǎng)絡(luò)具有相同節(jié)點(diǎn)數(shù)N和度分布P(k)的隨機(jī)化網(wǎng)絡(luò)。通常的做法是每

個(gè)節(jié)點(diǎn)的度值保持不變(即度序列保持不變X

(3)2階零模型：即于原網(wǎng)絡(luò)具有相同節(jié)點(diǎn)數(shù)N和二階度相關(guān)特性P(k,k')的隨機(jī)化網(wǎng)絡(luò)。有

時(shí)也考慮與原網(wǎng)絡(luò)具有相同同配系數(shù)的隨機(jī)化網(wǎng)絡(luò)。

(4)3即于原網(wǎng)絡(luò)具有相同節(jié)點(diǎn)數(shù)N和三階度相關(guān)特性P(kl,k2,k3)的隨機(jī)化網(wǎng)絡(luò)。

2、隨機(jī)重連算法，給出了一個(gè)"當(dāng)已經(jīng)有了某個(gè)實(shí)際網(wǎng)絡(luò)的拓?fù)鋽?shù)據(jù)，其中包含節(jié)點(diǎn)之間是如

何連接的完全信息，要生成一個(gè)與這個(gè)網(wǎng)絡(luò)具有相同度序列的隨機(jī)網(wǎng)絡(luò)模型〃的方法。

基本思想：在原始網(wǎng)絡(luò)數(shù)據(jù)的基礎(chǔ)上，保持每個(gè)節(jié)點(diǎn)的度不變，但是使得連邊的位置盡可能的

隨機(jī)化，以得到一個(gè)具有給定序列的隨機(jī)網(wǎng)絡(luò)。

2013-08-012013-08-15課題學(xué)習(xí)進(jìn)度。

第七章小世界網(wǎng)絡(luò)模型

本章圍繞與小世界網(wǎng)絡(luò)模型有關(guān)的兩個(gè)問(wèn)題而展開(kāi)。第一個(gè)問(wèn)題是如何構(gòu)建既具有聚類(lèi)特性又具有

小世界性質(zhì)的網(wǎng)絡(luò)模型。本章將介紹由Watts和Strogatz提出的通過(guò)在規(guī)則網(wǎng)絡(luò)上連邊進(jìn)行少許隨機(jī)

重連而得到的WS小世界網(wǎng)絡(luò)模型，以及隨后由Newman和Watts提出的在規(guī)則網(wǎng)絡(luò)上隨機(jī)添加少許

連邊而得到的NW小世界網(wǎng)絡(luò)模型。同時(shí)也介紹了如何分析這兩個(gè)模型的聚類(lèi)系數(shù)、平均距離和度分布

性質(zhì)。第二個(gè)問(wèn)題是什么樣的小世界網(wǎng)絡(luò)才能實(shí)現(xiàn)有效搜索。即使你知道你與世界上隨機(jī)選取的一個(gè)人

之間的距離也許并不大，但這并不意味著你就一定能輕易地找到連接你們兩個(gè)人的最短路徑。網(wǎng)絡(luò)的可

搜索性失語(yǔ)網(wǎng)絡(luò)結(jié)構(gòu)關(guān)聯(lián)在一起的。Kleinberg關(guān)于小世界網(wǎng)絡(luò)可搜索性的研究是網(wǎng)絡(luò)科學(xué)的另一個(gè)重

要突破，本章介紹了Kleinberg模型的仿真與理論分析及相關(guān)試驗(yàn)驗(yàn)證，并對(duì)其他模型做了簡(jiǎn)要介紹。

一、小世界網(wǎng)絡(luò)模型

1、WS小世界模型：作為從完全規(guī)則網(wǎng)絡(luò)向完全隨機(jī)網(wǎng)絡(luò)的過(guò)渡，只要在規(guī)則的網(wǎng)絡(luò)中引入少許

的隨機(jī)性就可以產(chǎn)生具有小世界特征的網(wǎng)絡(luò)模型，現(xiàn)在常稱(chēng)為WS小世界模型。

WS小世界模型構(gòu)造算法：

（1）從規(guī)則圖開(kāi)始：給定一個(gè)含有N個(gè)點(diǎn)的環(huán)狀最近鄰耦合網(wǎng)絡(luò)，其中每個(gè)節(jié)點(diǎn)都與它左右相

鄰的各K/2個(gè)節(jié)點(diǎn)相連，K是偶數(shù)。

（2）隨機(jī)化重連：以概率p隨機(jī)地重新連接網(wǎng)絡(luò)中原有的每條邊，即把每條邊的一個(gè)端點(diǎn)保持

不動(dòng)，另一個(gè)端點(diǎn)改取為網(wǎng)絡(luò)中隨機(jī)選擇的一個(gè)結(jié)點(diǎn)。其中規(guī)定不得有重邊和自環(huán)。

網(wǎng)絡(luò)科學(xué)研究的一般范式

（1）建立模型：通過(guò)對(duì)規(guī)則網(wǎng)絡(luò)的隨機(jī)重連提出了WS小世界網(wǎng)絡(luò)模型。

（2）仿真分析通過(guò)仿真揭示了當(dāng)重連概率較小時(shí)可以得到既具有較短的平均路徑長(zhǎng)度又具有較

高的聚類(lèi)系數(shù)的小世界網(wǎng)絡(luò)。

（3）實(shí)際驗(yàn)證：驗(yàn)證了3個(gè)實(shí)際網(wǎng)絡(luò)的平均路徑長(zhǎng)度和聚類(lèi)系數(shù)。

（4）影響分析：通過(guò)仿真說(shuō)明小世界特征對(duì)于網(wǎng)絡(luò)動(dòng)力學(xué)的影響。

2、NW小世界模型：NW模型是通過(guò)用“隨機(jī)化加邊"取代WS模型的構(gòu)造中的"隨機(jī)化重連”

而得到的。在NW模型中，原采的NK/2條邊保持不變，力是在此基礎(chǔ)上再隨機(jī)添加一些邊,為了便于

比較，這些添加的長(zhǎng)程邊數(shù)目的均值同樣取為NKp/2。

NW小世界模型構(gòu)造算法：

（1）從規(guī)則圖開(kāi)始：給定一個(gè)含有N個(gè)點(diǎn)的環(huán)狀最近鄰耦合網(wǎng)絡(luò)，其中每個(gè)節(jié)點(diǎn)都與它左右相鄰

的各K/2個(gè)節(jié)點(diǎn)相連，K是偶數(shù)。

（2）隨機(jī)化加邊：以概率p在隨機(jī)選取的NK/2對(duì)節(jié)點(diǎn)之間添加邊，其中規(guī)定不得有重邊和自

環(huán)

二、拓?fù)湫再|(zhì)分析

1、聚類(lèi)系數(shù)

2、度分布

3、平均路徑長(zhǎng)度

三、Kleinberg模型與可搜索性

Kleinberg對(duì)二維NW小世界模型做了如下修改：

（1）假設(shè)每條邊都是有向邊。這對(duì)底層的規(guī)則網(wǎng)格沒(méi)有影響，因?yàn)橐?guī)則網(wǎng)格上的兩個(gè)節(jié)點(diǎn)要么互

為鄰居,要么互相都不是鄰居。

（2）假設(shè)長(zhǎng)程連接并不是完全隨機(jī)地添加到原先的規(guī)則網(wǎng)格中。從每個(gè)節(jié)點(diǎn)都有q條郵箱的長(zhǎng)

程連接指向網(wǎng)絡(luò)中的其他q個(gè)節(jié)點(diǎn)。節(jié)點(diǎn)u有邊指向節(jié)點(diǎn)v的概率口色與這兩個(gè)節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離的

幕函數(shù)出〃同「“成正比,這里二0是一個(gè)參數(shù)。

二維網(wǎng)格上的Kleinberg模型構(gòu)造算法：

（1）從規(guī)則網(wǎng)格開(kāi)始：給定一個(gè)含有N='個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們分布在一個(gè)二維網(wǎng)格

上，使得每一行和每一列都恰好有77個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都通過(guò)有向邊指向所有與該節(jié)點(diǎn)的網(wǎng)格距離不超

過(guò)p>=l的節(jié)點(diǎn)。

（2）隨機(jī)化加邊：對(duì)于每個(gè)節(jié)點(diǎn)，添加從該節(jié)點(diǎn)指向網(wǎng)絡(luò)中其他q各節(jié)點(diǎn)的q條有向邊，其中

節(jié)點(diǎn)u有添加邊指向節(jié)點(diǎn)v的概率為

[d(u.v)]--

nuv

考慮二維Kleinberg網(wǎng)絡(luò)模型上的搜索問(wèn)題，假設(shè)每個(gè)節(jié)點(diǎn)采用的都是基于局部信息

的分散式算法。我們有：

（1）對(duì)于0〈二°〈2,存在一個(gè)與p,q,0相關(guān)但與N無(wú)關(guān)的常數(shù)以,平均傳遞步數(shù)都有一個(gè)下界

（2）當(dāng)°二2時(shí)，當(dāng)前新的持有節(jié)點(diǎn)只需把信件傳遞給一個(gè)在網(wǎng)格距離上最接近目標(biāo)節(jié)點(diǎn)的鄰居

節(jié)點(diǎn)，這種分散式算法的平均傳遞步數(shù)有一個(gè)上界C2（'ogN）j其中的是一個(gè)與N無(wú)關(guān)的常數(shù)。

（3）對(duì)于2,存在一個(gè)與p,q,°相關(guān)但與N無(wú)關(guān)的常數(shù)C。,使得對(duì)于任意的分散式算法，平均傳

遞步數(shù)都有一個(gè)下界CaN（2-a）/6-D。

說(shuō)明：當(dāng)心2時(shí)，分散式算法所需的平均傳遞步數(shù)至多是logN的多項(xiàng)式函數(shù)；而當(dāng)a!=2時(shí)，分

散式算法所需的傳遞步數(shù)T至少是N的多項(xiàng)式函數(shù)，即

其中，c是與N無(wú)關(guān)的常數(shù)，并且

(2-。)/3,0??<2,

第八章無(wú)標(biāo)度網(wǎng)絡(luò)模型

這一章中講的BA無(wú)標(biāo)度網(wǎng)絡(luò)模型的介紹也體現(xiàn)了復(fù)雜網(wǎng)絡(luò)模型研究的一種范式：明確建模目的

構(gòu)建簡(jiǎn)單模型t做出合理分析。接著介紹一個(gè)在20世紀(jì)60年代末就提出的有向無(wú)標(biāo)度網(wǎng)絡(luò)模型

--Price模型，該模型具有幕指數(shù)可調(diào)的幕律入度分布。BA模型則可以視為無(wú)向化的Price模型的一

個(gè)特例。本章還給出了Price模型和BA模型的計(jì)算機(jī)實(shí)現(xiàn)算法，并在此基礎(chǔ)上導(dǎo)出了“富者更富"現(xiàn)

象的節(jié)點(diǎn)復(fù)制機(jī)理。人們?cè)贐A模型的基礎(chǔ)上提出了多種多樣的擴(kuò)展和修正，第8章選介了其中兩個(gè)模

型：適應(yīng)度模型和局域世界演化模型。最后簡(jiǎn)要介紹了無(wú)標(biāo)度網(wǎng)絡(luò)的魯棒性分析。

一、BA無(wú)標(biāo)度網(wǎng)絡(luò)模型

1、模型描述：ER隨機(jī)圖和WS小世界模型忽略了世紀(jì)網(wǎng)絡(luò)的兩個(gè)重要特征：一是網(wǎng)絡(luò)的增長(zhǎng)特性;

二是網(wǎng)絡(luò)的優(yōu)先連接特性。基于這可個(gè)被忽略的因素，便提出了BA無(wú)標(biāo)度網(wǎng)絡(luò)模型。

BA無(wú)標(biāo)度網(wǎng)絡(luò)模型構(gòu)造算法

(1)增長(zhǎng)：從一個(gè)具有瓶。個(gè)節(jié)點(diǎn)的連通網(wǎng)絡(luò)開(kāi)始，每次引入一個(gè)新的節(jié)點(diǎn)并且連到m個(gè)已存在的

節(jié)點(diǎn)上，這里m?mo。

(2)優(yōu)先連接：一個(gè)新的節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率口1與節(jié)點(diǎn)I的度k之間滿足如

下關(guān)系：

kt

rii二次

2、嘉律度分布

可以通過(guò)仿真和理論分析來(lái)研究，BA網(wǎng)絡(luò)事都確實(shí)是具有幕律度分布的無(wú)標(biāo)度網(wǎng)絡(luò)。

二、Price模型

1、模型描述：Price有向網(wǎng)絡(luò)模型構(gòu)造算法

(1)增長(zhǎng)：從一個(gè)具有瓶。個(gè)孤立節(jié)點(diǎn)的網(wǎng)絡(luò)開(kāi)始，每次引入一個(gè)新的節(jié)點(diǎn)并且通過(guò)m條有向邊指

向m個(gè)已存在的節(jié)點(diǎn)上，這里m?瓶0。

(2)累計(jì)優(yōu)勢(shì)：一個(gè)新節(jié)點(diǎn)有邊指向一個(gè)已經(jīng)存在的入度為評(píng)的節(jié)點(diǎn)i的概率

in.

ki+a

L二小/+a)

2、幕指數(shù)可調(diào)的入度分布

3、幕指數(shù)可調(diào)的無(wú)向無(wú)標(biāo)度網(wǎng)絡(luò)

如果把Price模型中的每一條有向邊都視為無(wú)向邊，那么這樣構(gòu)成的無(wú)向網(wǎng)絡(luò)中的節(jié)點(diǎn)i的度k與

Price模型中的節(jié)點(diǎn)i的出度m和入度點(diǎn)之間具有如下關(guān)系：k=d+m。因此，基于Price模型的入度

分布對(duì)應(yīng)的無(wú)向網(wǎng)絡(luò)的度分布為

pk?（k-m+a）;y=2+a/m。

這樣就得到了幕指函數(shù)在（2,8）范圍內(nèi)可調(diào)的具有幕律度分布的無(wú)向無(wú)向網(wǎng)絡(luò)，

BA模型可以視為Price模型在取m=2時(shí)的特例：此時(shí)，由于*店+m,Price模型構(gòu)造算法中

的優(yōu)先連接概率公式即為BA模型構(gòu)造算法中的公式。因此，如果把Price模型中的每條有向邊都視為

無(wú)向邊，那么Price模型即為BA模型。

4、優(yōu)先連接機(jī)制的計(jì)算機(jī)實(shí)現(xiàn)

在計(jì)算機(jī)上實(shí)現(xiàn)Price模型和BA模型的關(guān)鍵是優(yōu)先連接機(jī)制的有效實(shí)現(xiàn)。

Price模型的計(jì)算機(jī)實(shí)現(xiàn)算法

（1）給定一個(gè)具有％個(gè)節(jié)點(diǎn)的初始強(qiáng)聯(lián)通網(wǎng)絡(luò)。把每一條邊所指向的節(jié)點(diǎn)的編號(hào)添加到數(shù)組

Array中。

（2）給定參數(shù)p￡[O,l]，對(duì)于，執(zhí)行如下操作：

①生成一個(gè)完全隨機(jī)數(shù)￡[0,1]；

②如果r<p,那么就完全隨機(jī)地在數(shù)組Array中選擇一個(gè)元素；

③如果r>=p,那么就完全隨機(jī)地選擇一個(gè)節(jié)點(diǎn)；

④執(zhí)行步驟①-③m次后,添加從新加入節(jié)點(diǎn)指向選定的m個(gè)節(jié)點(diǎn)的m條有向邊，并把這m個(gè)

節(jié)點(diǎn)的編號(hào)添加到數(shù)組Array中。

5、節(jié)點(diǎn)復(fù)制模型

在定成熟上，新加入節(jié)點(diǎn)傾向于模仿（復(fù)制）網(wǎng)絡(luò)中已有節(jié)點(diǎn)的行為。這種節(jié)點(diǎn)復(fù)制模式導(dǎo)致"富

者更富〃：某個(gè)節(jié)點(diǎn)如果已經(jīng)受到很多關(guān)注，那么今后就更有可能受到更多的關(guān)注。

節(jié)點(diǎn)復(fù)制模型構(gòu)造算法

(1)增長(zhǎng)：從一個(gè)具有四個(gè)孤立節(jié)點(diǎn)的網(wǎng)絡(luò)開(kāi)始，每次引入一個(gè)新的節(jié)點(diǎn)并且通過(guò)m條有向邊

指向個(gè)已存在的節(jié)點(diǎn)上，這里m

mm<°0

(2)節(jié)點(diǎn)復(fù)制：給定一個(gè)參數(shù)p￡[0,1],按照如下方式選擇已有節(jié)點(diǎn)，并添加從新節(jié)點(diǎn)指向該已

有節(jié)點(diǎn)的有向邊：

①生成一個(gè)隨機(jī)數(shù)

②如果r<p,那么就完全隨機(jī)地選擇一個(gè)節(jié)點(diǎn)，然后再完全隨機(jī)地選擇該節(jié)點(diǎn)所指向的一個(gè)鄰居

節(jié)點(diǎn)；

③如果r>=p,那么就完全隨機(jī)地選擇一個(gè)節(jié)點(diǎn)；

④執(zhí)行步驟①-③m次后，添加從新加入節(jié)點(diǎn)指向選定的m個(gè)節(jié)點(diǎn)的m條有向邊，并把這m個(gè)

節(jié)點(diǎn)的編號(hào)添加到數(shù)組Array中。

三、無(wú)標(biāo)度網(wǎng)絡(luò)模型的推廣

本節(jié)重點(diǎn)介紹BA模型的兩種推廣：一種是考慮到節(jié)點(diǎn)之間具有不同的競(jìng)爭(zhēng)能力的適應(yīng)度模型，另

一種是基于局域世界優(yōu)先連接的網(wǎng)絡(luò)模型。

1、適應(yīng)度模型

在許多實(shí)際的網(wǎng)絡(luò)中，節(jié)點(diǎn)的度及其增長(zhǎng)速度并非只與該節(jié)點(diǎn)的年齡有關(guān)，還與節(jié)點(diǎn)的內(nèi)在屬相相

關(guān)。如社會(huì)網(wǎng)絡(luò)中，個(gè)人的交際能力、WWW網(wǎng)站的內(nèi)容和科研論文的質(zhì)量等，研究人員把這一內(nèi)在的

性質(zhì)稱(chēng)為節(jié)點(diǎn)的適應(yīng)度，并據(jù)此在BA模型的基礎(chǔ)上提出了適應(yīng)度模型。

適應(yīng)度模型構(gòu)造算法：

(1)增長(zhǎng)：從一個(gè)具有瓶。個(gè)孤立節(jié)點(diǎn)的網(wǎng)絡(luò)開(kāi)始，每次引入一個(gè)新的節(jié)點(diǎn)并且通過(guò)m條有向邊指

向m個(gè)已存在的節(jié)點(diǎn)上，這里

(2)優(yōu)先連接:一個(gè)新節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率口:與節(jié)點(diǎn)i的度k和適應(yīng)度外之

間滿足如下關(guān)系：

4ik(

適應(yīng)度模型與BA無(wú)標(biāo)度模型的區(qū)別在于：適應(yīng)度模型中的優(yōu)先連接概率與節(jié)點(diǎn)的度和適應(yīng)度之

積成正比，而不是僅與節(jié)點(diǎn)的度成正比。

適應(yīng)度模型可能具有如下幾類(lèi)不同的特征：

(1)無(wú)標(biāo)度特征

(2)適者更富特征

(3)贏者通吃特征

2、局域世界演化網(wǎng)絡(luò)模型

四、魯棒性和脆弱性

無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)隨機(jī)節(jié)點(diǎn)故障具有極高的魯棒性：與隨機(jī)圖相比，最大連通子圖的相對(duì)大小在相對(duì)

高得多的f值時(shí)才下降到零而其平均路徑長(zhǎng)度的增長(zhǎng)則要緩慢的多。無(wú)標(biāo)度網(wǎng)絡(luò)的這種對(duì)隨機(jī)故障的

高度魯棒性來(lái)自于網(wǎng)絡(luò)度分布的極端非均勻性：絕大多數(shù)節(jié)點(diǎn)的度都相對(duì)很小而只有少量節(jié)點(diǎn)的度相

對(duì)很大。當(dāng)f較小時(shí)，隨機(jī)選取的節(jié)點(diǎn)都是度很小的節(jié)點(diǎn)，去除掉這些節(jié)點(diǎn)對(duì)整個(gè)網(wǎng)絡(luò)的連通性不會(huì)

產(chǎn)生大的影響。然而，正是這種非均勻性使得無(wú)標(biāo)度網(wǎng)絡(luò)對(duì)蓄意攻擊具有高度的脆弱性：只要有意識(shí)

地去除網(wǎng)絡(luò)中極少量度最大的節(jié)點(diǎn)就會(huì)對(duì)整個(gè)網(wǎng)絡(luò)的連通性產(chǎn)生大的影響。

第9章網(wǎng)絡(luò)傳播

將主要介紹，在把網(wǎng)絡(luò)結(jié)構(gòu)與經(jīng)典傳染病模型相結(jié)合的基礎(chǔ)上,得到的一些與傳統(tǒng)結(jié)果不一樣的

有意義的結(jié)果的基本知識(shí)。包括幾類(lèi)經(jīng)典的傳染病模型、均勻網(wǎng)絡(luò)與非均勻網(wǎng)絡(luò)上的傳播臨界值分析、

幾類(lèi)免疫策略的比較、節(jié)點(diǎn)的傳播影響力分析以及行為傳播的實(shí)證研究等內(nèi)容。

一、經(jīng)典的傳染病模型

在經(jīng)典的傳染病模型中，種群內(nèi)的N個(gè)個(gè)體的狀態(tài)可以分為如下幾類(lèi)：

(1)易染狀態(tài)S。一個(gè)個(gè)體在感染之前是處于易染狀態(tài)的，即該個(gè)體有可能被鄰居個(gè)體感染。

(2)感染狀態(tài)I。一個(gè)感染上某種病毒的個(gè)體就稱(chēng)為是處于感染狀態(tài)，該個(gè)體還會(huì)以一定概率感

染其鄰居個(gè)體。

(3)移除狀態(tài)R。也稱(chēng)為免疫狀態(tài)或恢復(fù)狀態(tài)。當(dāng)一個(gè)個(gè)體經(jīng)歷過(guò)一個(gè)完整的感染周期后,

該個(gè)體就不再被感染，因此就可以不再考慮該個(gè)體。

1、SI模型

假設(shè)一個(gè)易染個(gè)體在單位時(shí)間里與感染個(gè)體接觸井被傳染的概率為0。由于易染個(gè)體的比例為

S/N,時(shí)刻t網(wǎng)絡(luò)中總共有I(t)個(gè)感染個(gè)體，所以易染個(gè)體的數(shù)目按照如下變化率減少：

dSsi

哈嚴(yán),

相應(yīng)地，感染個(gè)體的數(shù)目按照如下變化率增加：

diSI

左邛N,

以上兩個(gè)方程即為完全混合假設(shè)下的SI模型的數(shù)學(xué)描述。

2、SIR模型

BS/

SIR模型第一階段仍與SI模型