New Proof Shows Geometry Alone Enables Ultra-Fast Routing in Random Networks

Decentralized routing in large networks typically relies on additional information, such as vertex weights, to find short paths. Greedy routing in GIRGs, a model that explains the algorithmic small-world phenomenon, achieves ultra-short paths of length Θ(log log n) but assumes knowledge of vertex weights – a restrictive assumption in many real-world scenarios. In a new paper on arXiv, researchers from multiple institutions ask whether the network's geometry alone (i.e., distances between nodes) is sufficient for efficient navigation.

The authors prove that geometric routing – using only distances – succeeds with constant probability for a wide range of parameters. The paths found are asymptotically optimal, matching greedy routing's Θ(log log n) length. The analysis reveals a two-phase trajectory: first, a rapid ascent toward high-weight core nodes (the heavy vertices), then efficient navigation to the target. This shows that geometry implicitly guides routing through the network's high-weight core, eliminating the need for explicit weight information. The results are significant for distributed networks where weight metadata may be unavailable or costly to maintain.