论文题目：

25 years of small-world network theory

论文地址：

https://www.nature.com/articles/s42254-023-00628-6

网络似乎是研究许多物理系统的自然数学框架，如电力网格、大脑和社交媒体平台。现今，关于这些网络组织方式的理论研究已颇为丰富，但情况并非一直如此。尽管网络研究历史悠久，但长期以来，描述现实世界网络的最接近方式仅是将其视为随机图（random graphs）——尽管大多数系统都表现出一定的组织性。正是在这样的背景下，25年前，邓肯·瓦茨（Duncan Watts）和史蒂文·斯托加茨（Steven Strogatz）发表了《“小世界”网络的集体动力学》一文，开启了现代网络科学的新纪元。

Duncan Watts 和 Steven Strogatz 提出“小世界”网络

Watts, D. & Strogatz, S. Collective dynamics of ‘small-world’ networks. Nature 393, 440–442 (1998)

https://www.nature.com/articles/30918

随机图的研究至少可以追溯到20世纪50年代末，当时保罗·埃多士（Paul Erdős）、阿尔弗雷德·伦伊（Alfréd Rényi）和埃德加·吉尔伯特（Edgar Gilbert）各自独立地引入了随机配对连接、固定节点数的图模型。这类图的特点是具有较短的路径长度——如果总连接数超过某一阈值，那么两个节点间最短路径上的连接数平均较小。这一特性与现实世界网络的观察相符，例如，社会心理学家斯坦利·米尔格拉姆（Stanley Milgram）在20世纪60年代曾经证明，两个美国人之间的典型联系链的长度介于2到10之间——即小世界现象。

然而，随机图几乎没有聚类现象——例如，节点之间很少连接成三角形——这与现实世界网络的观察不符。在现实世界网络中，一个人的朋友之间，往往相互是朋友。与之相反，聚类是规则晶格的典型特点。

瓦茨和斯托加茨的贡献在于提出了一个模型。该模型通过采用环形晶格，并以固定概率，对每个链接进行随机的重新连接，实现了规则晶格与随机图之间的插值。他们发现，在一定的重新连接概率范围内，所得网络保留了原始晶格的高聚类性，但路径长度大为缩短。因此，他们构建了一个能捕捉现实世界网络这两大重要特性的模型，并将其命名为“小世界”网络，以致敬米尔格拉姆的研究。

瓦茨和斯托加茨写道：“我们希望我们的工作能激发对小世界网络的进一步研究。”可以说他们的愿望已经实现。次年，阿尔伯特-拉斯洛·巴拉巴西（Albert-László Barabási）和雷卡·阿尔伯特（Réka Albert）引入了一种生成无标度网络的算法，即节点具有特定数量链接的概率遵循幂律分布。这一模型捕捉了现实世界网络的另一关键特性，即网络中常包括一些与众多其他节点相连的中心节点。巴拉巴西-阿尔伯特模型（简称BA模型）与瓦茨-斯托加茨模型（简称WS模型）相比，更具“小世界”特性。因为在WS模型中，节点间最短路径的最大长度随着系统规模的对数增长，而在BA模型中，最短路径的最大长度随着系统规模的对数的对数增长。这两个模型已成为网络理论的基础工具。

Barabási, A.-L. & Albert, R. Emergence of scaling in random networks. Science 286, 509–512 (1999)

https://www.science.org/doi/10.1126/science.286.5439.509

近年来，人们逐渐认识到，将系统建模为网络并非总是最佳方法。例如，瓦茨和斯托加茨通过将出现在同一部电影中的演员配对连接，构建了一个小世界网络，但人们同样可以通过一种高阶连接将一部电影的演员们连接在一起。由此产生的超图（也称为高阶网络）能以一种普通网络无法实现的方式捕捉集体行为。

Battiston, F. et al. The physics of higher-order interactions in complex systems. Nat. Phys. 17, 1093–1098 (2021)

https://www.nature.com/articles/s41567-021-01371-4

网络科学集智课堂第三期：

从数学建模到多学科应用