1、復雜網絡Complex Network,計算機學院,目錄,,,1 引言,2復雜網絡的統(tǒng)計特性,3 復雜網絡模型,本文目錄結構,4 總結,引言,自然界中存在的大量復雜系統(tǒng)都可以通過形形色色的網絡加以描述。一個典型的網絡是由許多節(jié)點與連接兩個節(jié)點之間的一些邊組成的, 其中節(jié)點用來代表真實系統(tǒng)中不同的個體, 而邊則用來表示個體之間的關系, 通常是當兩個節(jié)點之間具有某種特定的關系時連一條邊, 反之則不連邊。有邊相連的兩個節(jié)點在網絡中被看作是相鄰

2、的。。,1引言,復雜網絡的發(fā)展背景,例如, 神經系統(tǒng)可以看作是大量神經細胞通過神經纖維相互連接形成的網絡；計算機網絡可以看作是自主工作的計算機通過通信介質如光纜、雙絞線、同軸電纜等相互連接形成的網絡。類似的還有電力網絡、社會關系網絡、交通網絡等等。,1引言,神經網絡,計算機網絡,數學家和物理學家在考慮網絡的時候, 往往只關心節(jié)點之間有沒有邊相連, 至于節(jié)點在什么位置, 邊長還是短, 是彎曲還是平直, 有沒有相交等等都是他們不在意的。因此

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

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

5、這樣的一些網絡被科學家們叫做復雜網絡（Complex Network)，對于它們的研究標志著第三階段的到來。,1引言,大規(guī)模復雜網絡,1引言,復雜網絡的定義,具有自組織、自相似、吸引子、小世界、無標度中部分或全部性質的網絡稱為復雜網絡?！X學森,統(tǒng)計特性,,,2復雜網絡的統(tǒng)計特性,,,,,,3 聚類系數,4 社區(qū)結構,5 層次性,2復雜網絡的統(tǒng)計特性,度、度分布和度相關性,無向網絡的節(jié)點的度是指與節(jié)點連接的邊數；而有向網絡的節(jié)點的度分

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

7、型中, 任意兩個節(jié)點間相連的概率為p, 即任意節(jié)點連接到任意的其它節(jié)點的概率都是相同的. 但在許多現(xiàn)實網絡中, 存在著一定的混合模式，即一個節(jié)點傾向于連接到某一些節(jié)點。研究者也發(fā)現(xiàn)，許多網絡邊的兩節(jié)點間的度也存在依賴關系, 即度-度相關性。 如果度高的節(jié)點傾向于連接其它度高的節(jié)點, 稱為同配混合；如果度高的節(jié)點傾向于連接其它度低的節(jié)點稱為異配混合。網絡的同配性(異配性)影響網絡的結構和行為. 按照度同配混合的網絡比對應

8、的異配網絡更利于滲流；對于節(jié)點刪除, 同配混合的網絡要比異配和中性的網絡更具有魯棒性.,2復雜網絡的統(tǒng)計特性,最短路徑長度、平均最短路徑長度、介數,對于無權網絡, 網絡中任意兩點間的最短路徑是從一個節(jié)點到另一個節(jié)點的最少邊數；對于有權網絡, 兩點間的最短路徑是指權值之和為最小的路徑。網絡中任意兩個節(jié)點之間的最短路徑長度的最大值稱為網絡的直徑。平均最短路徑長度是網絡中所有節(jié)點對之間的最短路徑長度的平均值。

9、 平均路徑長度可以做為網絡信息傳遞效率的度量, 網絡的效率定義為：這里, n表示節(jié)點數，dij為兩個節(jié)點i和j之間的最短路徑長度。網絡的平均最短路徑長度較小的現(xiàn)象稱為小世界效應。許多現(xiàn)實網絡具有小世界效應，如電影演員網絡( 平均最短路徑為3.48)，對等網絡(平均最短路徑為4.28)，代謝網絡(平均最短路徑是2.56).,2復雜網絡的統(tǒng)計特性,最短路徑長度、平均最短路徑長度、介數,為了度量節(jié)點在網絡中的重要性——中心性，引

10、進了節(jié)點介數概念，定義如下：邊介數是經過這條邊的節(jié)點對的最短路徑數，它在社區(qū)發(fā)現(xiàn)中為區(qū)分一個社區(qū)的內部邊和社區(qū)之間的邊提供了一種有效的度量標準.,2復雜網絡的統(tǒng)計特性,聚類系數,二元關系R, 如果aRb, bRc, 那么aRc, 則稱R是傳遞的。熟人網絡中，也有類似的特性，即擁有一個共同朋友的兩個人他們也彼此熟悉，這種性質稱為網絡的聚類性，也稱為傳遞性。傳遞性意味著出現(xiàn)三角形，定義節(jié)點i 聚類系數如下：整個網絡的聚

11、類系數C就是所有節(jié)點i的聚類系數C i的平均值, 且有0≤ C≤ 1。 對于一些無標度網絡, 局部聚類系數Ci 隨著節(jié)點i的度下降而下降。隨機網絡的聚類系數為O(n‐¹) ，當網絡規(guī)模極大時趨于零，而多數現(xiàn)實網絡的聚類系數顯著大于零，a即具有明顯的聚類特性。,-,2復雜網絡的統(tǒng)計特性,社區(qū)結構,社區(qū)結構是許多現(xiàn)實網絡具有的一個共同的特征, 即網絡的節(jié)點可以分成幾個組, 每個組內部的節(jié)點連接稠密, 而組之間的節(jié)

12、點連接稀疏，下圖是一個包含三個社區(qū)的一個簡單網絡。 社區(qū)結構的發(fā)現(xiàn)具有重要的意義，例如在WWW 中的社區(qū)對應著一組關于某個主題的網頁；社會網絡中的社區(qū)對應著有著共同愛好或背景的一群人；生化網絡中的社區(qū)則對應著某個復合體或某種功能。因此，社區(qū)發(fā)現(xiàn)是當前復雜網絡研究的一個熱點方向，并且已經提出了各種方法，如基于介數度量的方法、隨機游走方法、電阻網絡方法、拉普拉斯特征值方法、極值優(yōu)化方法、派系過濾算法等。,2復雜

13、網絡的統(tǒng)計特性,社區(qū)結構,一個廣泛使用的度量網絡的社區(qū)結構的量是模塊度，它定義為：設網絡分為n個社區(qū)，則定義一個n * n的矩陣e，每一行和每一列都代表一個社區(qū)，矩陣元素eij表示社區(qū)i和j間的邊數占網絡總邊數的比例，eii就表示社區(qū)i內部邊所占的比例，ai =∑eij表示第i行或第i列元素之和, 即與第i個社區(qū)的節(jié)點相連的邊的總比例, 則模塊度定義為:即社區(qū)內部邊的比例減去具有同樣社區(qū)劃分但節(jié)點間是隨機連接的網絡的這一值的期

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

15、 Clauset等人建立了一種層次隨機圖模型，利用該模型對現(xiàn)實網絡進行擬合，發(fā)現(xiàn)網絡的層次結構可以解釋網絡的許多其它特征，如平均度、聚類系數和最短路徑等。發(fā)現(xiàn)網絡中的連接往往需要在實驗室或現(xiàn)場付出高昂的費用，這就使得許多現(xiàn)實網絡是不完備的， 在這種情形下預測網絡中丟失的連接具有重要的意義。Clauset進一步利用建立的模型設計了一個丟失連接的預測器，它與傳統(tǒng)的方法相比, 能夠應用于更廣泛類型的網絡結構。,復雜網絡模型,,3復雜網絡模

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

17、共同研究的ER模型。ER模型是指在給定 n 個頂點后，規(guī)定每兩個頂點之間都以 p 的概率連起來（0 ≤ p ≤ 1），而且這些判定之間兩兩無關。這樣得到的隨機圖一般記作 或 ERn(p)。,3復雜網絡模型,隨機圖,許多現(xiàn)實網絡如技術網絡、生物網絡和社會網絡等，既不是完全規(guī)則的，也不是完全隨機的，而是介于兩者之間。Watts和Strogatz基于這些觀察, 提出了WS模型，是指對一個具有n個節(jié)點的環(huán)格，初始時每個節(jié)點有k個鄰居，將

18、每條邊以概率p進行隨機重繞的過程。由于該模型生成的網絡具有較短的特征路徑，即網絡具有小世界效應，故稱為小世界網絡，WS模型也因此常稱為小世界網絡(模型)。,,,小世界網絡,3復雜網絡模型,上述的構造過程有可能破壞網絡的連通，因此Newman和Watts稍后提出了通過隨機化加邊的方法構造小世界網絡的模型，即NW 模型。還有許多改進的模型：加點、加邊、去點、去邊以及不同形式的交叉，產生多種形式的小世界模型。 小世界網絡具有高

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

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

21、A模型。該模型考慮了現(xiàn)實網絡的兩個重要特性：增長特性和擇優(yōu)連接特性。該模型的構成過程如下： 初始時刻有m0個孤立的節(jié)點, 在每一個時間步t= 1,2,3, …, n-m0 加上一個新的節(jié)點j，同時加上從此節(jié)點出發(fā)的m條邊, 將新節(jié)點j連接到網絡中已經存在的節(jié)點，i是按照正比于i的度的規(guī)律來選擇邊的另一端節(jié)點：,,,BA模型,3復雜網絡模型,BA無標度網絡的聚類系數為：可見，BA無標度網絡不具有高的聚類系數。

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

23、種網絡（如細胞網絡、蛋白質－蛋白質作用網絡、蛋白質折疊網絡、神經網絡、生態(tài)網絡）、Internet/WWW網絡、社會網絡，包括流行性疾病的傳播網絡、科學家合作網絡、人類性關系網絡、語言學網絡等等；所使用的主要方法是數學上的圖論、物理學中的統(tǒng)計物理學方法和社會網絡分析方法。,,,,,4總結,參考文獻：[1]劉濤，陳忠，陳曉榮。復雜網絡理論及其應用研究概述。上海交通大學安泰管理學院，上海 200030)[2]詹衛(wèi)華, 關佶紅, 章忠志