On the searchability of small-world networks with arbitrary underlying structure
On the searchability of small-world networks with arbitrary underlying structure
复制标题
DOI：
10.1145/1806689.1806744
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
P. Fraigniaud;George Giakkoupis
中科院分区：
文献类型：
--
作者：
P. Fraigniaud;George Giakkoupis
在回顾上世纪60年代的“小世界”实验时，克莱因伯格观察到，个体在任何两个人之间都能非常有效地构建短链的熟人，他提出了一个数学模型来解释这一现象。在这个模型中，个体是一个基本图的节点，正方形网格，捕捉社会网络的底层结构；这个基本图被从每个节点到该节点的几个远程接触点的附加边扩充，这些接触点是根据一些基于距离的自然分布选择的。在这个增广图中，贪婪搜索算法只需要图大小的多对数步数。在这项工作之后，几篇论文研究了底层结构和产生高效分散搜索的远程连接之间的相关性，将Kleinberg的结果推广到更广泛的底层结构类别，如有界加倍维的度量和次要排除图。我们主要讨论任意基图的情况。我们表明，对于与社交网络上的经验观察相一致的简单远程接触分布，贪婪搜索的轻微变化，只有在向目标产生足够的进展时，下一跳才会到达一个遥远的节点，不需要(1)步，其中$n$是节点的数量。准确地说，任何源-目标对的期望步数最多为2(log n)1/2+o(1)。这个边界几乎与最著名的Ω（2√log n）步长的下界相匹配，它适用于一般类型的搜索算法。在社会网络的背景下，我们的结果可以解释为：无论社会网络的底层结构如何，个人都可以在人与人之间构建短链。
Revisiting the "small-world" experiments of the '60s, Kleinberg observed that individuals are very effective at constructing short chains of acquaintances between any two people, and he proposed a mathematical model of this phenomenon. In this model, individuals are the nodes of a base graph, the square grid, capturing the underlying structure of the social network; and this base graph is augmented with additional edges from each node to a few long-range contacts of this node, chosen according to some natural distance-based distribution. In this augmented graph, a greedy search algorithm takes only a polylogarithmic number of steps in the graph size. Following this work, several papers investigated the correlations between underlying structure and long-range connections that yield efficient decentralized search, generalizing Kleinberg's results to broad classes of underlying structures, such as metrics of bounded doubling dimension, and minor-excluding graphs. We focus on the case of arbitrary base graphs. We show that for a simple long-range contact distribution consistent with empirical observations on social networks, a slight variation of greedy search, where the next hop is to a distant node only if it yields sufficient progress towards the target, requires no(1) steps, where $n$ is the number of nodes. Precisely, the expected number of steps for any source-target pair is at most 2(log n)1/2+o(1). This bound almost matches the best known lower bound of Ω(2√log n) steps, which applies to a general class of search algorithms. In the context of social networks, our result could be interpreted as: individuals may well be able to construct short chains between people regardless of the underlying structure of the social network.