论文标题
用道路网络对小世界现象进行建模
Modeling the Small-World Phenomenon with Road Networks
论文作者
论文摘要
可以追溯到1960年代社会心理学家斯坦利·米尔格拉姆（Stanley Milgram）的两个著名实验，小世界现象是所有人都通过短暂的熟人连接的想法，这些熟人可用于路由信息。随后的许多论文试图对这一现象进行建模，其中大多数集中在熟人的“短链”上，而不是其有效路由信息的能力。在本文中，我们研究了美国道路网络的小世界可通道性，其目的是提供一个模型，该模型解释了如何使用美国道路沿着短路路线路由原始的小世界实验中的消息。为此，我们介绍了邻里优先依恋模型，该模型结合了Kleinberg的模型和Barabási-Albert模型的元素，从而根据网络中顶点的学位和（道路网络）距离选择了远距离链接。我们通过运行分散的路由算法来凭经验评估所有三个模型，在该算法中，每个顶点只有对自己的邻居的了解，并发现我们的模型在平均跳跃长度方面都优于这两个模型。此外，我们的实验表明，与Barabási-Albert模型相似，我们的模型生成的网络是无标度的，这可能是原始小世界实验中熟人链接的更现实的表示。
Dating back to two famous experiments by the social-psychologist, Stanley Milgram, in the 1960s, the small-world phenomenon is the idea that all people are connected through a short chain of acquaintances that can be used to route messages. Many subsequent papers have attempted to model this phenomenon, with most concentrating on the "short chain" of acquaintances rather than their ability to efficiently route messages. In this paper, we study the small-world navigability of the U.S. road network, with the goal of providing a model that explains how messages in the original small-world experiments could be routed along short paths using U.S. roads. To this end, we introduce the Neighborhood Preferential Attachment model, which combines elements from Kleinberg's model and the Barabási-Albert model, such that long-range links are chosen according to both the degrees and (road-network) distances of vertices in the network. We empirically evaluate all three models by running a decentralized routing algorithm, where each vertex only has knowledge of its own neighbors, and find that our model outperforms both of these models in terms of the average hop length. Moreover, our experiments indicate that similar to the Barabási-Albert model, networks generated by our model are scale-free, which could be a more realistic representation of acquaintanceship links in the original small-world experiment.
