引用量超过4万的经典论文：小世界网络的集体动力学（附原文下载）

snachina

导语

1998年，一篇名为“小世界网络的集体动力学”（Collective dynamics of ‘small-world’ networks）的文章发表于 Nature，首次提出“小世界网络”的数学模型，并引起了来自社会科学、信息科学和自然科学等领域对这一模型的关注和应用。目前，该论文已经有超过 42000 次的引用量。本文是对这篇经典论文的简要介绍。

原文主要从数学上定义了小世界网络，对模型的全局性质和局部性质进行定量分析，并将其特征与现实生活中的例子联系。作者还通过分析简化的传染病传播模型，试图推广这一数学模型在动力学过程研究中的应用。

论文题目：
Collective dynamics of ‘small-world’ networks

论文地址：https://www.nature.com/articles/30918

下载地址：watts-collective_dynamics-nature_1998 (1).pdf

从六度分隔到小世界网络

小世界现象的概念最早大概出现于匈牙利作家考林蒂（Frigyes Karinthy）的短篇小说《链条》中，发表于 1929 年。

在《链条》这部小说中，一个人可以通过其认识的网球冠军、网球冠军的球友瑞典国王、瑞典国王又是诺贝尔奖的颁奖者这一路径，以简单明了的方式与一个诺贝尔奖的获得者连接上。考林蒂的关于人与人之间最多需要 5 层关系就能联系起来的推断，可以说是六度分隔假说的最早表述，也是“小世界网络”概念的雏形。

20世纪60年代，美国哈佛大学心理学教授斯坦利·米尔格拉姆（Stanley·Milgram）组织了连锁信件实验，也被称为小世界实验（Small world experiment），并于1967年将此实验的过程和结果发表于Psychology Today期刊：

一开始从Kansas和Nebraska两个州招募了一批志愿者，请他们分别将一封信转寄给一个住在Cambridge的哈佛大学某学生的妻子和一个住在Boston郊区的股票经纪人。尽管志愿者有寄信目标的相关信息，但是如果不是私人关系，不能把信直接寄给目标人，所以志愿者每次只能把信寄给最有可能知道这个人的熟人。在哈佛大学的研究人员通过原始信封里的追踪卡片追踪信函的路径。

结果表明，信件经过约6次转发后到达了目标收信人手中，后人称为六度分隔理论（Six degree of seperation）。

随后的几十年中，人们发现小世界现象广泛存在于各种社会网络、电力网络、生物神经网络中。1998年，康奈尔大学的博士生的Duncan Watts与他的导师Steve Strogatz首次提出小世界网络的概念和数学模型，尝试解释这一系列现象背后的原因。

关于小世界网络的集智百科：

小世界网络就在你身边，你了解嘛？| 集智百科

小世界实验：六度分隔理论的来源 | 集智百科

小世界网络模型简介：

从规则网络演化而来

Watts和Strogatz提出的小世界网络模型，图像上介于规则网络（regular networks）和随机网络（random networks）之间——既表现出与规则网络类似的高聚集性，又像随机网络一样节点之间存在“捷径”。

什么是规则网络？用n表示网络的节点数，k表示网络的连边数，可以给出规则网络的数学定义。以图为例，有n=12，k=4的规则网络由每个节点与之最近邻的4个节点相连接而形成。

图1：规则网络

但真实世界的网络不会这么规则。于是 Watts 和 Strogatz 引入随机性，重新设计了连接的规则。在规则网络的基础上，对每条连边进行重新连接演化。

重新连接的规则是：从一个节点顺时针方向的最近邻连边开始，此节点为出发点，连边与其余节点连接的概率为p。若还是与最近邻节点相连，此连接保持不变。按此规则顺时针方向遍历所有节点的最近邻连边后，对每个节点的次近邻连边进行同样的操作。

图2：规则网络演化为小世界网络

当p=0时，原规则网络不变。当0<p<1时，原规则网络演变为小世界网络。当p=1时，规则网络演变为随机网络。

图3：规则网络→小世界网络→随机网络

其中，网络的全局特征和局部特征，分别由结构参数特征路径长度L和聚集系数C来描述。

图4：网络特征路径长度示意

特征路径长度L 指的是，在网络中任选两个节点，连通这两个节点的最少边数，定义为这两个节点的路径长度(或长度)，如图4中A到D的路径长度为2（A→C→D）；网络中所有节点对应的路径长度的平均值，定义为网络的特征路径长度L。特征路径长度反映的是网络的全局特征。

对应到连锁信件实验（或小世界实验）中，特征路径长度，即志愿者将信寄给目标人物所需要的平均转发次数。

聚集系数C 是指，假设某个节点有k条边，则这k条边连接的节点（k个）之间最多可能存在的边的条数为k(k-1)/2，用实际存在的边数除以最多可能存在的边数得到的分数值，定义为这个节点的聚集系数。所有节点的聚集系数的均值定义为网络的聚集系数。某个节点的聚集系数，反映了网络在该点附近位置的局部特征。

在社交网络中，某个点聚集系数大，说明这个点代表的人有许多朋友，反之说明他的朋友少。

小世界网络的结构特点

接着，作者分析此演变过程中特征路径长度、聚集系数随重连接概率p的变化关系。

图5：特征路径长度、聚集系数随重连接概率        p        的变化

图中的数据来源于对20个规则网络（n=20，k=4）到随机网络演变做平均而得。其中L(0),C(0)分别是规则网络的特征路径长度、聚集系数，L(p),C(p)分别对应重新连接概率为p时的特征路径长度、聚集系数。L=L(p)/L(0),C=C(p)/C(0)是以初始规则网络为标准对所有数据进行归一化。

研究者重点研究节点连接稀疏但不至于分离的小世界网络。为了保证随机图是连接的，需要满足n≫k≫ln(n)≫1。此条件下，研究者发现，当p趋于零时，L～n/2k，C～3/4；当p趋于1时，L≈Lrandom～ln(n)/ln(k) , C≈Crandom~k/n。其中，Lrandom定义为节点数为n，连接数为k的随机网络的特征路径长度，即p=1时的L；Crandom定义与Lrandom类似，即p=1时的C。

此时的规律是，规则网络高度聚集，L随n线性增长；随机网络聚集较弱，L随n的对数增长。对这两个极值情况的分析会让人们误以为聚集系数大的网络特征路径长度的值大，聚集系数小的网络特征路径长度的值小。

然而在p介于0和1的很长一段区间内，L趋于Lrandom时，C(p)远大于Crandom。这种L(p)急剧变小的小世界网络是少量的长连边或捷径（long-range edges /'short cuts'）的形成导致的。长连边接指对两节点的连接长度小于Lrandom。当p很小的时候，每条捷径的形成对L 会产生很强的非线性影响，除了被连接的节点被影响，还会影响到节点周围的节点。

相比之下，移走一个聚集区域的节点而产生的捷径，对C 产生线性的影响更明显。因此，当p 很小的时候C(p) 基本上保持不变，但是L(p) 迅速变小。这意味着小世界中局部的变化是不明显的。在经过重连接后形成捷径的前提下，研究者对多种不同的起始网络图经过不同规则演化后进行了定量分析，都验证了这一观点。

小世界网络的实例

作者从这一现象推测，在有许多节点的稀疏网络中，        小世界效应或许非常普遍。通过计算演员合作网络图、美国西部电力输送网图和C. elegans线虫的神经网络图，作者验证了这一观点: L≳Lrandom但是C≫Crandom。这也说明，小世界网络并不仅存在于社交网络中，而且很可能在自然界大型的稀疏网络中普遍存在。

表1：三个生活中的小世界网络例子

表中，Lactual指实际网络结构的特征路径长度，Lrandom定义为节点数为n，连接数为k的随机网络的特征路径长度；Cactual与Crandom定义类似。

电影明星合作网络中，每位明星为一个节点，若两位明星共同出演过一部电影即可建立连接关系（数据来源http://us.imdb.com，数据统计截止于1997年4月）；在电力网络中，每个发电机为一个节点，连边表示与之连接输电站和变电站的高压输电线；线虫的神经网络中，神经元为节点，连接神经元的突出或者间隙连接为连边。所有连边都是无向无权重的。

小世界网络中的动力学：疾病传播

研究者通过研究简易化的传播病传染模型揭示了小世界网络的动力学性质。

在上文所述小世界网络模型（图3）的基础上，网络上的疾病传播，可以简化为：t=0时刻，其中一个人（网络中一个节点）被感染，其余人健康。患病者在一段时间（记为单位时间1）后因死亡或被隔离而永久离开网络。在这段时间中，病毒感染者传染引起其余健康个体患病的可能性为r。在接下来的时间中，病毒不断在人群中传播，直到整个群体被感染或者病毒灭亡。

图6：全体感染所需时间T与概率p的变化关系，同图5对数值进行重新标度

此简化模型做小世界网络演化后得到两个结果。

• 传染病感染一半群体所需的时间rhalf随p的增大而减小（见图6a）；
• 不管群体的网络结构如何，全体感染所需要的时间T与p的关系T(p)与之前（图5）L(p)相似（见图6b）。
  

尽管网络中只形成了少量的捷径，小世界网络模型全体感染所需的时间与随机图被全体感染的时间十分接近，即传染病在小世界网络中迅速传染。 研究者强调了他们的传染病传播模型与前人研究工作的不同。文中的模型将网络的动力学性质T(p)描述为网络结构的显函数，不是关注某些随机图、散点或者链中特定的拓扑结构，而其他网络模型只强调网络的结构会影响传染病传播的速度和程度。文中的网络图皆为连接图，所以所预测的动力学性质受微小的图结构变化影响比不连接程度的影响更大。

结语

1998年时，小世界网络的结构和动力性质方面的研究还没有得到其他领域的关注。随后的二十多年中，现实生活中出现越来越多的小世界网络，其动力学性质应用于解释导航（搜索）、同步、传播以及博弈等复杂问题中。比如同步问题，因小世界网络具有较大的局部群聚特性，同时又具有较短的        特征路径长度，所以小世界网络实现同步的能力远远高于其对应的规则网络。


至今，原文引用已达4万多次。基于原文两位作者的姓氏，这个小世界网络模型后来被命名为Watts-Strogatz模型（或W-S模型）。

snachina