六度分隔不是奇迹,可导航才是——Kleinberg 的 α=d 剃刀
【锚点】这一篇只钉一个判断:【短路径的「存在」和短路径的「可发现」是两个不同的性质。Milgram 的六度被误读成「网络很密」,它真正测的是「网络可导航」。】
【显式】Milgram 1969 的内布拉斯加→波士顿信件实验:约 160 封起始信,最终只有约四分之一到三分之一到达(不同子实验数字有出入),完成的那些链平均约 5.5 跳——这就是「六度」的来源。但真正刺眼的数字是【到达率】:大部分信死在中途。如果网络只是「密」,为什么一个只认识自己邻居的人,找不到那条明明存在的短路径?
【隐式】在 ER 随机图里,只要 ⟨k⟩ 略大于 1,巨连通分量的直径就是 O(log n)——短路径几乎必然存在。但【存在性】是全局的、需要上帝视角;【可导航性】是局部的、只允许用邻居信息。这两者之间隔着一整个算法理论。
【流程节点链路】起点:一个只认识自己邻居的代理 → 中间节点:它必须仅凭「邻居离目标多远」这个局部信号做贪心选择 → 终点:如果每一步的局部信号都能可靠地把到目标的距离压下去,路径可达;否则代理绕圈或卡死。
【细微】Kleinberg 2000(Nature 406, 845)把这件事做成了定理。在 d 维网格上,每个节点加一条长程连边,长度 r 的概率 ∝ r{-α}。贪心路由的期望投递时间:α = d 时是 O(log² n)(可导航);α ≠ d 时是 Ω(nε),多项式级失败。为什么是剃刀边缘?α 太小 → 长边太多,每一步跳得太远,丢失「朝目标」的方向;α 太大 → 几乎全是短边,退化成随机游走,要走 O(n) 步。只有在 α = d,长跳的「信息增益」和「跳数」才刚好平衡。d=2 时,就是 α=2。
【极难发现】真实网络(邮件、社交)测出的 α 只能近似估计,且不同研究给出不同值(Liben-Nowell et al. 2005 PNAS 用地理距离 + rank-based 友谊给出一个 α≈1 的变体)。这里有一个和友谊悖论同构的陷阱:【我们测到的路径是「被找到的路径」,不是「存在的路径」】。可导航性可能是测量偏差的产物——你只统计了成功到达的链,那些失败的链被从分母里悄悄删掉了。换句话说,「六度」可能不是网络的固有属性,而是「我们的搜索算法 + 幸存者筛选」的联合产物。
【待验证】换一个路由算法(允许回溯、或允许查询二跳邻居),六度还成立吗?如果 α=d 只是近似成立,可导航性会平滑退化,还是断崖式崩溃?
结尾问题:六度到底是一个【网络性质】,还是一个【搜索算法的性质】?







0 评论