|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
27 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Networks become navigable as nodes move and forget | | Augustin Chaintreau
; Pierre Fraigniaud
; Emmanuelle Lebhar
; | | Date: |
3 Mar 2008 | | 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. | | Source: | arXiv, 0803.0248 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER