← 实验室
ASTERXOR / 实验室

六座桥,让一个世界突然小了很多

地点没有移动,改变的是它们之间要走多少步。

六十个节点组成的圆环,六条金色连接横跨圆心。
人工构造的网络。六条跨越圆环的线是新增连接,不是真实道路或通信线路的测量结果。
实验室ASTERXOR / LEON LEUNG

一条捷径,改变的不只是站在桥头那个人的旅程。

想象六十个站点排成一个圆环,每站只连接左右邻居。去往对面,必须一步一步绕过去。现在往圆环中间加几座桥。圆还是那个圆,移动起来却像换了一个世界。这个小例子解释了为什么连接方式,有时比图上看起来相距多远更重要。

地图告诉你东西在哪里,网络还告诉你哪些移动是可能的。
加桥之前

相邻,是规则,不只是位置

起始图有六十个节点、六十条无向边。每个节点连接圆环上的前一个和后一个节点。每条边的成本都是一跳,不管画出来有多长。这个规则里没有藏着通行时间、拥堵或物理距离,它刻意保持简单。

任意两点之间都可以沿圆环的两个方向走,我们选择较短路线。正好相对的两点,两边都要三十跳;相邻节点只要一跳。单挑一个漂亮例子很容易,因此实验计算了全部 1,770 对不同节点之间的最短路,而不是只挑一条路线展示。

六条额外连接

桥也帮到了离桥头很远的人

新增边连接节点 0–30、5–35、10–40、15–45、20–50、25–55。编号只是人工圆环上的位置,不代表真实地点。总边数变成六十六条,原来的圆环连接仍保留。这一点很重要:增加的是选择,不是强迫大家放弃原路线。

可以先沿圆环走到桥头,过桥,再走到目的地,所以一座桥帮助的不只是两端节点,它也改变了许多其他节点对之间的路线。这六条连接是人为指定的,并不是搜索所有方案后证明最优的布局。

两张环形网络分别展示原始圆环,以及增加六条穿过中央的金色弦后的圆环。
FIG 0160 条边的圆环增加六条指定的对向节点连接。中央线条交叉处不是额外节点,也不是换路口。
测量整张图

平均旅程缩短了七跳

添加连接前,全部 1,770 对节点的平均最短距离约为 15.254 跳,之后约为 8.254 跳。在这个图里,差值恰好是七跳。直径,也就是所有节点对中最大的最短距离,从三十降到十五。两者回答不同问题:一个关注平均,另一个关注最远的一对。

有些节点对改善很多,另一些变化较小,相邻节点仍只需一跳。平均值不保证每个人节省相同步数。因此还应该看距离分布:它展示哪些路线长度变多或变少,比只报一个漂亮的平均改善更完整。

叠加直方图中,圆环距离延伸到 30 跳,新增连接后的距离集中在较短范围,最多 15 跳。
FIG 02全部 1,770 对无序节点的最短跳数。均值从 15.254237 降至 8.254237,直径从 30 降至 15。
新增边的保证

旧路线没有消失

在成本固定的无权图里,新增一条边不会让某对节点的最短距离变大。原来的最佳路线仍然存在,现在只是可能多了更好的选择。检查逐对比较新增前后的距离,而不只比较平均值;同时确认两张图都连通,并且确实只多了六条边。

这个保证依赖模型。现实中,新路开通后司机可能改变路线,拥堵又会改变耗时;通信线路也有容量和延迟。这里都没有模拟。图论结果说明的是固定成本下的可选路径,不是每条新公路都一定让现实系统变好的承诺。

另一个故障测试依次删除六条成本为1的捷径,每次只删一条。完整环仍在,所以60个节点始终连通。均跳数从8.2542升到8.3955,六种情况下直径仍为15。相同删除结果来自这个布局的旋转对称性,不是冗余网络的一般规律。这里“桥”只是捷径的形象称呼;图论中的桥特指删掉会导致图断开的边,这些新增边并不符合该技术定义。

画面不等于成本

长线可以很便宜,也可以很昂贵

六座桥虽然横跨整个圆环,在模型中都只花一跳。它们的收益很大程度来自这个假设。如果跨桥花二十分钟,而圆环相邻边只花一分钟,按时间计算会得到不同故事。网络图容易遮住这种选择,因为眼睛会自然把线的长度当成付出。

思考文档链接、软件组件或交通站点时,也要区分这两件事。问最短路线之前,先确定一条边是什么,成本表示什么。点击更少、换乘更少、耗时更少,是三个不同目标,不能让图上最漂亮的那条线替我们决定。

给线标价

纸上较短的穿越,也可能代价更高

扩展实验保持每条环边成本为1,分别把每条捷径设为1、5、15、30或35,形成五种场景。对全部1,770对重新计算带权最短路,而不是把旧跳数均值简单乘新价格。均成本约为8.2542、10.0847、13.4746、15.2542和15.2542。穿越越贵,收益越弱,尽管网络图外观可以完全不变。边数较少的路径,此时也可能更贵。

成本30时,每条捷径与其两个对径端点之间的30条环边路线打平。任何使用它的路径,都能不增加成本地换成那段环路。脚本确认不只是平均值,而是每对节点都回到纯环的最短成本。涨到35也不会有帮助,因为替代环路更便宜。对路径模型,可以先问盈亏边界:新连接的成本,相比已有路线到底如何?答案需要边权,而不是圆中一条看起来很有气势的线。

捷径成本增加时,平均带权距离回到纯环基准;删一条便宜捷径略增均跳数,但网络仍连通。
FIG 03五种带权成本实测场景,不插值;另检验六种逐条删除捷径的场景。环边始终成本1,删除面板先恢复捷径成本1再删一条。
限定结论

它解释捷径,不替全世界下结论

这个圆环不能证明现实中的人隔着几位朋友,也没有测量互联网性能。真实网络可能有单向边、不同重要性、动态可用性和极不均衡的连接数量。小世界的讨论可以从这样的例子开始,但不能把六十个虚构点当成社会调查。

实验提供的是一种清楚的思考习惯:统计整个网络,公开成本假设,并区分平均改善和每个人的改善。它已经足够有趣,不需要更宏大的宣称。节点一个都没移动,六条连接却改变了数百对节点之间的路线。

留一个想法带走

世界变小,有时不是因为靠得更近,而是因为多了一条更好的连接。