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

网络性能分析：小世界模型与Freenet网络应用

1. 网络分析基础问题

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

2. 小世界模型

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

直观上，如此庞大的网络的路径长度应该更长。大多数人的社交圈子高度紧密或聚集，即你认识的人大多也相互认识，你朋友的很多朋友你也已经认识。因此，增加跳数可能不会大幅增加可触及的人数。要突破一个社交圈子，跨越整个国家并到达另一个圈子，似乎需要大量的跳数，尤其是考虑到美国的规模。那么，如何解释Milgram的测量结果呢？

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

研究表明，即使少量的桥梁也能显著减少图中路径的长度。Duncan Watts和Steven Strogatz在《自然》杂志上发表的一篇论文中，通过研究规则图来阐述这一点。规则图是由n个顶点组成的