Efficient routeing in Poisson small-world networks

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.