计算机科学导论：跨学科方法

4.5　案例研究：小世界现象

我们用数学模型图（graph）来研究实体间成对性质。图能够帮助我们研究自然世界，也对我们更好地理解和改进我们创建的网络非常重要。在过去的一个世纪里，从神经生物学的神经系统模型，到医学传染病的传播，再到电话系统的发展，图在科学和工程领域发挥了重要的作用，其中也包括了对互联网发展的推动。

某些图显示了一个被称为小世界现象（small-world phenomenon）的特定属性。你可能熟悉这个属性，有时它也被称为六度分隔（six degrees of separation）。其基本思想是：即使我们每个人认识的熟人相对较少，但想在世界上任意两个陌生人之间建立联系，所需要的人际链条并不长（六度分隔）。这一假设在20世纪60年代由斯坦利·米尔格拉姆（Stanley Milgram）通过实验验证，并在20世纪90年代由邓肯·瓦茨（Duncan Watts）和斯蒂芬·斯特罗格茨（Stephen Strogatz）建立了数学模型。近年来，这一原理在各种各样的应用中被证明是非常重要的。科学家对小世界图感兴趣，因为它们模拟了自然现象；工程师对此也有兴趣，因为利用小世界图的自然属性可以更好地构建网络。

在本节中，我们将讨论小世界现象和图的基本计算问题。事实上，这个简单的问题：

一个既定的图是否表现出小世界现象？

带来的重大计算任务是巨大的。为了解决这个问题，我们将研究一个图处理所需的数据类型和几个有用的图处理客户程序。具体来说，我们将考察一个计算最短路径（shortest paths）的客户程序，这个计算本身有着很多重要的应用。

本节另一个主题是我们一直在研究的算法和数据结构，它们在图处理中起着核心作用。事实上，你会发现本章前面介绍的几种基本数据类型可以帮助我们开发优雅、高效的代码，以研究图的属性。 ...