跳至內容

複雜網絡

維基百科,自由的百科全書
隨機生成的BA模型複雜網絡。

網絡理論的研究中,複雜網絡是由數量巨大的節點和節點之間錯綜複雜的關係共同構成的網絡結構。用數學的語言來說,就是一個有着足夠複雜的拓撲結構特徵的。複雜網絡具有簡單網絡,如晶格網絡隨機圖等結構所不具備的特性,而這些特性往往出現在真實世界的網絡結構中。複雜網絡的研究是現今科學研究中的一個熱點,與現實中各類高複雜性系統,如的互聯網神經網絡社會網絡的研究有密切關係。

定義

[編輯]

無論在社會科學生命科學還是信息科學中,都存在着擁有十分複雜的拓撲結構特徵的網絡結構。這種網絡結構的形式既不是完全規則,也不是完全隨機的,例如在度分佈中出現肥尾現象,高集聚係數,邊與邊之間的相稱性或非相稱性,社團結構分級結構(hierarchy structure)等等。在有向圖網絡中,還會出現相互性,三角顯著性等其它方面的特徵。然而,複雜網絡的概念出現以前的數學網絡模型並沒有具備這樣的特性。

最著名也是最常被研究的兩類複雜網絡模型是小世界網絡無尺度網絡,它們也是最為經典的兩類複雜網絡模型。前者的特性是短特徵路徑長度與高集聚係數,後者的特性則是度分佈冪定律遞減。此外,隨着複雜網絡研究的不斷深化與廣泛,各種具有其他特性的複雜網絡模型也開始受到注意。

小世界網絡

[編輯]

小世界網絡,又稱為小世界效應,是複雜網絡的特性之一。1998年,美國康奈爾大學理論與應用力學系博士生華茲(Watts)與其導師斯特羅迦茨(Strogatz)合作,在《自然》雜誌上發表了題為《「小世界」網絡的集體動力學》的論文,標誌着小世界網絡模型的建立[1]

小世界網絡的判定準則有兩個,分別是特徵路徑長度短,和高集聚係數。網絡的特徵路徑長度是指在它的圖表示中,兩個節點的路徑長度的平均值(這裏路徑長度指兩節點間最短路徑的長度)。許多複雜網絡儘管節點數目巨大,但節點之間的特徵路徑長度則非常小[2]。集聚係數則是用來描述「抱團」現象的,也就是「你朋友之間相互認識的程度」。數學上來說,一個節點的集聚係數等於與它相連的節點中相互連接的點對數與總點對數的比值。高集聚係數實際上保證了較小的特徵路徑長度[3]

無尺度網絡

[編輯]
無尺度網絡與隨機網絡的對比:(a)中的隨機網絡,大部分節點都連出2到3條邊,0條與1條邊的和4條邊的都很少,而(b)中的無尺度網絡,大部分節點連1條邊,少數節點(紅色)連有大量邊。

1999年,Barabási與Albert的研究揭示出則複雜網絡的無尺度特性[1]。無尺度特性,或者叫無標度特性,是指網絡的度分佈滿足冪律分佈。所謂一個網絡的度分佈,是當隨機地從網絡中抽取一個節點時,與這個節點相連的節點數(叫做這個節點的度)d的概率分佈。比如說對一個n個節點組成的完全圖(所有節點之間都連有邊的圖),度分佈是:d = n - 1的概率是1,其餘的都是0。無尺度網絡的度分佈滿足冪律分佈,也就是說d = k的概率正比k的某個冪次(一般是負的):

冪律分佈這一特性,正說明了無尺度網絡的度分佈與一般隨機網絡的不同。隨機網絡的度分佈屬於正態分佈,因此有一個特徵度數,即大部分節點的度數都接近它。無尺度網絡的度分佈是呈集散分佈:大部分的節點只有比較少的連接,而少數節點有大量的連接。由於不存在特徵度數,因此得名「無尺度」。

現實生活中,無尺度網絡的例子有很多。互聯網、美國演員網絡、細胞中蛋白質的交互網絡都是無尺度網絡。無尺度網絡的特性是:當節點意外失效或改變時,對網絡的影響一般很小,只有很小的概率會發生大的影響,但當有集散節點受到影響時,網絡受到的影響會比隨機網絡大得多[4]

參見

[編輯]

參考來源

[編輯]
  1. ^ 1.0 1.1 《複雜網絡理論及其應用》,第8頁
  2. ^ 《複雜網絡理論及其應用》,第10頁
  3. ^ Ajith Abraham, Aboul Ella Hassanien, Václav Snášel. Computational Social Network Analysis: Trends, Tools and Research Advances. Springer. 2009. ISBN 1848822286. 第205頁.
  4. ^ 《科學美國人》中文版2003年7月. 无尺度网络. 集智集團. [2011-07-04]. (原始內容存檔於2012-01-11). 
  • 汪小帆,李翔,陳關榮. 《复杂网络理论及其应用》. 清華大學出版社. 2006. ISBN 9787302125051.