Efficient routeing in Poisson small-world networks

M Draief, AJ Ganesh

Research output: Contribution to journalArticle (Academic Journal)peer-review

19 Citations (Scopus)


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 contributionEfficient routeing in Poisson small-world networks
Original languageEnglish
Pages (from-to)678 - 686
Number of pages9
JournalJournal of Applied Probability
Volume43 (3)
Publication statusPublished - Sep 2006

Bibliographical note

Publisher: Applied Probability Trust


Dive into the research topics of 'Efficient routeing in Poisson small-world networks'. Together they form a unique fingerprint.

Cite this