網路科學

研究複雜網絡(如電腦網絡、社會關係網絡)

網路科學是從交叉學科研究成長起來的一個新興的學術領域[1][2]。致力於研究複雜網路的性質,並且應用這些性質去研究一些具有網路特點的領域,比如資訊科技網路,電腦網路,生物圈網路,學習和認知網路,社會關係網路以及經濟和金融網路。這個領域以數學中的圖論為理論基礎,從物理中的統計力學,電腦科學中的資料探勘資訊視覺化,統計學中的推斷建模,以及社會學和經濟學中的社會結構理論等學科和分之中汲取方法論營養。美國國家科研委員會(National Research Council)將網路科學定義為「研究物理,生物,和社會現象的網路化表達,建立針對這些象限具有預測效果的模型」的學科[3][4]

網路的性質

網路的節點及其之間的連接,常建模成圖論的頂點和邊。此時,可以計算圖的某些參數,來分析網路的對應性質。該些網路性質在定義各種網路模型英語network model時會用到,或是可用作比較不同模型的異同。除下列外,網路科學亦有採用其他圖論術語來描述網路的性質。

大小

網路的大小是以其節點數 衡量,又或是其邊數 。對於無重邊的連通網路,邊數介乎 )和某個最大值 。對於簡單圖(網路的每對頂點之間至多衹有一條無向邊,且頂點不會與自己連邊),有 ;對於(也不允許頂點與自己連邊的)有向圖,則是 ;對於允許與自己連邊的有向圖,最大值是 。若允許一對頂點之間有多條不同連接,則總邊數沒有上限。

密度

密度 將網路的邊數 ,化成介乎  的數值衡量。其為網路含有的「非必須」邊數,相比全部可能的非必須邊數,兩者的百分比,即

 

其中  分別是上一小節中, 個節點的連通網路,其邊數的最小和最大可能值。對於簡單圖,將  代入得

 

另一條公式是 ,其中 是單向連結的數目(Wasserman & Faust 1994)。[5]

網路直徑

 
彼得森圖,直徑2

網路中的任意一對節點,可以找出兩者之間的最短線路。所有此種最短線路之中,最長的長度就稱為網路的直徑。換言之,直徑是網路上最遠兩點的最短距離。[6]舉例,附圖所示的網路,其直徑為2,因為自任一點至另一點,衹需兩步連接。

各種模型

現實中,常會遇到複雜的網路,而數學模型是分析該些網路的基本工具。不同的隨機圖模型生成出不同的網路結構,用於與現實網路作比較。

艾狄胥-雷尼隨機圖

 
 個節點生成的ER模型。給定 個頂點,為每對頂點獨立地選取一個  之間的均勻隨機數,與某個固定的概率 作比較。若隨機數小於 ,則兩點之間連邊。

艾狄胥-雷尼模型(英語:Erdős–Rényi model)得名自兩位匈牙利數學家艾狄胥·帕爾雷尼·奧爾弗雷德英語Alfréd Rényi,此模型生成的隨機圖中,每對頂點之間皆各自獨立地以某固定概率 連邊。圖論的概率法英語probabilistic method常用此模型證明存在具某種性質的圖,並用作明確定義何謂「幾乎所有」圖皆具某種性質。

ER隨機圖 的參數 表示頂點數,而 則是任意兩頂點之間連邊的概率。此模型中,各個頂點的地位相同,沒有偏重,每個頂點的遵循二項分佈,對於任意頂點 ,度數為 的概率是:

 

瓦茨-斯特羅加茨模型

 
瓦茨-斯特羅加茨模型生成網路時,用到「重連」(rewiring)。模型始於規律的柵格結構,然後其每條邊有一個固定的概率發生重連,改變連接的頂點。圖示的平均度為 

瓦茨-斯特羅加茨模型Watts–Strogatz model)產生的隨機圖滿足小世界性質英語small-world properties

初始時,將網路的節點排成一圈,每個節點與最近 個節點相連,另一個參數是重連的概率 ,前述的每條邊以此概率發生重連,變成一條新的邊,保持一端不變,另一端則改為隨機一個頂點(但保持沒有兩點重複連邊)。重連次數期望值為 

因為始於規則的網路,若重連少(即 小),則集聚系數高,平均路徑亦長。隨 增加,每次重連皆可能產生不同集聚之間的捷徑,所以集聚系數和平均路徑長度皆會下降。但是,後者降得更快,所以在某時刻,會出現集聚系數大而平均路徑短的網路,此為「小世界網路」的特性。[7] 較大時,多數邊皆被重連,所得網路與完全隨機的網路差異不大。

分支領域

資訊科技網路

網際網路

生物圈網路

生物神經網路

電腦網路

類神經網路

經濟網路

人際關係網路幫助決定了人們所選擇的職業生涯,人們所找到的工作,他們買的商品,以及他們如何投票。社會網路決定著我們生活中的諸多方面。因此,社會網路是如何影響我們的行為,在一個社會中出現什麼樣的網路結構以及它們出現的概率有多大,以及我們為什麼像現在這樣安排我們自己的生活,就成為了值得研究的問題,也是許多社會科學研究中的關鍵因素[8]

參考

參考文獻

  1. ^ 方錦清,汪小帆,等. 一門嶄新的交叉科學:網路科學(上)頁面存檔備份,存於網際網路檔案館). 物理學進展. 2007.
  2. ^ Duncan J. Watts. THE “NEW” SCIENCE OF NETWORKS (PDF). Annual Review of Sociology. 2004年 [2014-07-06]. (原始內容 (PDF)存檔於2014-07-14) (英語). 
  3. ^ Committee on Network Science for Future Army Applications. Network Science. National Research Council. 2006 [2014-07-06]. ISBN 0309653886. (原始內容存檔於2008-07-05). 
  4. ^ Ted G. Lewis. Network Science: Theory and Applications. Wiley. 2009 [2014-07-06]. ISBN 0470331887. (原始內容存檔於2016-12-28). 
  5. ^ Gockel, C.; Werth, L. Measuring and modeling shared leadership: Traditional approaches and new ideas. Journal of Personnel Psychology. 2010, 9 (4): 172–180. doi:10.1027/1866-5888/a000023. 
  6. ^ Weisstein, Eric W. (編). Graph Diameter. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. (英語). 
  7. ^ 汪小帆; 李翔; 陳關榮. 复杂网络理论及其应用. 清華大學出版社. 2006: 22. ISBN 9787302125051. 
  8. ^ Matthew O. Jackson. Social and Economic Networks. Princeton University Press. 2010 [2014-07-06]. ISBN 0691148201. (原始內容存檔於2014-07-22).