on the searchability of small-world networks with arbitrary underlying structure
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 n o(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.
social networks decentralized search small worlds