网络科学

网络科学是从交叉学科研究成长起来的一个新兴的学术领域^[1][2]。致力于研究复杂网络的性质，并且应用这些性质去研究一些具有网络特点的领域，比如信息技术网络，计算机网络，生物圈网络，学习和认知网络，社会关系网络以及经济和金融网络。这个领域以数学中的图论为理论基础，从物理中的统计力学，计算机科学中的数据挖掘和信息可视化，统计学中的推断建模，以及社会学和经济学中的社会结构理论等学科和分之中汲取方法论营养。美国国家科研委员会（National Research Council）将网络科学定义为“研究物理，生物，和社会现象的网络化表达，建立针对这些象限具有预测效果的模型”的学科^[3][4]。

網絡的性質

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

大小

網絡的大小是以其節點數${\displaystyle N}$ 衡量，又或是其邊數${\displaystyle E}$ 。對於無重邊的連通網絡，邊數介乎${\displaystyle N-1}$ （樹）和某個最大值${\displaystyle E_{\max }}$ 。對於簡單圖（網絡的每對頂點之間至多衹有一條無向邊，且頂點不會與自己連邊），有${\displaystyle E_{\max }={\tbinom {N}{2}}=N(N-1)/2}$ ；對於（也不允許頂點與自己連邊的）有向圖，則是${\displaystyle E_{\max }=N(N-1)}$ ；對於允許與自己連邊的有向圖，最大值是${\displaystyle E_{\max }=N^{2}}$ 。若允許一對頂點之間有多條不同連接，則總邊數沒有上限。

密度

密度${\displaystyle D}$ 將網絡的邊數${\displaystyle E}$ ，化成介乎${\displaystyle 0}$ 至${\displaystyle 1}$ 的數值衡量。其為網絡含有的「非必須」邊數，相比全部可能的非必須邊數，兩者的百分比，即

${\displaystyle D={\frac {E-E_{\mathrm {min} }}{E_{\mathrm {max} }-E_{\mathrm {min} }}}}$ 

其中${\displaystyle E_{\mathrm {min} }}$ 和${\displaystyle E_{\mathrm {max} }}$ 分別是上一小節中，${\displaystyle N}$ 個節點的連通網絡，其邊數的最小和最大可能值。對於簡單圖，將${\displaystyle E_{\mathrm {max} }={\tbinom {N}{2}}}$ 和${\displaystyle E_{\mathrm {min} }=N-1}$ 代入得

${\displaystyle D={\frac {E-(N-1)}{E_{\mathrm {max} }-(N-1)}}={\frac {2(E-N+1)}{N(N-3)+2}}.}$ 

另一條公式是${\displaystyle D={\frac {T-2N+2}{N(N-3)+2}}}$ ，其中${\displaystyle T}$ 是單向連結的數目（Wasserman & Faust 1994）。^[5]

網絡直徑

 

彼得森圖，直徑2

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

各種模型

現實中，常會遇到複雜的網絡，而數學模型是分析該些網絡的基本工具。不同的随机图模型生成出不同的網絡結構，用於與現實網絡作比較。

艾狄胥-雷尼隨機圖

主条目：ER随机图

 

以${\displaystyle N=4}$ 個節點生成的ER模型。給定${\displaystyle N}$ 個頂點，為每對頂點獨立地選取一個${\displaystyle 0}$ 至${\displaystyle 1}$ 之間的均勻隨機數，與某個固定的概率${\displaystyle p}$ 作比較。若隨機數小於${\displaystyle p}$ ，則兩點之間連邊。

艾狄胥-雷尼模型（英語：Erdős–Rényi model）得名自兩位匈牙利數學家艾狄胥·帕爾和雷尼·奥爾弗雷德（英语：Alfréd Rényi），此模型生成的随机图中，每對頂點之間皆各自獨立地以某固定概率${\displaystyle p}$ 連邊。圖論的概率法（英语：probabilistic method）常用此模型證明存在具某種性質的圖，並用作明確定義何謂「幾乎所有」圖皆具某種性質。

ER随机图${\displaystyle G(n,p)}$ 的參數${\displaystyle n}$ 表示頂點數，而${\displaystyle p}$ 則是任意兩頂點之間連邊的概率。此模型中，各個頂點的地位相同，沒有偏重，每個頂點的度遵循二項分佈，對於任意頂點${\displaystyle v}$ ，度數為${\displaystyle k}$ 的概率是：

${\displaystyle \mathbb {P} (\deg(v)=k)={n-1 \choose k}p^{k}(1-p)^{n-1-k}.}$ 

瓦茨-斯特罗加茨模型

主条目：瓦茨-斯特罗加茨模型

 

瓦茨-斯特罗加茨模型生成網絡時，用到「重連」（rewiring）。模型始於規律的柵格結構，然後其每條邊有一個固定的概率發生重連，改變連接的頂點。圖示的平均度為${\displaystyle \langle k\rangle =4}$ 。

瓦茨-斯特罗加茨模型（Watts–Strogatz model）產生的隨機圖滿足小世界性質（英语：small-world properties）。

初始時，將網絡的節點排成一圈，每個節點與最近${\displaystyle \langle k\rangle }$ 個節點相連，另一個參數是重連的概率${\displaystyle p}$ ，前述的每條邊以此概率發生重連，變成一條新的邊，保持一端不變，另一端則改為隨機一個頂點（但保持沒有兩點重複連邊）。重連次數期望值為${\displaystyle pE=pN\langle k\rangle /2}$ 。

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

分支领域

信息技术网络

互联网

生物圈网络

生物神经网络

计算机网络

人工神经网络

经济网络

人际关系网络帮助决定了人们所选择的职业生涯，人们所找到的工作，他们买的商品，以及他们如何投票。社会网络决定着我们生活中的诸多方面。因此，社会网络是如何影响我们的行为，在一个社会中出现什么样的网络结构以及它们出现的概率有多大，以及我们为什么像现在这样安排我们自己的生活，就成为了值得研究的问题，也是许多社会科学研究中的关键因素^[8]。

参考

• 图论
• 统计力学
• 数据挖掘
• 复杂网络

参考文献

1. 方錦清，汪小帆，等. 一门崭新的交叉科学:网络科学(上) （页面存档备份，存于互联网档案馆）. 物理學進展. 2007.
2. Duncan J. Watts. (PDF). Annual Review of Sociology. 2004年 [2014-07-06]. （原始内容 (PDF)存档于2014-07-14） （英语）. 
3. Committee on Network Science for Future Army Applications. . National Research Council. 2006 [2014-07-06]. ISBN 0309653886. （原始内容存档于2008-07-05）. 
4. Ted G. Lewis. . 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. . Princeton University Press. 2010 [2014-07-06]. ISBN 0691148201. （原始内容存档于2014-07-22）.