“小世界”网络的集体动力学 Duncan J. Watts ， Steven H. Strogatz 美国纽约（14853）伊萨卡,康奈尔大学,Kimball 学院理论与应用力学系 （NATURE | VOL 393 | 4 JUNE 1998 pp.440—442） （译者 王恒山 上海理工大学管理学院、系统工程研究所 上海 200093） ....... ........... ............ ............ ............ ........... ......... 连结动力系统的网络已被用于为生物振荡器1-4、约瑟夫森结阵列5-6、应激介质7、神经网 络8-10、时空博弈11、基因控制网络12以及许多其它自组织系统建立模型。通常，这些模型的 拓扑结构被假定为完全规则网，或完全随机网。但许多生物网络、技术网络和社会网络却 介于这两种极端的网络之间。在这里我们探究能够直达两种极端网络中间地带的简单网络 模型：即通过重新连接规则网络中结点之间的连线来增加该网络的无规则性。我们发现这 些网络能够像规则网那样具有高度的集群性，又像随机网那样具有短的特征路径长度。由 于具有类似小世界现象（即众所周知的六度分离15），我们把它们称为“小世界”网络13-14。 蠕线虫的神经网络、美国西部的电力网络以及电影演员的协作网络已被证明是小世界网络。 具有小世界连接的动力系统模型显示出能增强信号的传播速度、计算能力和同步能力。尤 其是，传染性疾病在小世界网络中传播比在规则网络中要容易得多。 为在规则网络和随机网络之间生成新的网络，我们考虑以下随机重新连线过程（图 1）。 从一个有n个顶点以及每个顶点有k条边的环形网络开始，以概率p随机给每条边重新连线。 这一连线过程允许我们在规则网(p=0)和随机网(p=1) 之间生成各种网络，因此就能探查我 们还知之甚少的中间区域（0>k>>ln(n)>>1,其中 k>>ln(n) 保证随机网络图是连通的16。在这种状态下，我们发现 当p→0 时，L～n/2k>>1 以及C～3/4，而当p→1 时，L≈Lrandom～ln(n)/ln(k)以及C≈Crandom ～ k/n<<1。这样，当p=0 时的规则网络是一种高度集群的大世界网络，此时 L随n 线性增长， 而当p=1 时的随机网络是一种低度集群的小世界网络，此时 L仅随n成对数增长。这些有限 的例子可能导致人们推测大 C总是与大 L关联，小C总是与小L关联。 相反地，图 2 揭示出有一个p的广阔区间,在这个区间上L(p)几乎与Lrandom一样小，但 C(p)>>Crandom。这些小世界网络是通过引入几条长距离的边造成L(p)的直接下降所致。这样 的“捷径”连线会以比Lrandom方式不同方式连接更远离得多的顶点。对于小p,每个捷径对L有 一个高度非线性作用，不但缩小了它连结的一对点之间的距离，而且也缩小了它们所处的邻 域之间的距离，以及邻域的邻域之间的距离等。相比之下，从一个集群邻域中移去一条边以 建立一个捷径最多对C有线性作用；因此，即使L(p)急速下降，对于小P来说，C(p)仍然几乎 不变。 这里的重要意义是在局部层次(由C(p)反映)上向小世界网络的转变几乎是无法觉察 的。为检验这些结果的稳定性，我们已经试验了许多不同种类的原始规则网络图，还有随机 重新连接的不同算法，所有都给出了质量相似的结果。唯一的要求是改写连线边的方式必须 会比Lrandom方式连接更远离得多的顶点。 以上理想化的结构揭示了捷径的关键作用。它暗示小世界现象可能在有许多点的稀疏网 络中普遍存在，甚至捷径只占一个微小比例就足够了。为验证这一观点，我们计算了以下三 个网络的L和C值，它们是特色电影（来自http://us.imdb.com网站的数据）中演员的合作图， 1 

美国西部的电力网，以及蠕线虫17的神经网络。所有三个网络图都有科学价值。电影演员合 作图是社会网络的替代品18，对它的说明相对比较容易。对于传统以P. Erdös的观点(部分数 据来自http://www.acs.oakland.edu/,～grossman/erdoshp.html)为中心的数学合作研究 图也是类似的。电力网格图是与电力网络19的效率和稳定性相关的。而线虫是完全反映神经 网络的唯一例子。 表 1 说明三个图都是小世界网络。这些例子不是精心挑选的；之所以选它们是因为它们 内在的价值以及可以得到它们的完全连线图。这样，小世界现象就不仅仅是社会网络13，14的 奇异特性，也不是理想模型的赝像——它或许对自然界许多大型稀疏网络是一种普遍现象。 表 1 小世界网络的实际案例 --------------------------------------------------------- Lactual Lrandom Cactual Crandom …………………………………………………………………………… 电影演员合作网 3.65 2.99 0.79 0.00027 电力网 18.7 12.4 0.080 0.005 线虫 2.65 2.25 0.28 0.05 …………………………………………………………………………… 三个真实网络的特征路径长度L和集群程度C，与顶点(n)数量相同以及每个顶点拥有边的平均数量相同的随 机网络图之比较。(演员: n=225,226, k=61. 电力网: n=4,941, k=2.67. 线虫: n=282, k=14.) 网络图定 义如下：如果两个演员在一部电影中共同表演，就把他们用一条边连接起来。我们把讨论限定在这个网络 图的巨大连通分支上16，这个分支包括到 1997 年 4 月为止存储在因特网电影数据库(来自http://us.imdb.com) 里所有演员的 90%。对于电力网络来说，顶点代表发电机、变压器和变电站，边代表它们之间的高压传输 线。对于蠕线虫来说，如果两个神经细胞由突触或缝隙连接来连接的话，一条边就会把这两个细胞连起来。 我们把所有的边看作是无向的和无权重的，把所有的顶点看作是相同的，并承认这些假设是粗糙的近似。 所有三个网络显示了小世界现象：L Lrandom,但C >>Crandom。 我们现在研究动力系统的小世界连通性的功能意义。我们的试验案例是一个故意简化的 传染性疾病的传播模型。人口结构由图 1 所描绘的图的家族建模。在时间 t=0 时，一个单一 的传染性个体被引入原来健康的人群。经过一段时期的疾病传染后，传染性个体就会被永久 移去(由于免疫性或死亡)。在这一时期，每一个传染性个体会有概率为 r的机会把疾病传染 给它的每个健康邻居。在随后的各时间步中，疾病沿着网络图的边进行传播，直到它传染了 整个人群，或在传染了部分人群后逐渐消失。 图 1 在不改变网络图中顶点或边的数量的情况下，在规则环形网络和随机网络之间插入随机改写连线过 程。我们从有 n个顶点的环形开始，每个顶点由无向边连到它的 k个最近的邻点。为清楚起见，在这里的 示例中 n=20，k=4,而大得多的 n和 k用在本文的其它地方。我们选择一个顶点和一条边顺时针方向连到离 2 

它最近的邻点。我们以概率 p重新连接这条边到一个在整个环上随机选择的顶点，连接时不允许出现重复 的边；如果有重复的边，就不连接这条边。我们重复这一改写连线过程，顺时针方向沿环移动，依次考虑 每一个点直到一圈完成。然后，我们考虑连接该顶点到离它顺时针方向次近的邻点的那些边。像前面一样， 我们以概率 p随机为这些边的每一条重新连线，继续这一过程，绕环旋转并且每一圈之后考虑向外面更远 的邻点连接，直到原来网络的每条边都已经被改写完毕。(因为在整个图中有 nk/2 条边，所以 k/2 圈之后 重新连线过程结束。)在不同 p值条件下的三个连线结果如图所示。对于 p=0,原始环不变；随着 p值的增 加，网络图变得越来越紊乱直到 p=1,所有的边都是随机重新连线的。我们的一个主要结论是对于 p值的中 间值，曲线图是一个小世界网络：像规则网一样高度集群，却像随机网一样有较短的特征路径长度。(见图 2) 图 2 图 1 中所描绘的随机重新连线的网络图族的特征路径长度L(p)和集群程度C(p)。这里L被定义为两 顶点之间最短路径边的数量，是所有两顶点之间最短路径边的平均值。集群程度C(p)定义如下。假定每一 个点v有kv个邻点；于是在它们之间最多可以存在kv(kv-1)/2 条边 (这种情况发生在当v的每一邻点都连到 每一个v的其它邻点时)。以Cv表示实际存在的边与允许存在的边的比值。定义C为所有v的Cv的平均值。对于 朋友关系网络，这些统计结果有直观意义：L是在连结两个人的最短链中具有朋友关系的平均数量；Cv反映 的是V的朋友在多大程度上相互之间也是朋友；这样C度量的就是一个典型朋友关系中的集群性。数字中显 示的数据是图 1 所描绘的重新连线过程 20 个随机实现的平均值，并且已经被一个规则网络的L(0)和 C(0) 值规范化。所有的网络图有n=1,000 个点，并且每个顶点平均有k=10 条边。我们注意到一个对数水平的标 度被用于解决L(p)值的快速下降，相当于开始表现出小世界现象。在这一下降过程中，对于规则网络来说 C(p)几乎保持不变，这标志着在局部层次上向小世界网络的转变几乎是无法觉察的。 由此出现了两种结果。第一种，在疾病传染了一半人群时的临界传染性rhalf对于小p值来 说急速下降(图 3a)。第二种，不管其结构如何，对于一种有足够的传染性以传遍整个人群 的疾病，整个传染需要的时间T(p)类似于L(p)曲线(图 3b)。这样，传染性疾病在小世界网 络中预计传播得更容易、更快；令人吃惊的和不太明白的一点是为什么使世界变小只需要少 数捷径。 我们的模型在一些重要方面与其它疾病传播网络模型不同20-24。所有的模型显示出网络 结构影响疾病传输的速度和程度，但我们的模型却阐明动力学过程可作为一个结构的明晰函 数(图 3),胜过一些特殊拓扑结构，比如随机网络图、星型结构和链表结构20-23。在与本文紧 密相关的工作中，Kretschmar和Morris24已经揭示出协作伙伴数量的增加能显著加速一种沿 图的边传播的性传染疾病的传播速度。所有这些图都是不连通的，因为它们把每个人的合作 伙伴固定在k=1 时的平均数。协作伙伴数量的增加通过图的最大连通分支点数的增加而形成 更快的传播速度。反之，我们所有的图都是连通的；因此在传播动力学中的预计变化是由微 妙的结构特征引起的，而不是由于连通性的变化。此外，协作伙伴数量的变化对一个个体是 显而易见的，然而对引起小世界的转变却不易被发现。 3 

图 3 一个简单疾病传播模型的模拟结果。这一群体结构是由图 1 中按照随机连线方式产生的网络图族的一 个。a, 当疾病传染了人群的一半时的临界传染值rhalf随p值而减少。b,最大传染性疾病(r=1)传遍整个人群 需要的时间T(p)，与特征路径长度L(p)具有本质相同的函数形式。即使在原始网络中仅有少数边是随机重 新连线的，全部传染的时间也几乎与随机网络图一样短。 我们也考察了在三个其它动力系统中小世界连通性的效果。在每种情况下，各元素都是 根据图 1 所描绘的图族连接的。(1)对承担密度分类计算任务的元胞自动机25，我们发现运行 在小世界网络图上的简单“多数规则”胜过运行在环型网格上所有已知的人工和遗传算法产 生的规则。(2)在一个网络图上进行多人博弈“囚徒困境”的迭代时，我们发现随着捷径比 例的增加，在使用针锋相对26策略的选手群体中很少出现协作。随着p值的增加，从原始合作 /非合作混合进化出合作策略的可能性也随之下降。(3)具有耦合位相振荡器的小世界网络尽 管具有数量级较小的边，却几乎与在平均场模型2中一样容易同步。如果大脑具有小世界结 构似乎是真实的话，这一结果或许与在视觉皮层27中观察到的广泛分离的神经细胞的同步是 相应的。 我们希望我们的工作能刺激小世界网络的深入研究。小世界网络同时具有特征路径长度 短和集群程度高的特点，它们并不能从规则网络或随机网络中推导出来。尽管小世界的体系 结构现在还没有得到太多的关注，我们认为它可能会在生物系统、社会系统和人造系统中普 遍存在，而且通常具有重要的动力学地位。 收稿日期：1997-11-27; 接受日期：1998-04-06. 参考文献及致谢见原文 4