程序设计导论：Python语言实践

4.5.5　小世界图

科学家已经确定了出现在自然和社会科学的许多应用中一类特别有趣的图。小世界图（Small-world graph）具有如下三个特征：

·稀疏性：顶点的数量远远小于边的数量

·平均路径长度短：如果随机选择两个顶点，它们之间的最短路径长度比较短

·局部聚类性：如果两个顶点都是第三个顶点的邻居，则这两个顶点很可能彼此也是邻居

我们称满足上述三个特性的图具有“小世界现象”。术语“小世界”是指大多数的顶点同时具有局部聚类性和到其他顶点短距离的概念。修饰词“现象”是指实际情况中出现的许多图具有稀疏性，呈现出局部聚类性，并具有短路径的令人意外的事实。除了刚刚讨论的社交关系应用，小世界图还被用于研究产品市场和创意，声望和时尚的形成和传播，互联网的分析，安全点到点网络的构建，路由算法和无线网络的研发，电力网的设计，人类大脑中信息处理的建模，振荡器相变的研究，传染性病毒的传播（在生物体之间或计算机之间的传播），以及其他许多应用。从20世纪90年代邓肯·沃茨和史蒂芬·斯托加茨开创性的工作开始，科学家们在量化小世界现象上进行了大量的研究。

这种研究的一个关键问题是：给定一个图，我们如何判断它是否为小世界图？为了回答这个问题，我们一开始时即强制设定图的规模比较大（例如，1000个顶点或以上），且图是连接的（即每两个顶点对之间存在若干连接路径）。然后，我们需要为每个小世界属性设置具体的阈值：

·稀疏性：我们规定平均顶点度小于20lgV

·平均路径长度短：我们规定两个顶点之间的平均最短路径长度小于10lgV

·局部聚类性：我们规定一种称为聚类系数（clustering coefficient）的量值应该大于10%

局部聚类性的定义比稀疏性和平均路径长度的定义要复杂些。直观上，一个顶点的聚类系数表示随机选择两个邻居，这两个邻居也通过一条边连接的概率。更准确的含义是，如果一个顶点包含 ...