网络科学

网络科学是从交叉学科研究成长起来的一个新兴的学术领域^[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. 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）.