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è)概念。P*表示網(wǎng)絡(luò)中度為k的節(jié)點(diǎn)占整個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)的比列，稱為度分布；〈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)。否則，就稱網(wǎng)絡(luò)不具有度相關(guān)性，或稱網(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)=1.聯(lián)合概率分布具有如下性質(zhì)：對(duì)稱性，即p(j,k)=p(k,j),歸一化，即Z物吒pO,比)=1,成=%訊余度分布，即4(k)=容pO/)，其中上濕瀏比*夕別為網(wǎng)絡(luò)中節(jié)點(diǎn)的Kmin度的最小值和最大值。(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)性：一、用條件概率，如果條件概率「。(j|k)與k相關(guān)，那么就說(shuō)明節(jié)點(diǎn)

度之間具有相關(guān)性，并且網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可能具有層析結(jié)構(gòu)。如果條件概率Pc（jlk）與k無(wú)關(guān)，那么就說(shuō)明網(wǎng)絡(luò)沒(méi)有度相關(guān)性。二、計(jì)算度為k的節(jié)點(diǎn)的鄰居節(jié)點(diǎn)的平均度，也稱度為k的節(jié)點(diǎn)的余平均度，記為〈上沖〉（k）。假設(shè)節(jié)點(diǎn)i的外個(gè)鄰居節(jié)點(diǎn)的度為k「,j=1，2，…外?？梢杂?jì)算節(jié)點(diǎn)i的余平均度，即節(jié)點(diǎn)i的也個(gè)鄰居節(jié)點(diǎn)的平均度〈上沖〉.如下：〈k〈knn〈kg〉（k）與條件概率和聯(lián)合概率之間具有如下關(guān)系：〈k〉（k）=^kmaxkrP（k'\k）=JL'Zkmaxk'6nnkfmC乳k'=km.nkk，其中，ekk，=%'%（如果網(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ò)是同配的；反之，如果〈knn）（k）是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)傾向于連接度大的節(jié)點(diǎn)，那么就稱網(wǎng)絡(luò)是度相關(guān)的，或稱說(shuō)網(wǎng)絡(luò)是同配的。相反，如果總體上度大的節(jié)點(diǎn)傾向于連接度小的節(jié)點(diǎn)，那么就稱網(wǎng)絡(luò)是度負(fù)相關(guān)的，或者稱網(wǎng)絡(luò)是異配的。7、同配系數(shù)：用于刻畫網(wǎng)絡(luò)是同配還是異配的指標(biāo)。網(wǎng)絡(luò)是度相關(guān)的就意味著6心和qjqk之間不恒等，因此，可以通過(guò)兩者之間的差的大小刻畫網(wǎng)絡(luò)的同配或者異配程度：〈jk〉-⑴〈k〉=亳/（%一歸）當(dāng)網(wǎng)絡(luò)為完全同配時(shí)，e.k=q.qk，上面式子達(dá)到最大值，即為余度分布@比的方差：帝以上近一［冷縱］2于是得到歸一化的相關(guān)系數(shù)，也稱為同配系數(shù)如下：r苛Zj,jJk（ejk-qjqk）顯然，re［-1,1］，如果r>0，那么網(wǎng)絡(luò)是同配的，如果r<0，那么網(wǎng)絡(luò)是異配的。|r|的大小反映了網(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è)常見的指標(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)的歸一化的度中心值定義為：Dq=4。2、介數(shù)中心性：是一個(gè)用于通過(guò)測(cè)量經(jīng)過(guò)某個(gè)節(jié)點(diǎn)的最短路徑的數(shù)目來(lái)刻畫節(jié)點(diǎn)重要性的指標(biāo)，簡(jiǎn)稱介數(shù)（BC）。具體的，節(jié)點(diǎn)i的介數(shù)定義為：日弓=乙衣"＜，其中，編為從9st節(jié)點(diǎn)s到節(jié)點(diǎn)t的最短路徑的數(shù)目，打農(nóng)為從節(jié)點(diǎn)s到節(jié)點(diǎn)t的g就條最短路徑中經(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ù)目，即為（N1）（N2）』23N222基于上式，一個(gè)包含N個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中的節(jié)點(diǎn)i的歸一化結(jié)束定義為Bq=n*Zs/?H歸一化介數(shù)的另外一個(gè)定義形式是：

BC.BC.=1S1N29st這是由Newman給出的定義，此式中包含了每個(gè)節(jié)點(diǎn)到自身的路徑，以及以節(jié)點(diǎn)i為起點(diǎn)或終點(diǎn)的路徑，N2則是網(wǎng)絡(luò)中所有可能的節(jié)點(diǎn)對(duì)（包括節(jié)點(diǎn)到自身的配對(duì)）。3、接近中心性：對(duì)于網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)I,可以計(jì)算該節(jié)點(diǎn)到網(wǎng)絡(luò)中所有節(jié)點(diǎn)的距離的平均值，記為右，即有%斗電其中《/是節(jié)點(diǎn)i到節(jié)點(diǎn)j的距離。這樣，就得到網(wǎng)絡(luò)平均路徑長(zhǎng)度的另一種計(jì)算公式：Lg%。引值得相對(duì)大小也在某種程度上反映了節(jié)點(diǎn)i在網(wǎng)絡(luò)中的相對(duì)重要性：引直越小意味著節(jié)點(diǎn)i更接近其他節(jié)點(diǎn)。我們把《的倒數(shù)定義為節(jié)點(diǎn)i的接近中心性，簡(jiǎn)稱接近數(shù)，用記號(hào)cq來(lái)表示：cq=t京財(cái)。4、k-殼和k-核k-殼的分解方法。經(jīng)分解，網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)對(duì)應(yīng)于唯一的k-殼指標(biāo)^，并且k-殼中所包含的節(jié)點(diǎn)的度值必然滿足k>>ks。實(shí)際網(wǎng)絡(luò)中的一種情況:度大的節(jié)點(diǎn)既然可能具有較大的么值從而位于k-殼分解的核心內(nèi)層，也有可能具有較小的ks值而位于k-殼分解的外層，從而使得對(duì)于某些問(wèn)題而言，度大的節(jié)點(diǎn)未必是重要的節(jié)點(diǎn)。在得到一個(gè)網(wǎng)絡(luò)的k-殼分解之后，我們把所有ks>>k的k-殼的并集稱為網(wǎng)絡(luò)的k-核，把指標(biāo)ks<<k的k-殼的并集稱為網(wǎng)絡(luò)的k-皮。k-殼的一個(gè)的一個(gè)等價(jià)的定義是：它是一個(gè)網(wǎng)絡(luò)中所有度值不小于k的節(jié)點(diǎn)組成的連通片?；趉-殼分解（k-核分解）可以把網(wǎng)絡(luò)中的節(jié)點(diǎn)粗?；瘎澐譃?組：核心、對(duì)等連通片和孤立片。5、特征向量中心性：其基本想法是：一個(gè)節(jié)點(diǎn)的重要性既取決于其鄰居節(jié)點(diǎn)的數(shù)量，也取決于其鄰居節(jié)點(diǎn)的重要性。記^為節(jié)點(diǎn)i的重要性度量值，那么，應(yīng)該有：x廣弘auxj其中c為一比例常數(shù)，A=(%)仍然是網(wǎng)絡(luò)的鄰接矩陣。記X=[xj2xn]t，則上面的式子可寫成如下矩陣形式：X=cAx，上式意味著x是矩陣A與特征值ci對(duì)應(yīng)的特征向量，故此稱為特征向量中心性。6、HITS算法：基本思想：每個(gè)網(wǎng)頁(yè)的重要性有兩種刻畫指標(biāo)權(quán)威性和樞紐性。一般的，一個(gè)頁(yè)面的權(quán)威性有指向該頁(yè)面的其他頁(yè)面的樞紐值來(lái)刻畫：如果一個(gè)頁(yè)面被多個(gè)具有高樞紐值的頁(yè)面所指向，那么該頁(yè)面就具有高得權(quán)威性。另一方面，一個(gè)頁(yè)面的樞紐值由它所指向的頁(yè)面的權(quán)威值來(lái)刻畫：如果一個(gè)頁(yè)面指向多個(gè)具有高權(quán)威值得頁(yè)面，那么該頁(yè)面就具有高得樞紐值。7、PageRank算法：基本思想：WWW是一個(gè)頁(yè)面的重要性取決于指向它的其他頁(yè)面的數(shù)量和質(zhì)量。8、節(jié)點(diǎn)相似性與鏈路預(yù)測(cè)：刻畫節(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ì)未知鏈接，也稱丟失鏈接的預(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)介紹了幾類典型的隨機(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ù)目一般至多是O(N)而不是O(N2)。在具有相同節(jié)點(diǎn)數(shù)的所有網(wǎng)絡(luò)中，全耦合網(wǎng)絡(luò)具有最多的邊數(shù)、最大的聚類系數(shù)Cgc=1和最小的平均路徑長(zhǎng)度婦。=1.2、最近鄰耦合網(wǎng)絡(luò)：網(wǎng)絡(luò)中，每一個(gè)節(jié)點(diǎn)只和它周圍的鄰居節(jié)點(diǎn)相連。如：體育游戲或者跳舞等集體運(yùn)動(dòng)是，所有人手牽手排成一個(gè)長(zhǎng)隊(duì)或者圍成一圈。這類網(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ā)生切換。最近鄰耦合網(wǎng)絡(luò)的聚類系數(shù)％=3網(wǎng)("角形的數(shù)數(shù)目3*N*N*($3*(K2)4*(K1)最近鄰耦合網(wǎng)絡(luò)的平均路徑長(zhǎng)度婦次工孕/2[2m/K]小/2K。gcN/2m13、星型耦合網(wǎng)絡(luò)：它有一個(gè)中心節(jié)點(diǎn)，其余的N-1個(gè)點(diǎn)斗志與這個(gè)中心點(diǎn)連接，而它們彼此之間不連接。如：公共服務(wù)器連接個(gè)人電腦。星型耦合網(wǎng)絡(luò)的聚類系數(shù):Cgc=0,這是因?yàn)橹行墓?jié)點(diǎn)的N-1鄰居節(jié)點(diǎn)之間互不相連，從而中心節(jié)點(diǎn)的聚類系數(shù)為0.星型耦合網(wǎng)絡(luò)的平均路徑長(zhǎng)度L=2-皿4-2(N-8)。gcN(N1)二、隨機(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,M)。ER隨機(jī)圖G(N,M)的構(gòu)造算法:初始化：給定N個(gè)節(jié)點(diǎn)和戴天價(jià)的邊數(shù)M.隨機(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)之間有一條邊的概率固定為p。ER隨機(jī)圖G(N,p)的構(gòu)造算法：初始化：給定N個(gè)節(jié)點(diǎn)以及連邊概率pE[0,1]。隨機(jī)連邊：選擇一對(duì)沒(méi)有邊相連的不同的節(jié)點(diǎn)。生成一個(gè)隨機(jī)數(shù)rE(0,1)。如果r<p,那么就在這對(duì)點(diǎn)之間添加一條邊；否則就不添加邊。重復(fù)步驟①?③，直至所有的節(jié)點(diǎn)對(duì)都被選擇過(guò)一次。三、廣義隨機(jī)圖配置模型：在配置模型中事先給定的是網(wǎng)絡(luò)的度序列/1，d2，…』州｝，其中非負(fù)整數(shù)q為節(jié)點(diǎn)i的度。關(guān)于度序列，給兩個(gè)必要條件：由于網(wǎng)絡(luò)中所有節(jié)點(diǎn)的度值之和等于網(wǎng)絡(luò)中所有邊數(shù)之和的兩倍，Z告q必須為偶數(shù)并且有Z2d.<<N(N-1)；11td.<<N-1，i=1,2,…,N,等號(hào)只有當(dāng)一個(gè)節(jié)點(diǎn)與其他所有節(jié)點(diǎn)都相連時(shí)才成立。在上述條件的基礎(chǔ)上少許加以推廣，就可得到如下的充要條件：定理：一個(gè)非負(fù)整數(shù)序列｛d1，d2，…4?｝是某個(gè)簡(jiǎn)單圖的度序列的充要條件為：Z告dt為偶數(shù)；對(duì)于每個(gè)整數(shù)k，1<<k<<N，均有Z2d.<<k(k-1)+Z%min(k,d.)11IJK1J配置模型構(gòu)造算法：(1)初始化：根據(jù)給定度序列確定N個(gè)節(jié)點(diǎn)的度值。（2）引出線頭：從度為也的節(jié)點(diǎn)i引出kt個(gè)線頭。共有Z告kt=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ò)稱為該實(shí)際網(wǎng)絡(luò)的隨機(jī)化網(wǎng)絡(luò)。這里的“某些性質(zhì)A”可以是平局度、度分布、聚類系數(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是否為這類隨機(jī)化網(wǎng)絡(luò)的典型特征。這類隨機(jī)化網(wǎng)絡(luò)模型在統(tǒng)計(jì)學(xué)上稱為零模型。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)的度值保持不變（即度序列保持不變）。（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（k1，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(wǎng)絡(luò)數(shù)據(jù)的基礎(chǔ)上，保持每個(gè)節(jié)點(diǎn)的度不變，但是使得連邊的位置盡可能的隨機(jī)化，以得到一個(gè)具有給定序列的隨機(jī)網(wǎng)絡(luò)。2013-08-01——2013-08-15課題學(xué)習(xí)進(jìn)度。第七章小世界網(wǎng)絡(luò)模型本章圍繞與小世界網(wǎng)絡(luò)模型有關(guān)的兩個(gè)問(wèn)題而展開。第一個(gè)問(wèn)題是如何構(gòu)建既具有聚類特性又具有小世界性質(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è)模型的聚類系數(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)在常稱為WS小世界模型。WS小世界模型構(gòu)造算法：（1）從規(guī)則圖開始：給定一個(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ī)重連提出了可、小世界網(wǎng)絡(luò)模型。仿真分析:通過(guò)仿真揭示了當(dāng)重連概率較小時(shí)可以得到既具有較短的平均路徑長(zhǎng)度又具有較高的聚類系數(shù)的小世界網(wǎng)絡(luò)。實(shí)際驗(yàn)證：驗(yàn)證了3個(gè)實(shí)際網(wǎng)絡(luò)的平均路徑長(zhǎng)度和聚類系數(shù)。影響分析：通過(guò)仿真說(shuō)明小世界特征對(duì)于網(wǎng)絡(luò)動(dòng)力學(xué)的影響。2、NW小世界模型：NW模型是通過(guò)用“隨機(jī)化加邊”取代WS模型的構(gòu)造中的“隨機(jī)化重連”而得到的。在NW模型中，原來(lái)的NK/2條邊保持不變，而是在此基礎(chǔ)上再隨機(jī)添加一些邊，為了便于比較，這些添加的長(zhǎng)程邊數(shù)目的均值同樣取為NKp/2。NW小世界模型構(gòu)造算法：(1)從規(guī)則圖開始：給定一個(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、聚類系數(shù)2、度分布3、平均路徑長(zhǎng)度三、Kleinberg模型與可搜索性Kleinberg對(duì)二維NW小世界模型做了如下修改：假設(shè)每條邊都是有向邊。這對(duì)底層的規(guī)則網(wǎng)格沒(méi)有影響，因?yàn)橐?guī)則網(wǎng)格上的兩個(gè)節(jié)點(diǎn)要么互為鄰居，要么互相都不是鄰居。假設(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的概率n印與這兩個(gè)節(jié)點(diǎn)之間的網(wǎng)絡(luò)距離的冪函數(shù)[d(u,v)]?成正比，這里a〉=0是一個(gè)參數(shù)。二維網(wǎng)格上的Kleinberg模型構(gòu)造算法:從規(guī)則網(wǎng)格開始：給定一個(gè)含有N=N*N個(gè)點(diǎn)的最近鄰耦合網(wǎng)絡(luò)，它們分布在一個(gè)二維網(wǎng)格上，使得每一行和每一列都恰好徊個(gè)節(jié)點(diǎn)。每個(gè)節(jié)點(diǎn)都通過(guò)有向邊指向所有與該節(jié)點(diǎn)的網(wǎng)格距離不超過(guò)p>=1的節(jié)點(diǎn)。隨機(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的概率n印為n=[d(u.v)]a_UV屋[d(u,u)]a考慮二維Kleinberg網(wǎng)絡(luò)模型上的搜索問(wèn)題，假設(shè)每個(gè)節(jié)點(diǎn)采用的都是基于局部信息的分散式算法。我們有：對(duì)于0〈=a〈2,存在一個(gè)與p,q,a相關(guān)但與N無(wú)關(guān)的常數(shù)C”平均傳遞步數(shù)都有一個(gè)下界CaN(2a)/3o當(dāng)a=2時(shí)，當(dāng)前新的持有節(jié)點(diǎn)只需把信件傳遞給一個(gè)在網(wǎng)格距離上最接近目標(biāo)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)，這種分散式算法的平均傳遞步數(shù)有一個(gè)上界C2(logN)2，其中q是一個(gè)與N無(wú)關(guān)的常數(shù)。對(duì)于a〉2,存在一個(gè)與p,q,a相關(guān)但與N無(wú)關(guān)的常數(shù)q,使得對(duì)于任意的分散式算法，平均傳遞步數(shù)都有一個(gè)下界CaN(2a)/&)。說(shuō)明：當(dāng)質(zhì)2時(shí)，分散式算法所需的平均傳遞步數(shù)至多是logN的多項(xiàng)式函數(shù)；而當(dāng)以=2時(shí)，分散式算法所需的傳遞步數(shù)T至少是N的多項(xiàng)式函數(shù)，即T〉=cRg其中，c是與N無(wú)關(guān)的常數(shù)，并且(2a)/3，0?a<2，B=\°^^，a>2。val第八章無(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è)具有n0個(gè)節(jié)點(diǎn)的連通網(wǎng)絡(luò)開始，每次引入一個(gè)新的節(jié)點(diǎn)并且連到m個(gè)已存在的節(jié)點(diǎn)上，這里m?m0o（2）優(yōu)先連接：一個(gè)新的節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率幾與節(jié)點(diǎn)I的度也之間滿足如下關(guān)系：n=41磯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è)具有n0個(gè)孤立節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個(gè)新的節(jié)點(diǎn)并且通過(guò)m條有向邊指向m個(gè)已存在的節(jié)點(diǎn)上，這里m?m0。（2）累計(jì)優(yōu)勢(shì)：一個(gè)新節(jié)點(diǎn)有邊指向一個(gè)已經(jīng)存在的入度為k機(jī)的節(jié)點(diǎn)i的概率n=—1與以宵）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的度焰與Price模型中的節(jié)點(diǎn)i的出度m和入度蜜之間具有如下關(guān)系吊廣昭孔+m。因此，基于Price模型的入度分布對(duì)應(yīng)的無(wú)向網(wǎng)絡(luò)的度分布為pfc~（k—ma）-y,y=2+a/m。這樣就得到了冪指函數(shù)在（2,8）范圍內(nèi)可調(diào)的具有冪律度分布的無(wú)向無(wú)向網(wǎng)絡(luò)。BA模型可以視為Price模型在取m=2時(shí)的特例：此時(shí)，由于k.=fc?n+m，Price模II型構(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è)具有m0個(gè)節(jié)點(diǎn)的初始強(qiáng)聯(lián)通網(wǎng)絡(luò)。把每一條邊所指向的節(jié)點(diǎn)的編號(hào)添加到數(shù)組Array中。（2）給定參數(shù)p^[0,1],對(duì)于t=1,2,…,N-m0，執(zhí)行如下操作：生成一個(gè)完全隨機(jī)數(shù)rE[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)造算法增長(zhǎng)：從一個(gè)具有m0個(gè)孤立節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個(gè)新的節(jié)點(diǎn)并且通過(guò)m條有向邊指向m個(gè)已存在的節(jié)點(diǎn)上，這里m<m0o節(jié)點(diǎn)復(fù)制：給定一個(gè)參數(shù)p￡[0,1]，按照如下方式選擇已有節(jié)點(diǎn)，并添加從新節(jié)點(diǎn)指向該已有節(jié)點(diǎn)的有向邊：生成一個(gè)隨機(jī)數(shù)re[0,1];如果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ì)稱為節(jié)點(diǎn)的適應(yīng)度，并據(jù)此在BA模型的基礎(chǔ)上提出了適應(yīng)度模型。適應(yīng)度模型構(gòu)造算法：(1)增長(zhǎng)：從一個(gè)具徹0個(gè)孤立節(jié)點(diǎn)的網(wǎng)絡(luò)開始，每次引入一個(gè)新的節(jié)點(diǎn)并且通過(guò)m條有向邊指向m個(gè)已存在的節(jié)點(diǎn)上，這里m<m0。（2）優(yōu)先連接：一個(gè)新節(jié)點(diǎn)與一個(gè)已經(jīng)存在的節(jié)點(diǎn)i相連接的概率n,與節(jié)點(diǎn)i的度也和適應(yīng)度％之間滿足如下關(guān)系:適應(yīng)度模型與BA無(wú)標(biāo)度模型的區(qū)別在于：適應(yīng)度模型中的優(yōu)先連接概率與節(jié)點(diǎn)的度和適應(yīng)度之積成正比，而不是僅與節(jié)點(diǎn)的度成正比。適應(yīng)度模型可能具有如下幾類不同的特征：（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í)。包括幾類經(jīng)典的傳染病模型、均勻網(wǎng)絡(luò)與非均勻網(wǎng)絡(luò)上的傳播臨界值分析、幾類免疫策略的比較、節(jié)點(diǎn)的傳播影響力分析以及行為傳播的實(shí)證研究等內(nèi)容。、經(jīng)典的傳染病模型在經(jīng)典的傳染病模型中，種群內(nèi)的N個(gè)個(gè)體的狀態(tài)可以分為如下幾類：易染狀態(tài)S。一個(gè)個(gè)體在感染之前是處于易染狀態(tài)的，即該個(gè)體有可能被鄰居個(gè)體感染。感染狀態(tài)I。一個(gè)感染上某種病毒的個(gè)體就稱為是處于感染狀態(tài)，該個(gè)體還會(huì)以一定概率感染其鄰居個(gè)體。移除狀態(tài)R。也稱為免疫狀態(tài)或恢復(fù)狀態(tài)。當(dāng)一個(gè)個(gè)體經(jīng)歷過(guò)一個(gè)完整的感染周期后，該個(gè)體就不再被感染，因此就可以不再考慮該個(gè)體。1、SI模型假設(shè)一個(gè)易染個(gè)體在單位時(shí)間里與感染個(gè)體接觸并被傳染的概率為B。由于易染個(gè)體的比例為S/N,時(shí)刻t網(wǎng)絡(luò)中