2.8 小世界
小世界现象——又称六度分隔，长期以来备受公众关注。小世界现象指出，在地球上任意选择两个人，你会发现他们之间相隔最多6个相识关系（图2-10）。如果说生活在同一个城市里的两个人彼此之间只相隔少数几个相识关系，你可能不会感到吃惊。然而，小世界概念告诉我们，即便是生活在地球上相对方位的两个人，彼此之间也只相隔少数几个相识关系。
图2-10 六度分隔
根据六度分隔理论，来自世界上任何地方的两个人，都可以通过不超过6个相识关系连接起来。例如，虽然萨拉并不认识皮特，但她认识拉尔夫，而拉尔夫认识简，简又认识皮特，因此萨拉和皮特之间相隔3个相识关系，或者说萨拉和皮特是三度分隔的。在网络科学的语言中，六度分隔被称为小世界性质——意味着网络中任意两个节点之间的距离非常小。
在网络科学的语言中，小世界现象意味着，网络中随机选择的两个节点之间的距离很短。这一论断带来了两个问题：怎样才算短，或者说和什么相比是短的呢？如何解释距离短这一现象呢？
这两个问题都可以通过一个简单的计算来回答。考虑一个平均度为
的随机网络，平均情况下每个节点有：
个距离为1的节点（d=1）；
2个距离为2的节点（d=2）；
3个距离为3的节点（d=3）；
……
d个距离为d的节点。
例如，如果≈1000（每个人平均认识的人数），那么从某个人出发距离为2的人数约为106，距离为3的人数大约有10亿人——和全球总人数在一个数量级。
精确地讲，从一个起始节点出发距离不超过d的期望节点数为：
注意，N(d)不能超过网络中的节点总数N。因此，距离不可能取任意大的值。最大距离dmax——又称网络直径，可以通过下面的公式算出：
假设≫1，公式2.15的分子和分母中的（-1）项可以忽略不计，从而有：
因此，随机网络的直径为：
公式2.18是小世界现象的数学表示。关键是对公式2.18的解读：
● 公式2.18给出了网络直径dmax和网络大小N之间的关系。然而，对大多数网络而言，和对网络直径dmax的近似相比，公式2.18更好地提供了两个随机选择节点之间平均距离
的近似（表2-2）。这是因为，dmax往往取决于少数几个极端路径；是关于所有节点对的平均值，受随机波动影响不大。因此，通常情况下，小世界性质定义为：
表2-2 六度分隔
表中给出了10个网络的平均距离和最大距离dmax。最后一列是公式2.19预测的，可以看出它是对实测的一个合理近似。不过，公式2.19的预测并不完美：在下一章我们将看到，对于很多真实网络，公式2.19需要调整。对于有向网络，平均度和路径长度是考虑了边的方向测量出的。
公式2.19刻画了平均距离和网络大小N、平均度之间的依赖关系。
● 一般而言，lnN
N。因此，平均距离对lnN的依赖，意味着随机网络中的距离比网络大小要小多个数量级。因此，“小世界现象”中的“小”是指，平均路径长度或网络直径和网络大小的关系是对数关系。因此，“小”的意思是，正比于lnN，而不是正比于N或者N的幂（图2-11）。
图2-11 为什么小世界令人惊奇？
我们关于距离的直觉大多来自认识规则格子网络中的经验，而格子网络不具有小世界性质：
一维（1D）：对于一维格子（一条长度为N的线），其直径及平均路径长度都和N呈线性关系：dmax~~N。
二维（2D）：对于正方形格子，有dmax~~N1/2。
三维（3D）：对于立方体格子，有dmax~~N1/3。
四维（4D）：通常情况下，对于d维格子，有dmax~~N1/d。
上述多项式依赖关系表明，格子网络的网络直径或平均路径长度随N增长的速度要比公式2.19快得多。这意味着，格子网络中的平均路径长度明显大于随机网络中的平均路径长度。例如，如果社会网络是一个正方形格子（2D），每个人只认识其邻居，那么任意两个人之间的平均距离将大致为（7×109）1/2=83666。即使我们把每个人平均认识的人数从二维格子的4修正为1000，人们之间的平均距离也比公式2.19要高几个数量级。
（a）线性坐标下，格子网络和随机网络中对N的依赖关系。
（b）和（a）相同，不过坐标换成了双对数坐标。
● 公式2.19中的项1/ln意味着，网络越稠密，节点间的距离越小。
● 真实网络中，公式2.19需要进行系统修正。这源于这样一个事实：当d>时，和起始节点距离为d的节点数目迅速减少（进阶阅读2.F）。
我们现在来看一下公式2.19对社交网络意味着什么。全球社交网络中，节点数为N≈7×109，平均度为≈103，因此有：
因此，地球上所有人只相隔3~4个相识关系[20]。公式2.20的估计可能比人们经常提到的“六度”更接近真实值（边栏2.7）。
边栏2.7
六度：实验验证
关于小世界现象的第一个实证研究发生在1967年。斯坦利·米尔格拉姆在波普尔和科亨[20]的工作基础上设计了一个实验，来测量社会网络中的距离[24]，[25]。米尔格拉姆选择了波士顿的一位股票经纪人和马萨诸塞州沙伦神学院的一位学生作为目标，然后在威奇托和奥马哈随机选择一些居民参与实验，给他们每人发送一封信，信的内容包括对此项实验研究目的简要介绍，以及目标对象的照片、姓名、地址和其他相关信息。实验要求每位参与者从他的朋友、亲戚或熟人中选出他认为最有可能认识目标对象的人，然后将信转给他。
几天后，第一封信到达了，只经过了两个链接。最终，全部296封信中有64封回来了。不过，有些信则经过了多达10余个链接才送到目标手中[25]。使用这些成功返回的信件，米尔格拉姆得以算出将信从原发者送达目标对象中间需要经过的人数（图2-12a）。他发现，中间所经历人数的平均值为5.2，这个相对而言很小的数字，非常接近弗里杰什·考林蒂（Frigyes Karinthy）于1929年做出的判断（边栏2.8）。
米尔格拉姆没有人们之间的相识关系网络，因此他的实验无法得到实验参与者和目标对象之间真实距离。今天，Facebook拥有了有史以来世界上最大的社交网络地图。使用Facebook 2011年5月的社交网络——包括7.21亿个活跃用户和680亿个对称朋友关系，研究人员发现这些用户之间的平均距离是4.74（图2-12b）。因此，研究发现的“四度分隔”[18]，比米尔格拉姆的六度[24]，[25]更接近公式2.20的预测。
图2-12 六度？从米尔格拉姆到Facebook
（a）在米尔格拉姆的实验中，296封信中的64封到达了收件人手中。图中给出了这64封邮件经过的中间人数的分布。从中可以看出，有些信只经过了一个中间人，有些信则经过了多达10个中间人。该分布的平均值为5.2，这表明平均需要约6次“联络”才能使信到达收件人那里。20年后，剧作家约翰·格尔将这一现象称为“六度分隔”[25]。
（b）Facebook所有用户间的平均距离分布以及美国Facebook用户间的平均距离分布。基于Facebook社交网络的节点数N和链接数L，公式2.19预测，社交网络中人们的平均距离约为3.9，和文献[18]中报道的四度相差不大。
我问一位智者，按照实验中的方式从内布拉斯加州到沙伦，需要经历多少个中间人，他回答说，将需要不少于100个人。
——斯坦利·米尔格拉姆，1969
关于随机网络的小世界性质，包括公式2.19的结论，均出自由曼弗雷德·科亨和伊锡尔·德索拉·普尔合著的一篇并不怎么出名的论文。论文中给出了小世界性质的数学建模，并深入讨论了小世界性质的社会学意义。这篇论文启发了著名的米尔格拉姆实验（边栏2.6），而米尔格拉姆实验又带来了“六度分隔”的说法。
边栏2.6
十九度分隔
万维网中，需要多少次点击才能从一个随机选择的网页到达另外一个随机选择的网页呢？回答该问题的困难之处在于，我们没有完整的万维网地图，只有这个地图的采样。不过，我们可以不断增加万维网采样的大小并测量其平均路径长度，从而对整个万维网的平均路径长度进行估计，这一过程被称为有限标度法。测量结果表明，万维网的平均路径长度和万维网大小之间的关系为[21]：
1999年时，万维网大约有8亿个网页[22]，根据上述公式可以计算出当时万维网的平均路径长度为≈18.69。换句话说，1999年时两个随机选择的页面之间平均相隔19次点击，这被称为十九度分隔。随后，在一个有2亿个网页的万维网采样上得出的测量结果是≈16[23]，和公式预测的≈17很接近。目前，万维网估计有大约N~1012个网页，相应地有≈25。因此，不是固定不变的，而是随着网络大小的增加而增加。万维网的这个平均路径长度25比社会网络中众所周知的六度要大得多（边栏2.7）。这个差距很容易理解：万维网的平均度比社会网络要小，而大小却比社会网络大，根据公式2.19，这两方面使得万维网的直径要更大些。
虽然小世界性质是在社会系统中被发现的，但它不只适用于社交网络（边栏2.6）。为了阐明这一点，我们在表2-2中将几个真实网络的平均路径长度和公式2.19的预测值进行了对比。对比发现，尽管这些网络形态多样、大小N以及平均度相差很大，公式2.19也给实际观测到的提供了一个很好的近似。
总之，小世界性质不仅引发了公众的想象（边栏2.8），在网络科学中也起到了重要作用。小世界现象在随机网络模型背景下可以得到非常好的解释：小世界现象源于这样一个事实：从某个节点出发，距离为d的节点个数随着d指数增长。我们在接下来的章节中将看到，真实网络和公式2.19之间存在系统性偏差，这迫使我们用更准确的预测取代公式2.19。不过，随机网络模型提供的关于小世界现象起源的直观认识在真实网络中仍然是有效的。
边栏2.8
万维网的十九度分隔
