Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
Skip to Main content Skip to Navigation

Searching for optimal paths in long-range contact networks.

Abstract : Since Milgram experiment in 1967, that demonstrated the ability of people to find short paths efficiently in networks, based only on their own local view of the network, different models have been proposed to study the ``small world phenomenon''. In 2000, Kleinberg shows that most of the previously known models for small world fail to capture an important feature of the phenomenon: no local information based (i.e., decentralized) algorithm can find short paths in these graphs, when they exists. He then introduces a model composed of a lattice (representing the local acquaintances) augmented with directed links (symbolizing long-range contacts) distributed harmonically. He proposes to model people behavior by the greedy algorithm that forwards the message to the contact (local or long-range) of the current holder, which is the closest to its destination. He shows that this greedy algorithm computes paths of expected length $\Theta(\log^2n)$ between any pair of nodes. The present paper questions the choice of the greedy strategy to model social behavior. We proposes a new strategy in which nodes consult their acquaintances near by, before deciding where to forward the message. Our algorithm presents the same computational characteristics as Kleinberg's original algorithm: uses $\Theta(\log n)$ bits of memory and visits $O(\log^2n)$ nodes. However, it computes much shorter paths, of expected length $O(\log n(\log \log n)^2)$, between any pair of nodes. This algorithm demonstrates that consulting their acquaintances near by, leads to considerable improvements in performances. It also shows that this consultation is less and less useful as one gets closer to the target. As far as we know, this is the first algorithm to ``break the $\Theta(\log^2 n)$ barrier'' for the paths length in Kleinberg's network.
Document type :
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Colette ORANGE Connect in order to contact the contributor
Submitted on : Wednesday, April 17, 2019 - 9:10:40 AM
Last modification on : Saturday, September 11, 2021 - 3:18:55 AM


Files produced by the author(s)


  • HAL Id : hal-02101954, version 1



Emmanuelle Lebhar, Nicolas Schabanel. Searching for optimal paths in long-range contact networks.. [Research Report] LIP RR-2003-55, Laboratoire de l'informatique du parallélisme. 2003, 2+8p. ⟨hal-02101954⟩



Record views


Files downloads