Networks Become Navigable as Nodes Move and Forget

Augustin Chaintreau Pierre Fraigniaud 1, 2 Emmanuelle Lebhar 1, 2
2 GANG - Networks, Graphs and Algorithms
LIAFA - Laboratoire d'informatique Algorithmique : Fondements et Applications, Inria Paris-Rocquencourt
Abstract : We propose a dynamical process for network evolution, aiming at explaining the emergence of the small world phenomenon, i.e., the statistical observation that any pair of individuals are linked by a short chain of acquaintances computable by a simple decentralized routing algorithm, known as greedy routing. Previously proposed dynamical processes enabled to demonstrate experimentally (by simulations) that the small world phenomenon can emerge from local dynamics. However, the analysis of greedy routing using the probability distributions arising from these dynamics is quite complex because of mutual dependencies. In contrast, our process enables complete formal analysis. It is based on the combination of two simple processes: a random walk process, and an harmonic forgetting process. Both processes reflect natural behaviors of the individuals, viewed as nodes in the network of inter-individual acquaintances. We prove that, in k-dimensional lattices, the combination of these two processes generates long-range links mutually independently distributed as a k-harmonic distribution. We analyze the performances of greedy routing at the stationary regime of our process, and prove that the expected number of steps for routing from any source to any target in any multidimensional lattice is a polylogarithmic function of the distance between the two nodes in the lattice. Up to our knowledge, these results are the first formal proof that navigability in small worlds can emerge from a dynamical process for network evolution. Our dynamical process can find practical applications to the design of spatial gossip and resource location protocols.
Complete list of metadatas

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/inria-00257962
Contributor : Emmanuelle Lebhar <>
Submitted on : Thursday, February 21, 2008 - 11:02:28 AM
Last modification on : Friday, January 4, 2019 - 5:33:21 PM
Long-term archiving on : Thursday, May 20, 2010 - 11:08:24 PM

File

MobilityArxiv.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00257962, version 1

Collections

Citation

Augustin Chaintreau, Pierre Fraigniaud, Emmanuelle Lebhar. Networks Become Navigable as Nodes Move and Forget. [Research Report] 2008, pp.19. ⟨inria-00257962⟩

Share

Metrics

Record views

370

Files downloads

230