1、復(fù)雜網(wǎng)絡(luò)Complex Network,計算機學院,目錄,,,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)系, 通常是當兩個節(jié)點之間具有某種特定的關(guān)系時連一條邊, 反之則不連邊。有邊相連的兩個節(jié)點在網(wǎng)絡(luò)中被看作是相鄰

2、的。。,1引言,復(fù)雜網(wǎng)絡(luò)的發(fā)展背景,例如, 神經(jīng)系統(tǒng)可以看作是大量神經(jīng)細胞通過神經(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ù)學家和物理學家在考慮網(wǎng)絡(luò)的時候, 往往只關(guān)心節(jié)點之間有沒有邊相連, 至于節(jié)點在什么位置, 邊長還是短, 是彎曲還是平直, 有沒有相交等等都是他們不在意的。因此

3、, 我們把網(wǎng)絡(luò)不依賴于節(jié)點的具體位置和邊的具體形態(tài)就能表現(xiàn)出來的性質(zhì)叫做網(wǎng)絡(luò)的拓撲性質(zhì), 相應(yīng)的結(jié)構(gòu)叫做網(wǎng)絡(luò)的拓撲結(jié)構(gòu). 那么, 什么樣的拓撲結(jié)構(gòu)比較適用于描述真實的系統(tǒng)呢?,1引言,兩百多年來, 對這個問題的研究經(jīng)歷了三個階段。在最初的一百多年里, 科學家們認為真實系統(tǒng)各因素之間的關(guān)系可以用一些規(guī)則的結(jié)構(gòu)表示, 例如二維平面上的歐幾里德格網(wǎng), 它看起來像是格子體恤衫上的花紋; 又如最近鄰環(huán)網(wǎng), 它總是會讓你想到一群手牽著手、圍著篝火跳

4、圓圈舞的姑娘.,1引言,到了20 世紀50 年代末, 數(shù)學家們想出了一種新的構(gòu)造網(wǎng)絡(luò)的方法, 在這種方法下, 兩個節(jié)點之間連邊與否不再是確定的事情, 而是根據(jù)一個概率決定. 數(shù)學家把這樣生成的網(wǎng)絡(luò)叫做隨機網(wǎng)絡(luò), 它在接下來的40 年里一直被很多科學家認為是描述真實系統(tǒng)最適宜的網(wǎng)絡(luò).,直到最近幾年，由于計算機數(shù)據(jù)處理和運算能力的飛速發(fā)展, 科學家們發(fā)現(xiàn)大量的真實網(wǎng)絡(luò)既不是規(guī)則網(wǎng)絡(luò)，也不是隨機網(wǎng)絡(luò), 而是具有與前兩者皆不同的統(tǒng)計特征的網(wǎng)絡(luò)。

5、這樣的一些網(wǎng)絡(luò)被科學家們叫做復(fù)雜網(wǎng)絡(luò)（Complex Network)，對于它們的研究標志著第三階段的到來。,1引言,大規(guī)模復(fù)雜網(wǎng)絡(luò),1引言,復(fù)雜網(wǎng)絡(luò)的定義,具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質(zhì)的網(wǎng)絡(luò)稱為復(fù)雜網(wǎng)絡(luò)?！X學森,統(tǒng)計特性,,,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é)點的度分

6、為入度和出度。網(wǎng)絡(luò)中所有節(jié)點度的列表稱為度序列，度序列的平均值稱為網(wǎng)絡(luò)的平均度, 記為。給定了網(wǎng)絡(luò)的度序列就確定了該網(wǎng)絡(luò)的度分布。度分布是指從圖中隨機選擇一個節(jié)點其度為k的概率，記為P(k)。度分布是網(wǎng)絡(luò)的最基本的拓撲特性。根據(jù)度分布，可以將網(wǎng)絡(luò)分為隨機圖、無標度網(wǎng)絡(luò)和指數(shù)網(wǎng)絡(luò)等。度分布一個非常有用的表示( 生成函數(shù)表示法)為:其中pk 表示度為k的節(jié)點在網(wǎng)絡(luò)中的比例.,2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計特性,度、度分布和度相關(guān)性,在隨機圖模

7、型中, 任意兩個節(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)

8、的異配網(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é)點對之間的最短路徑長度的平均值。

9、 平均路徑長度可以做為網(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ò)中的重要性——中心性，引

10、進了節(jié)點介數(shù)概念，定義如下：邊介數(shù)是經(jīng)過這條邊的節(jié)點對的最短路徑數(shù)，它在社區(qū)發(fā)現(xiàn)中為區(qū)分一個社區(qū)的內(nèi)部邊和社區(qū)之間的邊提供了一種有效的度量標準.,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ò)的聚

11、類系數(shù)C就是所有節(jié)點i的聚類系數(shù)C i的平均值, 且有0≤ C≤ 1。 對于一些無標度網(wǎng)絡(luò), 局部聚類系數(shù)Ci 隨著節(jié)點i的度下降而下降。隨機網(wǎng)絡(luò)的聚類系數(shù)為O(n‐¹) ，當網(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é)

12、點連接稀疏，下圖是一個包含三個社區(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)是當前復(fù)雜網(wǎng)絡(luò)研究的一個熱點方向，并且已經(jīng)提出了各種方法，如基于介數(shù)度量的方法、隨機游走方法、電阻網(wǎng)絡(luò)方法、拉普拉斯特征值方法、極值優(yōu)化方法、派系過濾算法等。,2復(fù)雜

13、網(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ò)的這一值的期

14、望。Q的值在-1與1之間，Q 越接近1( 這是最大值)預(yù)示著具有越強的社區(qū)結(jié)構(gòu)。,2復(fù)雜網(wǎng)絡(luò)的統(tǒng)計特性,層次性,按層次組織是許多復(fù)雜系統(tǒng)的一個共同特征。在代謝網(wǎng)絡(luò)中，有許多小的連接密集的簇，它們會相互結(jié)合形成較大較稀疏的簇，而這些簇又可能進一步形成更大更稀疏的簇。這種自相似地嵌套形成了我們現(xiàn)實網(wǎng)絡(luò)的嚴格而又精細的結(jié)構(gòu)。有趣地是，網(wǎng)絡(luò)的層次性特性, 可以通過簡單的量來捕獲，即C ( k)曲線滿足C(K)~ k﹣¹。

15、 Clauset等人建立了一種層次隨機圖模型，利用該模型對現(xiàn)實網(wǎng)絡(luò)進行擬合，發(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進一步利用建立的模型設(shè)計了一個丟失連接的預(yù)測器，它與傳統(tǒng)的方法相比, 能夠應(yīng)用于更廣泛類型的網(wǎng)絡(luò)結(jié)構(gòu)。,復(fù)雜網(wǎng)絡(luò)模型,,3復(fù)雜網(wǎng)絡(luò)模

16、型,,,隨機圖是圖論中最年輕的分支之一，對它的系統(tǒng)研究起源于1959年保羅·埃爾德什和阿爾弗雷德·雷尼的工作，他們發(fā)表了一系列的論文，建立了豐富的隨機圖理論的基礎(chǔ)?，F(xiàn)實網(wǎng)絡(luò)具有復(fù)雜的拓撲結(jié)構(gòu)和未知的組織原理，總是呈獻出某種隨機性，因此用隨機圖作為網(wǎng)絡(luò)的模型是最直接的一種選擇。,一個隨機圖實際上是將給定的頂點之間隨機地連上邊。邊的產(chǎn)生可以依賴于不同的隨機方式，這樣就產(chǎn)生了不同的隨機圖模型。一個典型的模型是埃爾德什和雷尼

17、共同研究的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個鄰居，將

18、每條邊以概率p進行隨機重繞的過程。由于該模型生成的網(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 模型。還有許多改進的模型：加點、加邊、去點、去邊以及不同形式的交叉，產(chǎn)生多種形式的小世界模型。 小世界網(wǎng)絡(luò)具有高

19、的聚類系數(shù)，WS小世界網(wǎng)絡(luò)的聚類系數(shù)為：而NW小世界網(wǎng)絡(luò)的聚類系數(shù)為： 小世界網(wǎng)絡(luò)的典型特征是平均最短路徑滿足對數(shù)標度，但是到目前為止還沒有精確的解析表達式。小世界網(wǎng)絡(luò)的度分布與多數(shù)現(xiàn)實網(wǎng)絡(luò)并不能很好匹配，對于NW模型和WS模型，其表達式都比較復(fù)雜。,,,小世界網(wǎng)絡(luò),3復(fù)雜網(wǎng)絡(luò)模型,節(jié)點度服從冪律分布，是指具有某個特定度的節(jié)點數(shù)目與這個特定的度之間的關(guān)系可以用一個冪函數(shù)近似地表示，冪函數(shù)曲線是一條下降相對緩慢的曲

20、線，這使得度很大的節(jié)點可以在網(wǎng)絡(luò)中存在。對于隨機網(wǎng)絡(luò)和規(guī)則網(wǎng)絡(luò)，度分布區(qū)間非常狹窄，幾乎找不到偏離節(jié)點度均值較大的點，故其平均度可以被看作其節(jié)點度的一個特征標度。在這個意義上，我們把節(jié)點度服從冪律分布的網(wǎng)絡(luò)叫做無標度網(wǎng)絡(luò),,,無標度網(wǎng)絡(luò),3復(fù)雜網(wǎng)絡(luò)模型,1999年, Albert-László Barabási 和Réka Alber受WWW 形成的啟發(fā), 提出了構(gòu)造無標度網(wǎng)絡(luò)的演化模型，常稱為B

21、A模型。該模型考慮了現(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無標度網(wǎng)絡(luò)的聚類系數(shù)為：可見，BA無標度網(wǎng)絡(luò)不具有高的聚類系數(shù)。

22、 BA無標度網(wǎng)絡(luò)具有小世界特性，其平均路徑長度為：,,,BA模型,3復(fù)雜網(wǎng)絡(luò)模型,總結(jié),復(fù)雜網(wǎng)絡(luò)作為一門新興的交叉學科正處于蓬勃發(fā)展階段，為各學科中的復(fù)雜系統(tǒng)提供了一種對其進行認識和處理的統(tǒng)一的框架，同時為處理包括計算機科學在內(nèi)的許多學科中的復(fù)雜問題提供了新的觀點和方法。 加入復(fù)雜網(wǎng)絡(luò)研究的學者主要來自圖論、統(tǒng)計物理學、計算機網(wǎng)絡(luò)研究、生態(tài)學、社會學以及經(jīng)濟學等領(lǐng)域，研究所涉及的網(wǎng)絡(luò)主要有：生命科學領(lǐng)域的各

23、種網(wǎng)絡(luò)（如細胞網(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ò)、科學家合作網(wǎng)絡(luò)、人類性關(guān)系網(wǎng)絡(luò)、語言學網(wǎng)絡(luò)等等；所使用的主要方法是數(shù)學上的圖論、物理學中的統(tǒng)計物理學方法和社會網(wǎng)絡(luò)分析方法。,,,,,4總結(jié),參考文獻：[1]劉濤，陳忠，陳曉榮。復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用研究概述。上海交通大學安泰管理學院，上海 200030)[2]詹衛(wèi)華, 關(guān)佶紅, 章忠志