小世界现象背后的大学问

会员服务 ·

小世界现象背后的大学问

2017 年 9 月 28 日 中科院物理所 杨夕歌

北冥南海纵千貌，五岳三山横云霄。

可汗三征掠西欧，英雄背水环地球。

天地茫茫人海处，蓦然回首已陌路。

山高水远毋烦忧，辗转六度迹可求。

——开场诗

“世界这么大，我想去看看”，几年前那张洒脱而霸气的请假条背后，是人们对这个世界的无尽好奇。但别说环游世界这等美差，就连“环游全国”在古人的笔下却都被悲观成了“颠沛流离”。比如苏东坡足迹走遍天下，在今天看来够发好几百条朋友圈了，但实际上则是居无定所，四处漂泊（可参考小编写苏东坡的文章《苏东坡》）。

苏东坡人生轨迹图

古代交通不发达，游子在外和家人都得靠家书。家书没腿，自己没法跑，只有通过驿站或飞鸽传书的方式方可传达，不像现在，李雷想给韩梅梅发信息只要敲敲键盘动动鼠标就行，还不怕吴彦煮窃取信息（当然这里得假设吴彦煮既没有量子计算机，也不会快速分解大整数），安全又快捷。古人眼里的五湖四海太行王屋，在互联网时代中和隔壁老王家的小小门槛并无二致。互联网在很大程度上增强了人与人之间的联系，世界在屏幕的那一头被浓缩成一个小世界。

说到小世界，多数读者都听说过小世界定律，它又被称作六度分隔理论（Six Degrees of Separation）。这个理论断言，世界上任意两个人之间最多隔了5个中间人（用数学语言，“平均最小路径”为 6）。

李雷可以通过最多五个中间人就能联系到其他任何人（上图中的韩梅梅）

这个定律最神奇的地方在于，它在互联网时代之前就已经存在了！也就是说，在交通不发达的北宋，在海南岛度假的苏东坡也最多只需要五个中间人就能吃到山东武大郎做的烧饼！“江山如画，一时多少豪杰”——在小世界定律下，五个豪杰就能编织出如画的江山。

小世界定律的来源

那么小世界定律是怎么被发现的呢？它最早是由无线电之父马可尼（Guglielmo Marconi，1909年诺贝尔物理学奖）在 20 世纪初所预测[1]，并在 60 年由社会心理学家米尔格拉姆（Stanley Milgram）通过实验所验证。米尔格拉姆的实验思路很简单：

在美国中部地区随机地选择 300 个左右居民，给他们发送附有指令的包裹，希望他们把这个包裹送到波士顿的一个指定目标那里（波士顿很远，多半没人认识这个指定对象）；
包裹当然不能直接送达，只能交给自己认识的人，并且需要标注具体把包裹交给了谁。这样就能统计这个包裹历经多少人之手了。

可想而知，如果收到包裹的人严格遵守指令的话，那么他们就会把包裹交给“更可能认识指定目标”的人，这是实验成功的一大前提。不过愿意乖乖听话的陌生人并不多，最后只有 64 个包裹成功到达指定目标，有效数据不足四分之一。米尔格拉姆发现这 64 个包裹经过的中间人手从 1 人到 10 人不等，中间人的中位数正好是 5（注意，不是平均值），从而“验证”了小世界定律。

严谨的读者们可能早已察觉到这整个验证过程还有诸多值得商榷之处，例如：

这些瑕疵并不妨碍米尔格拉姆的这一实验成为社会学领域的一大经典，因为社会学涉及到的因素太多太多了，实验不可能做到完美。不过需要引起我们注意的，则是如何辨证地看待“小世界定律”——定律（Law）和数学上的定理（Theorem）是完全不同的，前者并不需要严格的证明，只需“大体上成立”即可。再例如牛顿运动定律和哈勃定律等物理定律，都是通过实验观测得到的规律，而没办法用数学的方法严格证明。不过值得一提的是，尽管有的定律例如大数定律（Law of Large Numbers），最初的提出是基于实验，但后来在很多情景下获得了严格的数学证明[3]。

既然小世界定律又很难用严格的数学手段来证明，那么如何使用更有说服力的方法来研究它呢？

图论中的小世界网络

小编在之前的很多文章中都提到过“图论”这一概念（《阿尔法狗vs爱因斯坦》、《星际争霸下》等），足见它在科学界中的重要地位。图（Graph）的概念很简单，无非就是一些节点 V（Node）和连接节点的边（Edge）E 构成的二元组，G = (V, E)。我们很容易想到，社交网络中的个体都可以用节点表示；如果两个个体之间有联系，就用便把他们连起来，这样社交网络就被抽象成了图论的模型。这个看似简单的想法，却在 20 世纪 30 年代以后才逐渐引起人们的关注，比相对论和量子力学的兴起还晚了十多年[4]。

既然社交网络可以通过图表达出来，那么我们很自然会想到用图论来研究小世界现象？1998 年，美国社会学家 Watts 联手数学家 Strogatz 构思出了一个简单实用的图论模型，这在今天被称为 Watts - Strogatz 模型。它的算法如下：

把 N 个节点（n_1, n_2,..., n_N）均匀地排布在一个圆周上，每个节点连接周围最近的 K 个节点（K 一般取做偶数，并且要求 K << N，否则每个节点都和其他太多节点相连，过于外向了）：

此图中节点数 N = 20，每个节点连接 K = 4 个相邻节点
选取一个 [0, 1] 区间的概率 p，让步骤 1 中每一条边（注意这些边都连接相邻节点，长度比较短）都以概率 p 发生“变异”，例如连接节点 n_j 和n_i （i < j）的“短”边变异为连接 n_j 和 n_k（n_k 为任意节点）的“任意长度”边。变异结果如下：

“变异”概率p=0.1后的新网络

如果变异概率为 1，那么小世界网络就变成一团乱麻了：

因为“变异”后既可能生成长边，也可以生成短边，所以还是存在不少连接相邻节点的边

这和小世界定律又有什么关系呢？如果把六度分离现象用图论的语言表述，那么就是小世界图的平均最短路径（Mean Average Path）不超过 6。平均最短路径的精确定义如下：

我们来计算一下在 20 个节点的情况下，不同变异概率 p 下的平均最短路径。使用如下代码（小编使用了 python，其中中名为“networkx”的宏包使得整个过程非常容易实现）：

#!/usr/bin/env python

# -*- coding: utf-8 -*-

import networkx as nx

import numpy as np

import matplotlib.pyplot as plt

def DrawGraph(G,ind,p):       # 画图函数

pos = nx.circular_layout(G) # 排成一圈

nx.draw(G,pos,node_color='b',node_size=50,with_labels=False)

plt.text(-1,1,'p=%f'%(p[ind]))

if __name__ == '__main__':

    # 20个节点, 每个点和附近两个节点相连, 取11个不同p值:

n, k, N = 20, 4, 11

p =np.arange(N)*1./(N-1)

for rep in np.arange(20): # 模拟20个小世界图

foo = 0.

for ind in np.arange(N):

          # 生成小世界网络

G = nx.watts_strogatz_graph(n,k,p[ind])

  # 计算分离节点数的平均值

foo = nx.average_shortest_path_length(G)

   sum += foo*1./20

DrawGraph(G,ind,p) # 画图！

得到了如下散点统计：

一共计算了20个小世界网络的平均最短路径

我们可以看到，在变异概率 p = 0 时，平均最短路径接近 3；而变异概率就算只有 0.1，平均最短路径直接降到了 2.5 以下。如果我们把节点数增加到 200（保持 K = 4 不变），让变异概率从 0 变化到 0.2，就更加符合六度分离现象了：

随着p的增加，平均最短路径从 25 迅速下降，在 p 约为 0.125 时接近 6

或许有的读者会对这个简单的模型产生疑问：真实的社交网络真是如 Watts 和 Strogatz 所描述的那样吗，要知道现实中的社交圈是非常复杂的！所以在 Watts 和 Strogatz 以后（也就是近 20 年左右）又涌现出了许多其他小世界模型，例如考虑了自相似效益（Self-Similarity，这一概念最早是从数学中的分形理论中出现的，随后迅速发展为物理学和社会经济学中的一个重要思想，小编以后还会重点介绍这一思想[5]）的 Barabási–Albert 模型[6]，以及 Kleinberg 为了更方便地计算平均最短路径，站在数学的角度将上述模型推广了出去[7]。关于小世界网络的研究才刚刚起步，读者们甚至可以按照这个思路建立自己喜欢的模型，感受感受这一新兴领域。

Kleinberg 模型是二维格点上的网络模型，N 个节点的 Kleinberg 模型平均最短路径为(log(N))^2[7]

不仅仅是社交网络

或许 Watts 和 Strogatz 不会想到，他们在 20 年前建立的模型不仅引起了社会学家的关注，而且还引起了其他不同学科的广泛关注。例如图论在生命科学中的应用，大致总结如下：

生物问题中涉及到的图论（网络）模型都非常复杂，节点非常多。但我们都知道，生命的自我调节能力非常高效——小编认为，我们每天的喜怒哀乐悲欢离合本质上都是因为受到环境影响后，神经元、基因调节和新陈代谢三大复杂网络交互影响而产生的宏观效应（欢迎读者们提出自己的想法）。或许小世界现象理论能够较好地解释，生命为什么会能高效地“摆布”这么多的节点，例如文献[8]总结了小世界模型在神经元建模中的应用。

物理学家们则对小世界现象另有想法。英国物理学家、复杂网络理论奠基人马克∙纽曼（Mark Newman，统计物理出身）发现了相变理论中自发性对称缺失（Spontaneous Symmetry-Breaking，当温度跨域一个临界值时，系统稳定性发生变化）和小世界网络的高聚类特性（High-Clustering，例如社交网络中的朋友圈就是一个 cluster）颇为相似，从而把两者联系了起来[9]。

小世界网络和凝聚态现象（相变的一种结果）之间都有聚类的情况发生

凝聚态物理是现代物理学的一大主流，它和相变现象紧密相连。和生命科学中的图论模型一样，相变理论中也有许多离散模型，例如 Ising 模型（最初用来研究铁磁系统磁性突然消失的奇特现象）、XY 模型（可以模拟液晶、He-3超流性相变等薄层物质的相变，导致了2016年诺贝尔物理学奖的诞生）和更加一般的海森堡模型等，这些概念小编以后会继续进行介绍。

和生物中的各种复杂图论模型相比，离散相变模型主要研究晶体的相变，因此节点往往都建立在规则的格点之上；但从小世界网络的角度出发，我们可以看到相变模型和各种生物网络模型之间的诸多相似之处。而找到这些不同现象背后的共性，还需要靠数学作为主要工具，例如马天和汪守宏的著作[10]就是对这些现象的一个总结，尽管他们采用的是微分方程的建模方法（这是连续建模方法，不同于离散建模，两种方法各有优缺点）。

总结

小世界网络能解释的现象还有很多很多，例如 p2p 网络的搭建、学术圈的建立和发展、总统选举的投票情况分析等，在文献[9]中都有介绍。

运用小世界模型的思想，我们可以更有效地搭建 p2p 网络[11]

在数学领域，图论已经存在数百年之久了，这个方向在国内数学系似乎并不太受到重视。但随着不同分支间的相互融合与网络时代的信息多元化趋势，图论的正在日渐体现出它的价值。随机图论（Random Graph，图论+概率论）、拓扑数据分析（Topological Data Analysis，图论+代数拓扑+黎曼几何）、热带几何（Tropical Geometry，图论+代数几何，无需使用范畴论的语言）这些近期涌现出来的数学分支，正在受到越来越多的关注，而它们的基础都是图论。

新生事物总是会受到不少质疑，许多数学家对这些新兴学科并不买账，部分原因是这些学科的基础“太过于简单”。不过小编一直相信，真正好的数学应该是简洁、美观而且具有高度普适性的，而并非一味的抽象和简单问题复杂化。就像 Watts-Strogatz 的小世界模型那样，非常简单的理论基础就能解释很多复杂的自然现象。

最后欢迎读者们各种留言、讨论、吐槽以及质疑！

不同 p 值下的小世界网络

参考文献：

[1] Guglielmo Marconi, 1909, Nobel Lecture, Wireless telegraphic communication.

[2] Travers, Jeffrey & Stanley Milgram. 1969. "An Experimental Study of the Small World Problem." Sociometry, Vol. 32, No. 4, pp. 425-443.

[3] https://en.wikipedia.org/wiki/Law_of_large_numbers#cite_note-1.

[4] Watts, D. J., Strogatz, S. H. (1998). "Collective dynamics of 'small-world' networks". Nature. 393 (6684): 440–442.

[5] Mandelbrot, Benoit B. (1982). The Fractal Geometry of Nature.

[6] Albert, Réka; Barabási, Albert-László (2002). "Statistical mechanics of complex networks". Reviews of Modern Physics. 74 (1): 47–97. Bibcode:2002RvMP...74...47A.

[7] https://courses.cs.washington.edu/courses/cse522/05au/martel-smallworld.pdf.

[8] arXiv:1608.05665.

[9] https://arxiv.org/pdf/cond-mat/0303516.

[10] Tian Ma and Shouhong Wang, Phase Transition Dynamics, Springer, pp 555, 2013.

[11] Hui, K.Y., Lui, J.C., & Yau, D.K. (2004). Small world overlay P2P networks. IWQoS.