小世界现象

1967 年，社会心理学家 Stanley Milgram 做了一个著名的实验：让美国内布拉斯加州等地的志愿者把一封信转交给波士顿的一位陌生目标人物，规则是只能寄给自己“直呼其名”的熟人，由熟人继续转寄。在最终送达的 64 封信中，平均转手约 6 次，这就是“六度分隔”（six degrees of separation）说法的来源。2003 年 Dodds、Muhamad 和 Watts 用电子邮件在全球范围重做了实验，起始链条约 2.4 万条，到达的链条很少，但到达的链条长度同样集中在 5–7 步。

为什么路径会这么短？一个粗略的估算：如果每个人认识 100 人，那么 2 步可达 $10^4$ 人，3 步可达 $10^6$ 人，5 步就超过了世界人口。这个“指数扩张”的论证与 ER 随机网络的结论一致：ER 网络的平均路径长度 $L_{\text{rand}} \approx \ln N / \ln \langle k \rangle$。

但这个估算有一个漏洞：现实中你朋友的朋友，很多本来就是你的朋友。三角形闭合（triadic closure）会让第二步、第三步“新认识的人”大量重复，扩张速度远低于 $100^h$。高聚类本应让路径变长——那么社交网络为什么仍然是小世界？这就是 Watts 和 Strogatz 要解决的问题。

短路径存在 ≠ 能找到短路径

Milgram 实验还揭示了一个常被忽略的事实：参与者并不知道整个网络，只能根据“谁离目标更近”的局部信息转发，却仍然找到了短链。Kleinberg（2000, Nature）指出这需要额外的结构条件。他在二维网格上给每个节点加一条长程连接，连到距离为 $r$ 的节点的概率 $\propto r^{-\alpha}$，并让信息按“贪心”规则转发给离目标最近的邻居。结论是：只有当 $\alpha$ 等于空间维数（二维时 $\alpha=2$）时，贪心转发的步数才随 $N$ 呈多项式对数增长；$\alpha$ 偏小（长程边太随机，缺少“方向感”）或偏大（长程边太短）时，步数都随 $N$ 的某个幂次增长。也就是说，可导航的小世界要求长程连接的长度分布与空间（或社会距离）结构相匹配。这一思想后来被用于理解脑网络与分子网络中“局部信息路由”的效率。