经典论文难度：入门

“小世界”网络的集体动力学

Collective dynamics of 'small-world' networks

Watts DJ, Strogatz SH · Nature 1998 · DOI: 10.1038/30918

小世界重连概率聚集系数特征路径长度线虫神经网络

一句话

用随机重连在规则网格与随机图间插值，发现少量捷径即可使网络兼具高聚类与短路径，并在真实网络中验证。

相关专题：小世界与无标度网络模型、网络结构指标与随机图、同步与协同动力学

VIDEO讲解视频

“小世界”网络的集体动力学5 分 15 秒

文字稿

大家好，这一期我们精读1998年发表在Nature上的小世界网络论文。作者是 Watts 和 Strogatz，全文只有三页，非常值得完整读一遍。

1998年以前，连接拓扑通常只有两种选择，一种是规则网格，聚集程度高，但两点之间要走很多步。另一种是完全随机的随机图，路径很短，却几乎没有三角形。社会学中的六度分隔现象提示，真实网络可能介于两者之间。作者要问的是，在规则与随机之间连续调节，结构量会怎样变化，真实网络又落在哪里？

先看两个指标，聚集系数刻画的是朋友的朋友也是朋友的程度。一个节点的邻居之间最多能连多少条边，实际连了多少，比例就是它的局部聚集系数。画面中这个节点有5个邻居，邻居之间最多可以有10条边，红色标出的是实际存在的边。对所有节点取平均就是聚集系数；特征路径长度则是所有节点对最短路径边数的平均。

模型从一个环形网格出发，每个节点只与最近的几个邻居相连。然后依次考察每条边，以一定的重连概率，把它的一端改接到随机选出的节点上。重连概率为0是原始网格，为1时近似随机图，中间就是待探索的地带。画面左边橙色的边，就是改接出来的捷径。右边两条曲线是聚集系数和路径长度，都除以了规则网格时的值，横轴取对数。重连概率还很小时，路径长度已经急剧下降，聚集系数却仍接近原值。原文模拟取1000个节点、每个节点10个邻居，曲线是20次重连实现的平均。

作者给出两个极限，重连概率趋于0时，路径长度随节点数线性增长，聚集系数约为四分之三。重连概率趋于1时，路径长度只随节点数的对数增长，聚集系数则很小。小世界网络的判据是，路径长度接近随机图，而聚集系数远大于随机图。机制在于，一条捷径能把两个原本很远的邻域拉近，对路径长度的影响是高度非线性的。而从局部团簇里拿走一条边，对聚集系数的影响至多是线性的。

电影演员合作网有22万多个节点，平均路径长度3.65，聚集系数高达0.79。美国西部电网有4941个节点，路径长度18.7，聚集系数0.080。秀丽隐杆线虫的神经网络有282个节点，路径长度2.65，聚集系数0.28。同规模随机图的路径长度分别是2.99、12.4和2.25，与真实网络相差不大。而随机图的聚集系数只有0.00027、0.005和0.05，远低于真实网络。作者强调，这三个网络并不是挑选出来的。

在一个简单的感染移除模型里，使一半人群被感染所需的传染性，随重连概率增大迅速下降。对传染性最强的疾病，传遍全体所需的时间，与路径长度的曲线形状几乎相同。小世界连接下的相位振子，几乎和全连接模型一样容易同步，而边数少了几个数量级。作者还报告了元胞自动机密度分类和多人囚徒困境上的结果，这部分可以略读。

这个模型的度分布很窄，没有枢纽节点，第二年的增长与优先连接模型补上了这一块。重连可能使网络断开，Newman 与 Watts 随后提出只加捷径、不删边的变体，便于解析。原文的判断是定性的，后来的小世界系数依赖零模型和网络密度，大网络几乎都会大于1。后来大量研究报告人脑网络具有小世界性，但结论对脑区划分和阈值选择很敏感。

线虫神经网络是表中唯一的生物网络，它同样兼具高聚类和短路径。对传染病来说，只需少量重连，传遍全体的时间就接近随机图。如果要论证某种脑疾病患者的小世界性下降，就要设计好零模型，避免密度差异造成假象。

总结一下，作者用随机重连在规则网格和随机图之间连续插值。少量捷径就能让路径骤降到随机图水平，而聚集系数几乎不变。演员合作网、电网和线虫神经网络都落在这个小世界区间。这种结构让传染病更容易传播，也让振子更容易同步。建议细看原文图2和表1，再亲手调一调重连概率，画出这两条曲线。

一句话看懂

只需把规则网格中极少一部分边随机改接成“捷径”，平均路径长度就会骤降到随机图的水平，而聚集系数几乎不变；这种“高聚类 + 短路径”的状态就是小世界网络，它在社会、技术和生物网络中普遍存在。

研究背景与问题

在 1998 年以前，研究耦合振子、神经网络、传染病等动力学系统时，连接拓扑通常只有两种选择：完全规则（如环形网格）或完全随机（Erdős–Rényi 随机图）。两者各有一个“缺点”：规则网格聚集程度高，但任意两点之间要走很多步；随机图路径很短，但几乎没有三角形。社会学中的“六度分隔”现象提示真实网络可能介于两者之间，但当时没有一个可以定量刻画这一中间地带的模型。

作者的问题是：在规则与随机之间连续调节，网络的结构量会如何变化？真实网络落在哪里？这种结构对动力学过程有什么影响？

核心思想与方法

模型从一个环形网格出发： $n$ 个节点排成一圈，每个节点与最近的 $k$ 个邻居相连。然后按顺时针依次考察每条边，以概率 $p$ 把它的一端改接到随机选择的节点上（不允许重边）。 $p=0$ 是原始网格， $p=1$ 近似随机图， $0<p<1$ 是待探索的中间地带。

两个指标分别刻画全局和局部结构：

特征路径长度 $L(p)$ ：所有节点对之间最短路径边数的平均值，刻画网络的“全局距离”。

聚集系数 $C(p)$ ：节点 $v$ 有 $k_v$ 个邻居，邻居之间最多可有 $k_v(k_v-1)/2$ 条边，实际存在的比例记为 $C_v$ ； $C$ 是 $C_v$ 对所有节点的平均，刻画“朋友的朋友也是朋友”的程度。

小世界网络： $L \gtrsim L_{\text{random}}$ 而 $C \gg C_{\text{random}}$ 的网络。

作者给出两个极限： $p\to0$ 时 $L\sim n/2k$ 、 $C\sim3/4$ ； $p\to1$ 时 $L\approx\ln n/\ln k$ 、 $C\approx k/n$ 。关键的机制解释是：一条捷径能把两个原本很远的邻域“拉近”，对 $L$ 的影响是高度非线性的；而从局部团簇中拿走一条边对 $C$ 的影响至多是线性的。因此 $p$ 很小时 $L$ 已经大幅下降， $C$ 却几乎看不出变化。

主要发现

存在一个宽阔的 $p$ 区间：在 $n=1000$ 、 $k=10$ 的模拟中（图 2，横轴取对数）， $p$ 还远小于 1 时 $L(p)/L(0)$ 已急剧下降，而 $C(p)/C(0)$ 仍接近 1（曲线均为 20 次重连实现的平均）。作者指出，从局部看“几乎察觉不到”向小世界的转变。
三个真实网络都是小世界（表 1）：电影演员合作网（ $n=225\,226$ ） $L=3.65$ 、 $L_{\text{random}}=2.99$ ， $C=0.79$ 、 $C_{\text{random}}=0.00027$ ；美国西部电网（ $n=4941$ ） $L=18.7$ 对 12.4， $C=0.080$ 对 0.005；秀丽隐杆线虫神经网络（ $n=282$ ，突触与缝隙连接均视为无向边） $L=2.65$ 对 2.25， $C=0.28$ 对 0.05。
传染病更容易传播：在一个简单的感染–移除模型中，使一半人群被感染所需的传染性 $r_{\text{half}}$ 随 $p$ 增大而迅速下降；对传染性最强的疾病，传遍全体所需时间 $T(p)$ 与 $L(p)$ 的曲线形状几乎相同——只需少量重连，传遍全体的时间就接近随机图。
其他动力学：小世界连接下的相位振子几乎和全连接（平均场）模型一样容易同步，而边数少了几个数量级；作者还报告了元胞自动机密度分类和多人囚徒困境上的结果。

怎样读这篇论文

全文只有三页，建议完整读。先读摘要和第一段，理解“规则–随机”二分法；再细看图 1（重连过程示意）和图 2（ $C$ 、 $L$ 随 $p$ 变化，注意对数横轴）——这是全文的核心图；然后看表 1 及其注释，注意作者如何定义每个网络的节点与边、以及“随机图”是指同样 $n$ 和 $k$ 的随机图；最后看图 3 的传染病模拟。关于元胞自动机和囚徒困境的段落可以略读。

局限与后续工作

度分布很窄：WS 模型中每个节点的度都集中在 $k$ 附近，没有枢纽节点，无法解释真实网络的重尾度分布。第二年 Barabási 与 Albert 的增长–优先连接模型补上了这一块。
模型不易解析：重连可能使网络断开。Newman 与 Watts 随后提出“只加捷径、不删边”的变体，便于解析计算。
“是不是小世界”的判据：原文用 $L\approx L_{\text{random}}$ 、 $C\gg C_{\text{random}}$ 的定性判断。后来出现了小世界系数 $\sigma$ 、 $\omega$ 等定量指标，但它们依赖零模型和网络密度，大网络几乎都满足 $\sigma>1$ ，比较两组网络时必须控制密度。
脑网络中的应用：后来大量研究报告人脑结构与功能网络具有小世界性，但结论对脑区划分和阈值选择很敏感（见拓扑指标：小世界、模块、枢纽与富人俱乐部）。

关联知识

聚集系数的定义就是本文给出的“平均局部聚集系数”；真实网络与随机网络的比较用 ER 随机图做“尺子”的思路也来自本文的比较方式。
Watts–Strogatz 小世界模型中的 WS 模型、表 1 数据和小世界判据直接来自本文，配套的交互演示可以亲手调节重连概率。
网络拓扑与同步阈值讨论拓扑对同步的影响时，可以回到本文“小世界振子容易同步”的观察。
线虫连接组在网络可控性与稳定性中还会再次出现（Yan 等 2017 的控制实验）。

延伸思考

作者强调表 1 中的三个网络“不是挑选出来的”。如果你要论证某种脑疾病患者的脑网络“小世界性下降”，你会怎样设计零模型，才能避免密度差异造成的假象？
在线虫网络中，作者把化学突触和缝隙连接都当作无向、无权边。这一简化可能如何影响 $C$ 和 $L$ 的估计？
图 3 显示传染时间 $T(p)$ 与 $L(p)$ 曲线几乎重合。为什么最强传染性下的传播时间主要由最短路径决定？传染性较弱时这一关系还成立吗？