26、网络性能与小世界模型：Freenet案例分析

网络性能与小世界模型：Freenet案例分析

1. 网络分析基础问题

在网络分析和故障排查中，确定是否存在路由以及路由所需的跳数是基本问题。对于去中心化的点对点网络，这两个问题同样重要。第一个问题能让我们知道哪些节点可以通过消息转发路由相互通信，第二个问题则表明实现通信所需的工作量。为了深入理解这些问题，我们先回顾一下信件传递实验，再探讨其对点对点网络的启示。

2. 小世界模型

Milgram的志愿者成功地在看似截然不同的美国乡村和城市之间传递信件，这表明美国的社交网络是连通的。其特征路径长度约为六，即完成一条传递链所需的中间人的中位数。

直观上，如此庞大的网络路径长度应该更长。因为大多数人的社交圈子高度紧密或聚集，也就是你认识的人彼此也大多相识，增加跳数可能不会大幅扩大可触及的人群范围。要突破一个社交圈子、跨越全国并到达另一个圈子，似乎需要大量跳数，尤其是考虑到美国的幅员辽阔。那么，如何解释Milgram的测量结果呢？

关键在于社交网络中连接的分布。在任何社交群体中，一些人相对孤立，带来的新联系人较少，而另一些人则有更广泛的连接，能够充当遥远社交集群之间的桥梁。这些桥梁节点在拉近网络距离方面起着关键作用。例如，在Milgram实验中，四分之一到达目标人物的传递链都经过了一个当地店主，一半的传递链仅由三个人介导，他们共同充当了目标与外界的网关。

研究表明，即使少量桥梁的存在也能显著减少图中路径的长度。Duncan Watts和Steven Strogatz通过研究规则图来进行说明。规则图是由n个顶点组成的环，每个顶点与其最近的k个邻居相连。当n远大于k，且k远大于1时，规则图的路径长度近似为n/2k。例如，当n =