復(fù)雜網(wǎng)絡(luò)簡介

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

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

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

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

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

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

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

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

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

加入復(fù)雜網(wǎng)絡(luò)研究的學(xué)者主要來自圖論、統(tǒng)計物理學(xué)、計算機網(wǎng)絡(luò)研究、生態(tài)學(xué)、社會學(xué)以及經(jīng)濟學(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ò)、社會網(wǎng)絡(luò)，包括流行性疾病的傳播網(wǎng)絡(luò)、科學(xué)家合作網(wǎng)絡(luò)、