Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-14T08:12:43.629Z Has data issue: false hasContentIssue false
  • English
  • Français

Efficient routeing in Poisson small-world networks

Part of:Graph theoryGeometric probability and stochastic geometryAlgorithms - Computer Science

Published online by Cambridge University Press:  14 July 2016

M. Draief and
A. Ganesh
M. Draief*
Affiliation:
University of Cambridge
A. Ganesh*
Affiliation:
Microsoft Research
*
∗ Postal address: Statistical Laboratory, Centre for Mathematical Sciences, University of Cambridge, Wilberforce Road, Cambridge CB3 0WB, UK. Email address: m.draief@statslab.cam.ac.uk
∗∗ Postal address: Microsoft Research, 7 J J Thomson Avenue, Cambridge CB3 0FB, UK. Email address: ajg@microsoft.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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 -α, of the distance, r, between them. Kleinberg showed that greedy routeing is efficient if α = d and that there is no efficient decentralised routeing algorithm if α ≠ 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.

Keywords

Small worldrouteing

MSC classification

Primary:60D05: Geometric probability and stochastic geometry68W15: Distributed algorithms
Secondary:05C80: Random graphs

Information

Type
Research Article
Information
Journal of Applied Probability , Volume 43 , Issue 3 , September 2006, pp. 678 - 686
Copyright
© Applied Probability Trust 2006 

References

Barbour, A. D. and Reinert, G. (2001). Small worlds. Random Structures Algorithms 19, 54–74.CrossRefGoogle Scholar
Benjamini, I. and Berger, N. (2001). The diameter of long-range percolation clusters on finite cycles. Random Structures Algorithms 19, 102–111.CrossRefGoogle Scholar
Benjamini, I., Kesten, H., Peres, Y. and Schramm, O. (2004). Geometry of the uniform spanning forest: transitions in dimensions 4,8,12,…. Ann. Math. 160, 465–491.CrossRefGoogle Scholar
Coppersmith, D., Gamarnik, D. and Sviridenko, M. (2002). The diameter of a long-range percolation graph. Random Structures Algorithms 21, 1–13.CrossRefGoogle Scholar
Erdős, P. and Rényi, A. (1959). On random graphs. I. Publ. Math. Debrecen 6, 290–297.CrossRefGoogle Scholar
Franceschetti, M. and Meester, R. (2003). Navigation in small world networks, a scale-free continuum model. Tech. Rep. UCB/ERL M03/33, EECS Department, University of California, Berkeley.Google Scholar
Kleinberg, J. (2000). The small-world phenomenon: an algorithmic perspective. In Proc. 32nd Annual ACM Symp. Theory Comput., ACM, New York, pp. 163–170.Google Scholar
Milgram, S. (1967). The small world problem. Psychology Today 2, 60–67.Google Scholar
Penrose, M. (2003). Random Geometric Graphs. Oxford University Press.CrossRefGoogle Scholar
Sharma, G. and Mazumdar, R. R. (2005). Hybrid sensor networks: a small world. In Proc. 6th ACM Internat. Symp. Mobile Ad Hoc Networking Comput., ACM, New York, pp. 366–377.Google Scholar
Watts, D. J. and Strogatz, S. H. (1967). Collective dynamics of small world networks. Nature 393, 440–442.CrossRefGoogle Scholar