Kleinberg, J. (2000). The small-world phenomenon: an algorithmic perspective. In Proc. STOC 2000, pp. 163–170. DOI 10.1145/335305.335325
Key takeaways
Read in full (NOTE-923). On an n × n lattice where each node also gets q long-range links drawn with probability proportional to d^(−r), short paths exist for r = 0, but no algorithm that sees only the links of nodes the message has visited finds them faster than about n^(2/3) steps in expectation. At r = 2 the greedy rule (pass to the contact nearest the target in lattice distance) delivers in O((log n)²) expected steps (proved for p = q = 1); for 0 ≤ r < 2 every such algorithm needs Ω(n^((2−r)/3)) and for r > 2 Ω(n^((r−2)/(r−1))). So efficient decentralized search depends on how the long-range links are distributed relative to the lattice, not on the links’ existence or on the graph’s diameter. The k-dimensional version (r = k) is stated without proof, and the model is a lattice with a known distance that every node can compute to the target.
Why this is here
CLAIM-310 (arrangements, not descriptions): within a family of inverse-power-law long-range links on a lattice, greedy routing finds short paths only at one exponent, so navigability depends on the arrangement of links. It also needs every node to compute its distance to the target in shared coordinates, and the proofs are for two dimensions.