復(fù)雜網(wǎng)絡(luò)ComplexNetwork計(jì)算機(jī)學(xué)院目錄1引言2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性3復(fù)雜網(wǎng)絡(luò)模型本文目錄結(jié)構(gòu)4總結(jié)

引言自然界中存在的大量復(fù)雜系統(tǒng)都可以通過形形色色的網(wǎng)絡(luò)加以描述。一個(gè)典型的網(wǎng)絡(luò)是由許多節(jié)點(diǎn)與連接兩個(gè)節(jié)點(diǎn)之間的一些邊組成的,其中節(jié)點(diǎn)用來代表真實(shí)系統(tǒng)中不同的個(gè)體,而邊則用來表示個(gè)體之間的關(guān)系,通常是當(dāng)兩個(gè)節(jié)點(diǎn)之間具有某種特定的關(guān)系時(shí)連一條邊,反之則不連邊。有邊相連的兩個(gè)節(jié)點(diǎn)在網(wǎng)絡(luò)中被看作是相鄰的。。1引言復(fù)雜網(wǎng)絡(luò)的發(fā)展背景例如,神經(jīng)系統(tǒng)可以看作是大量神經(jīng)細(xì)胞通過神經(jīng)纖維相互連接形成的網(wǎng)絡(luò)；計(jì)算機(jī)網(wǎng)絡(luò)可以看作是自主工作的計(jì)算機(jī)通過通信介質(zhì)如光纜、雙絞線、同軸電纜等相互連接形成的網(wǎng)絡(luò)。類似的還有電力網(wǎng)絡(luò)、社會(huì)關(guān)系網(wǎng)絡(luò)、交通網(wǎng)絡(luò)等等。1引言神經(jīng)網(wǎng)絡(luò)計(jì)算機(jī)網(wǎng)絡(luò)數(shù)學(xué)家和物理學(xué)家在考慮網(wǎng)絡(luò)的時(shí)候,往往只關(guān)心節(jié)點(diǎn)之間有沒有邊相連,至于節(jié)點(diǎn)在什么位置,邊長(zhǎng)還是短,是彎曲還是平直,有沒有相交等等都是他們不在意的。因此,我們把網(wǎng)絡(luò)不依賴于節(jié)點(diǎn)的具體位置和邊的具體形態(tài)就能表現(xiàn)出來的性質(zhì)叫做網(wǎng)絡(luò)的拓?fù)湫再|(zhì),相應(yīng)的結(jié)構(gòu)叫做網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu).那么,什么樣的拓?fù)浣Y(jié)構(gòu)比較適用于描述真實(shí)的系統(tǒng)呢?1引言兩百多年來,對(duì)這個(gè)問題的研究經(jīng)歷了三個(gè)階段。在最初的一百多年里,科學(xué)家們認(rèn)為真實(shí)系統(tǒng)各因素之間的關(guān)系可以用一些規(guī)則的結(jié)構(gòu)表示,例如二維平面上的歐幾里德格網(wǎng),它看起來像是格子體恤衫上的花紋;又如最近鄰環(huán)網(wǎng),它總是會(huì)讓你想到一群手牽著手、圍著篝火跳圓圈舞的姑娘.

1引言到了20世紀(jì)50年代末,數(shù)學(xué)家們想出了一種新的構(gòu)造網(wǎng)絡(luò)的方法,在這種方法下,兩個(gè)節(jié)點(diǎn)之間連邊與否不再是確定的事情,而是根據(jù)一個(gè)概率決定.數(shù)學(xué)家把這樣生成的網(wǎng)絡(luò)叫做隨機(jī)網(wǎng)絡(luò),它在接下來的40年里一直被很多科學(xué)家認(rèn)為是描述真實(shí)系統(tǒng)最適宜的網(wǎng)絡(luò).直到最近幾年，由于計(jì)算機(jī)數(shù)據(jù)處理和運(yùn)算能力的飛速發(fā)展,科學(xué)家們發(fā)現(xiàn)大量的真實(shí)網(wǎng)絡(luò)既不是規(guī)則網(wǎng)絡(luò)，也不是隨機(jī)網(wǎng)絡(luò),而是具有與前兩者皆不同的統(tǒng)計(jì)特征的網(wǎng)絡(luò)。這樣的一些網(wǎng)絡(luò)被科學(xué)家們叫做復(fù)雜網(wǎng)絡(luò)（ComplexNetwork)，對(duì)于它們的研究標(biāo)志著第三階段的到來。1引言大規(guī)模復(fù)雜網(wǎng)絡(luò)1引言復(fù)雜網(wǎng)絡(luò)的定義具有自組織、自相似、吸引子、小世界、無標(biāo)度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò)?！X學(xué)森統(tǒng)計(jì)特性統(tǒng)計(jì)特性2最短路徑長(zhǎng)度、平均最短路徑長(zhǎng)度、介數(shù)1度、度分布和度相關(guān)性2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性3聚類系數(shù)4社區(qū)結(jié)構(gòu)5層次性2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性度、度分布和度相關(guān)性無向網(wǎng)絡(luò)的節(jié)點(diǎn)的度是指與節(jié)點(diǎn)連接的邊數(shù)；而有向網(wǎng)絡(luò)的節(jié)點(diǎn)的度分為入度和出度。網(wǎng)絡(luò)中所有節(jié)點(diǎn)度的列表稱為度序列，度序列的平均值稱為網(wǎng)絡(luò)的平均度,記為<k>。給定了網(wǎng)絡(luò)的度序列就確定了該網(wǎng)絡(luò)的度分布。度分布是指從圖中隨機(jī)選擇一個(gè)節(jié)點(diǎn)其度為k的概率，記為P(k)。度分布是網(wǎng)絡(luò)的最基本的拓?fù)涮匦?。根?jù)度分布，可以將網(wǎng)絡(luò)分為隨機(jī)圖、無標(biāo)度網(wǎng)絡(luò)和指數(shù)網(wǎng)絡(luò)等。度分布一個(gè)非常有用的表示(生成函數(shù)表示法)為:其中pk表示度為k的節(jié)點(diǎn)在網(wǎng)絡(luò)中的比例.

2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性度、度分布和度相關(guān)性在隨機(jī)圖模型中,任意兩個(gè)節(jié)點(diǎn)間相連的概率為p,即任意節(jié)點(diǎn)連接到任意的其它節(jié)點(diǎn)的概率都是相同的.但在許多現(xiàn)實(shí)網(wǎng)絡(luò)中,存在著一定的混合模式，即一個(gè)節(jié)點(diǎn)傾向于連接到某一些節(jié)點(diǎn)。研究者也發(fā)現(xiàn)，許多網(wǎng)絡(luò)邊的兩節(jié)點(diǎn)間的度也存在依賴關(guān)系,即度-度相關(guān)性。

如果度高的節(jié)點(diǎn)傾向于連接其它度高的節(jié)點(diǎn),稱為同配混合；如果度高的節(jié)點(diǎn)傾向于連接其它度低的節(jié)點(diǎn)稱為異配混合。網(wǎng)絡(luò)的同配性(異配性)影響網(wǎng)絡(luò)的結(jié)構(gòu)和行為.按照度同配混合的網(wǎng)絡(luò)比對(duì)應(yīng)的異配網(wǎng)絡(luò)更利于滲流；對(duì)于節(jié)點(diǎn)刪除,同配混合的網(wǎng)絡(luò)要比異配和中性的網(wǎng)絡(luò)更具有魯棒性.2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性最短路徑長(zhǎng)度、平均最短路徑長(zhǎng)度、介數(shù)對(duì)于無權(quán)網(wǎng)絡(luò),網(wǎng)絡(luò)中任意兩點(diǎn)間的最短路徑是從一個(gè)節(jié)點(diǎn)到另一個(gè)節(jié)點(diǎn)的最少邊數(shù)；對(duì)于有權(quán)網(wǎng)絡(luò),兩點(diǎn)間的最短路徑是指權(quán)值之和為最小的路徑。網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間的最短路徑長(zhǎng)度的最大值稱為網(wǎng)絡(luò)的直徑。平均最短路徑長(zhǎng)度是網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)之間的最短路徑長(zhǎng)度的平均值。

平均路徑長(zhǎng)度可以做為網(wǎng)絡(luò)信息傳遞效率的度量,網(wǎng)絡(luò)的效率定義為：這里,n表示節(jié)點(diǎn)數(shù)，dij為兩個(gè)節(jié)點(diǎn)i和j之間的最短路徑長(zhǎng)度。網(wǎng)絡(luò)的平均最短路徑長(zhǎng)度較小的現(xiàn)象稱為小世界效應(yīng)。許多現(xiàn)實(shí)網(wǎng)絡(luò)具有小世界效應(yīng)，如電影演員網(wǎng)絡(luò)(平均最短路徑為3.48)，對(duì)等網(wǎng)絡(luò)(平均最短路徑為4.28)，代謝網(wǎng)絡(luò)(平均最短路徑是2.56).

2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性最短路徑長(zhǎng)度、平均最短路徑長(zhǎng)度、介數(shù)為了度量節(jié)點(diǎn)在網(wǎng)絡(luò)中的重要性——中心性，引進(jìn)了節(jié)點(diǎn)介數(shù)概念，定義如下：邊介數(shù)是經(jīng)過這條邊的節(jié)點(diǎn)對(duì)的最短路徑數(shù)，它在社區(qū)發(fā)現(xiàn)中為區(qū)分一個(gè)社區(qū)的內(nèi)部邊和社區(qū)之間的邊提供了一種有效的度量標(biāo)準(zhǔn).2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性聚類系數(shù)二元關(guān)系R,如果aRb,bRc,那么aRc,則稱R是傳遞的。熟人網(wǎng)絡(luò)中，也有類似的特性，即擁有一個(gè)共同朋友的兩個(gè)人他們也彼此熟悉，這種性質(zhì)稱為網(wǎng)絡(luò)的聚類性，也稱為傳遞性。傳遞性意味著出現(xiàn)三角形，定義節(jié)點(diǎn)i聚類系數(shù)如下：整個(gè)網(wǎng)絡(luò)的聚類系數(shù)C就是所有節(jié)點(diǎn)i的聚類系數(shù)Ci的平均值,且有0≤C≤1。對(duì)于一些無標(biāo)度網(wǎng)絡(luò),局部聚類系數(shù)Ci隨著節(jié)點(diǎn)i的度下降而下降。隨機(jī)網(wǎng)絡(luò)的聚類系數(shù)為O(n‐1)，當(dāng)網(wǎng)絡(luò)規(guī)模極大時(shí)趨于零，而多數(shù)現(xiàn)實(shí)網(wǎng)絡(luò)的聚類系數(shù)顯著大于零，a即具有明顯的聚類特性。-2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性社區(qū)結(jié)構(gòu)社區(qū)結(jié)構(gòu)是許多現(xiàn)實(shí)網(wǎng)絡(luò)具有的一個(gè)共同的特征,即網(wǎng)絡(luò)的節(jié)點(diǎn)可以分成幾個(gè)組,每個(gè)組內(nèi)部的節(jié)點(diǎn)連接稠密,而組之間的節(jié)點(diǎn)連接稀疏，下圖是一個(gè)包含三個(gè)社區(qū)的一個(gè)簡(jiǎn)單網(wǎng)絡(luò)。社區(qū)結(jié)構(gòu)的發(fā)現(xiàn)具有重要的意義，例如在WWW中的社區(qū)對(duì)應(yīng)著一組關(guān)于某個(gè)主題的網(wǎng)頁；社會(huì)網(wǎng)絡(luò)中的社區(qū)對(duì)應(yīng)著有著共同愛好或背景的一群人；生化網(wǎng)絡(luò)中的社區(qū)則對(duì)應(yīng)著某個(gè)復(fù)合體或某種功能。因此，社區(qū)發(fā)現(xiàn)是當(dāng)前復(fù)雜網(wǎng)絡(luò)研究的一個(gè)熱點(diǎn)方向，并且已經(jīng)提出了各種方法，如基于介數(shù)度量的方法、隨機(jī)游走方法、電阻網(wǎng)絡(luò)方法、拉普拉斯特征值方法、極值優(yōu)化方法、派系過濾算法等。2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性社區(qū)結(jié)構(gòu)一個(gè)廣泛使用的度量網(wǎng)絡(luò)的社區(qū)結(jié)構(gòu)的量是模塊度，它定義為：設(shè)網(wǎng)絡(luò)分為n個(gè)社區(qū)，則定義一個(gè)n*n的矩陣e，每一行和每一列都代表一個(gè)社區(qū)，矩陣元素eij表示社區(qū)i和j間的邊數(shù)占網(wǎng)絡(luò)總邊數(shù)的比例，eii就表示社區(qū)i內(nèi)部邊所占的比例，ai=∑eij表示第i行或第i列元素之和,即與第i個(gè)社區(qū)的節(jié)點(diǎn)相連的邊的總比例,則模塊度定義為:即社區(qū)內(nèi)部邊的比例減去具有同樣社區(qū)劃分但節(jié)點(diǎn)間是隨機(jī)連接的網(wǎng)絡(luò)的這一值的期望。Q的值在-1與1之間，Q越接近1(這是最大值)預(yù)示著具有越強(qiáng)的社區(qū)結(jié)構(gòu)。2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計(jì)特性層次性按層次組織是許多復(fù)雜系統(tǒng)的一個(gè)共同特征。在代謝網(wǎng)絡(luò)中，有許多小的連接密集的簇，它們會(huì)相互結(jié)合形成較大較稀疏的簇，而這些簇又可能進(jìn)一步形成更大更稀疏的簇。這種自相似地嵌套形成了我們現(xiàn)實(shí)網(wǎng)絡(luò)的嚴(yán)格而又精細(xì)的結(jié)構(gòu)。有趣地是，網(wǎng)絡(luò)的層次性特性,可以通過簡(jiǎn)單的量來捕獲，即C(k)曲線滿足C(K)~k﹣1。Clauset等人建立了一種層次隨機(jī)圖模型，利用該模型對(duì)現(xiàn)實(shí)網(wǎng)絡(luò)進(jìn)行擬合，發(fā)現(xiàn)網(wǎng)絡(luò)的層次結(jié)構(gòu)可以解釋網(wǎng)絡(luò)的許多其它特征，如平均度、聚類系數(shù)和最短路徑等。發(fā)現(xiàn)網(wǎng)絡(luò)中的連接往往需要在實(shí)驗(yàn)室或現(xiàn)場(chǎng)付出高昂的費(fèi)用，這就使得許多現(xiàn)實(shí)網(wǎng)絡(luò)是不完備的，在這種情形下預(yù)測(cè)網(wǎng)絡(luò)中丟失的連接具有重要的意義。Clauset進(jìn)一步利用建立的模型設(shè)計(jì)了一個(gè)丟失連接的預(yù)測(cè)器，它與傳統(tǒng)的方法相比,能夠應(yīng)用于更廣泛類型的網(wǎng)絡(luò)結(jié)構(gòu)。

復(fù)雜網(wǎng)絡(luò)模型復(fù)雜網(wǎng)絡(luò)模型隨機(jī)圖小世界網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò)BA模型3復(fù)雜網(wǎng)絡(luò)模型隨機(jī)圖是圖論中最年輕的分支之一，對(duì)它的系統(tǒng)研究起源于1959年保羅·埃爾德什和阿爾弗雷德·雷尼的工作，他們發(fā)表了一系列的論文，建立了豐富的隨機(jī)圖理論的基礎(chǔ)?，F(xiàn)實(shí)網(wǎng)絡(luò)具有復(fù)雜的拓?fù)浣Y(jié)構(gòu)和未知的組織原理，總是呈獻(xiàn)出某種隨機(jī)性，因此用隨機(jī)圖作為網(wǎng)絡(luò)的模型是最直接的一種選擇。一個(gè)隨機(jī)圖實(shí)際上是將給定的頂點(diǎn)之間隨機(jī)地連上邊。邊的產(chǎn)生可以依賴于不同的隨機(jī)方式，這樣就產(chǎn)生了不同的隨機(jī)圖模型。一個(gè)典型的模型是埃爾德什和雷尼共同研究的ER模型。ER模型是指在給定n個(gè)頂點(diǎn)后，規(guī)定每?jī)蓚€(gè)頂點(diǎn)之間都以p的概率連起來（0≤p≤1），而且這些判定之間兩兩無關(guān)。這樣得到的隨機(jī)圖一般記作或ERn(p)。3復(fù)雜網(wǎng)絡(luò)模型隨機(jī)圖許多現(xiàn)實(shí)網(wǎng)絡(luò)如技術(shù)網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和社會(huì)網(wǎng)絡(luò)等，既不是完全規(guī)則的，也不是完全隨機(jī)的，而是介于兩者之間。Watts和Strogatz基于這些觀察,提出了WS模型，是指對(duì)一個(gè)具有n個(gè)節(jié)點(diǎn)的環(huán)格，初始時(shí)每個(gè)節(jié)點(diǎn)有k個(gè)鄰居，將每條邊以概率p進(jìn)行隨機(jī)重繞的過程。由于該模型生成的網(wǎng)絡(luò)具有較短的特征路徑，即網(wǎng)絡(luò)具有小世界效應(yīng)，故稱為小世界網(wǎng)絡(luò)，WS模型也因此常稱為小世界網(wǎng)絡(luò)(模型)。小世界網(wǎng)絡(luò)3復(fù)雜網(wǎng)絡(luò)模型上述的構(gòu)造過程有可能破壞網(wǎng)絡(luò)的連通，因此Newman和Watts稍后提出了通過隨機(jī)化加邊的方法構(gòu)造小世界網(wǎng)絡(luò)的模型，即NW模型。還有許多改進(jìn)的模型：加點(diǎn)、加邊、去點(diǎn)、去邊以及不同形式的交叉，產(chǎn)生多種形式的小世界模型。小世界網(wǎng)絡(luò)具有高的聚類系數(shù)，WS小世界網(wǎng)絡(luò)的聚類系數(shù)為：而NW小世界網(wǎng)絡(luò)的聚類系數(shù)為：小世界網(wǎng)絡(luò)的典型特征是平均最短路徑滿足對(duì)數(shù)標(biāo)度，但是到目前為止還沒有精確的解析表達(dá)式。小世界網(wǎng)絡(luò)的度分布與多數(shù)現(xiàn)實(shí)網(wǎng)絡(luò)并不能很好匹配，對(duì)于NW模型和WS模型，其表達(dá)式都比較復(fù)雜。小世界網(wǎng)絡(luò)3復(fù)雜網(wǎng)絡(luò)模型節(jié)點(diǎn)度服從冪律分布，是指具有某個(gè)特定度的節(jié)點(diǎn)數(shù)目與這個(gè)特定的度之間的關(guān)系可以用一個(gè)冪函數(shù)近似地表示，冪函數(shù)曲線是一條下降相對(duì)緩慢的曲線，這使得度很大的節(jié)點(diǎn)可以在網(wǎng)絡(luò)中存在。對(duì)于隨機(jī)網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)，度分布區(qū)間非常狹窄，幾乎找不到偏離節(jié)點(diǎn)度均值較大的點(diǎn)，故其平均度可以被看作其節(jié)點(diǎn)度的一個(gè)特征標(biāo)度。在這個(gè)意義上，我們把節(jié)點(diǎn)度服從冪律分布的網(wǎng)絡(luò)叫做無標(biāo)度網(wǎng)絡(luò)無標(biāo)度網(wǎng)絡(luò)3復(fù)雜網(wǎng)絡(luò)模型1999年,Albert-LászlóBarabási和RékaAlber受WWW形成的啟發(fā),提出了構(gòu)造無標(biāo)度網(wǎng)絡(luò)的演化模型，常稱為BA模型。該模型考慮了現(xiàn)實(shí)網(wǎng)絡(luò)的兩個(gè)重要特性：增長(zhǎng)特性和擇優(yōu)連接特性。該模型的構(gòu)成過程如下：初始時(shí)刻有m0個(gè)孤立的節(jié)點(diǎn),在每一個(gè)時(shí)間步t=1,2,3,…,n-m0

加上一個(gè)新的節(jié)點(diǎn)j，同時(shí)加上從此節(jié)點(diǎn)出發(fā)的m條邊,將新節(jié)點(diǎn)j連接到網(wǎng)絡(luò)中已經(jīng)存在的節(jié)點(diǎn)，i是按照正比于i的度的規(guī)律來選擇邊的另一端節(jié)點(diǎn)：BA模型3復(fù)雜網(wǎng)絡(luò)模型BA無標(biāo)度網(wǎng)絡(luò)的聚類系數(shù)為：可見，BA無標(biāo)度網(wǎng)絡(luò)不具有高的聚類系數(shù)。BA無標(biāo)度網(wǎng)絡(luò)具有小世界特性，其平均路徑長(zhǎng)度為：BA模型3復(fù)雜網(wǎng)絡(luò)模型總結(jié)復(fù)雜網(wǎng)絡(luò)作為一門新興的交叉學(xué)科正處于蓬勃發(fā)展階段，為各學(xué)科中的復(fù)雜系統(tǒng)提供了一種對(duì)其進(jìn)行認(rèn)識(shí)和處理的統(tǒng)一的框架，同時(shí)為處理包括計(jì)算機(jī)科學(xué)在內(nèi)的許多學(xué)科中的復(fù)雜問題提供了新的觀點(diǎn)和方法。

加入復(fù)雜網(wǎng)絡(luò)研究的學(xué)者主要來自圖論、統(tǒng)計(jì)物理學(xué)、計(jì)算機(jī)網(wǎng)絡(luò)研究、生態(tài)學(xué)、社會(huì)學(xué)以及經(jīng)濟(jì)學(xué)等領(lǐng)域，研究所涉及的網(wǎng)絡(luò)主要有：生命科學(xué)領(lǐng)域的各種網(wǎng)絡(luò)（如細(xì)胞網(wǎng)絡(luò)、蛋白質(zhì)－蛋白質(zhì)作用網(wǎng)絡(luò)、蛋白質(zhì)折疊網(wǎng)絡(luò)、神經(jīng)網(wǎng)絡(luò)、生態(tài)網(wǎng)絡(luò)）、Internet/WWW網(wǎng)絡(luò)、社會(huì)網(wǎng)絡(luò)，包括流行性疾病的傳播網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)、