Long-range links with P(r) ∝ r−α — only α=2 allows efficient decentralized routing in 2D
Hops to target: — |
α = 2.0 |
Grid: 14×14
Kleinberg (2000): Each node has short-range links to neighbors + one long-range link sampled with probability ∝ r−α.
Greedy routing always forwards to the neighbor closest to the target. At α=2 (matching the spatial dimension d=2), expected path length is O(log²N).
For α=0 (uniform random) or α > 2, routing degrades dramatically — the optimal exponent is exactly the grid dimension.