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 :
Reports
Complete list of metadatas

Cited literature [12 references]  Display  Hide  Download

https://hal-lara.archives-ouvertes.fr/hal-02101954
Contributor : Colette Orange <>
Submitted on : Wednesday, April 17, 2019 - 9:10:40 AM
Last modification on : Friday, May 17, 2019 - 1:39:20 AM

File

RR2003-55.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02101954, version 1

Collections

Citation

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⟩

Share

Metrics

Record views

4

Files downloads

7