本文作者Alessandro Vespignani

美国东北大学网络科学家

编译：集智翻译组

来源：Nature

论文题目：Twenty years of network science

20年前的“小世界”（small-world）网络模型，解释了人与人相连为什么是六度分隔。这个发现看似小众，日后却影响巨大。

1998年，Watts, D. J. 和 Strogatz, S. H. 引入了“小世界”网络模型，它描述了真实世界中网络节点的聚集和分离。我仍然清楚记得，当时我和其他统计物理学家的讨论：相比于我们习以为常的网格状结构，小世界网络模型很有意思，但似乎只是对传统模型的一个偏离。但是随着这篇论文被各个领域的学者广泛引用，它深刻地影响了我们对疾病传染、信息扩散等现实世界的动态行为和相变现象的理解。这篇文章很快开启了一个新时代——作为多学科交叉领域的网络科学由此诞生。

Erdös–Rényi 模型

在 Watts 和 Strogatz 的论文发表之前，典型的网络生成算法是基于像 Erdös–Rényi 模型这样的构建过程。这些过程有明显缺点：对网络中节点之间连边生成规则缺乏认识，并且还假设一对节点之间连接的概率可以随机给定。这样的过程产生的是随机网络，网络中任意两个节点之间的平均路径长度（两个节点相连所需要的最小连边数量），与节点总数满足对数关系。换句话说，随机性可以解释被统称为“六度分隔”的小世界现象：世界上的每个人都可以通过一系列（6个）彼此认识的人联系在一起。

教堂中人群的聚集

（Cliquishness）

然而，随机地构建网络不能捕捉到真实世界中网络节点的局部聚集性

(Cliquishness）。聚集性由聚集系数来度量，聚集系数定义为“某个节点的邻居节点之间的连边数量，与邻居节点之间可能连边数最大值之比”，用来定量描述节点的聚集程度。真实世界的网络中，节点聚集的典型例子是“我朋友的朋友也是我的朋友”：三个人在社交网络中彼此成为朋友的概率，远远高于用简单随机过程构建的模型网络所做的预测。





“小世界”网络模型

为了克服随机性和聚集性之间的矛盾， Watts 和 Strogatz 提出了新的模型，首先有一个具有较大聚集系数的普通网络，然后允许节点之间以固定的概率（p）随机地重新连接，从而引入随机性（Stochasticity）。通过调整 p，这个模型可以有效地生成介于标准网络（p 趋近于0）和完全随机网络（p 趋近于1）之间的网络。

在 p 非常小的时候，产生的网络是一个规则的网格结构，具有很高的聚集系数。然而即使 p 值很小，网格中相距很远的节点之间也会出现连边，从而大幅缩短了网络节点间的平均最短路径长度，如图所示。 Watts 和 Strogatz 的研究表明，根据节点数量，在很大的 p 值范围内，都有可能找到聚集程度很高，同时平均最短路径很小的网络，从而调和了小世界现象和网络聚集的矛盾。



图一：小世界网络模型：

1988年，Watts 和 Strogatz 提出了一个用于解释实际网络结构的模型。a，图中的三角晶格中，每个节点和其他六个节点相连，Watts就是从这种规则的网络开始构建模型；b，他们让节点之间以固定的概率随机重连。随着这个概率值的增加，越来越多的近路(红线)把网络中相距较远的节点连接起来。这就能产生小世界效应:只需通过少许几条节点之间连边，任何两个节点都能相连，但是相邻的节点又相互连接，形成了集聚集团。

Watts 和 Strogatz 的模型最开始只是被简单地看作对六度分隔的一种解释。但是，它铺平了研究网络结构对众多网络上动力学现象的影响的道路，这有可能是其最重要的影响。另外一篇论文也很关键：1999年，Barabási 和Albert提出了“偏好依附”网络模型，该模型强调了真实网络中节点之间连边的概率经常有“重尾分布（heavy-tailed）”的特点，而不是由随机网络推出的泊松分布。这些具有集群连通性和异构联通性的网络所呈现出的涌现行为和相变特性，吸引了许多领域的科学家的注意。

无标度网络模型

随后的一系列的研究发现，突出了这种复杂的网络结构如何支撑起各种真实世界中的系统的研究，而且在网络鲁棒性、流行病传播、信息流和集群行为的同步性质等方面都有重要应用。例如，小世界连接模式被证明是理解万维网结构和大脑功能分区和结构分区之间通信机制的关键。网络其他的机构性质在随后被仔细的研究，例如模块度和结构单元的概念。从亚细胞网络到生态系统再到互联网，所有的这些研究都帮助科学家们更好的描述和理解这些自然和人造系统的架构。

当前这一代网络科学，受益于空前的计算能力、大数据集和新的计算建模技术的领域交叉，从而在单个节点的动力学和宏观网络的特性之间，架起了一座桥梁。但是，小世界网络和偏好依附模型直接又简洁，仍然支撑着我们对网络拓扑的理解。事实上，正是这些模型与不同科学领域的关联，奠定了网络科学这一跨学科领域

（multidisciplinary field）的基础。

整合来自社会科学、物理学、生物学、计算机科学和应用数学这些不同领域的知识和方法并不容易。找到共同点、就定义达成一致意见、协调和重视每个领域研究网络的不同方法，往往需要好几年的时间。这项工作仍然在进行当中，跨学科研究固有的困难和陷阱就已经全部呈现出来。但是在过去的20年里，一个充满活力的网络科学社区已经出现：有著名的期刊、有专门的研究机构，以及有数千名科学家参与的会议。

这篇经典论文发表已经20周年，现在小世界网络模型被认为是基准的网络拓扑之一，被超过18000篇论文引用。 Watts 和 Strogatz 在论文结尾说，“我们希望这项工作能够促进对小世界网络的进一步研究。”也许没有比这更有远见的声明了。

小世界网络之父邓肯·瓦茨经典回顾

解读幂律与无标度网络 | 网络科学入门

无标度网络理论之父Barabási回应质疑

理论危机 | 无标度网络遭到史上最严重质疑

扫码听课