Abstract
In a recent paper, Kleinberg (2000) considered a small-world network model consisting of a d-dimensional lattice augmented with shortcuts. The probability of a shortcut being present between two points decays as a power, r(-alpha), of the distance, r, between them. Kleinberg showed that greedy routeing is efficient if alpha = d and that there is no efficient decentralised routeing algorithm if alpha not equal d. The results were extended to a continuum model by Franceschetti and Meester (2003). In our work, we extend the result to more realistic models constructed from a Poisson point process wherein each point is connected to all its neighbours within some fixed radius, and possesses random shortcuts to more distant nodes as described above.
Translated title of the contribution | Efficient routeing in Poisson small-world networks |
---|---|
Original language | English |
Pages (from-to) | 678 - 686 |
Number of pages | 9 |
Journal | Journal of Applied Probability |
Volume | 43 (3) |
DOIs | |
Publication status | Published - Sept 2006 |