Geometric Routing in Geometric Inhomogeneous Random Graphs
For network scientists studying decentralized navigation in complex networks, this work shows that geometry alone suffices for efficient routing in a realistic random graph model, eliminating the need for weight knowledge.
This paper proves that decentralized geometric routing in Geometric Inhomogeneous Random Graphs (GIRGs) can achieve ultra-short paths of length Θ(log log n) with constant probability, matching the optimal guarantees of greedy routing, without requiring weight information. The result holds for power-law weight exponent τ∈(2,3) and geometric decay parameter α>τ-1.
We present the first rigorous analysis of decentralized geometric routing in Geometric Inhomogeneous Random Graphs (GIRGs), a weight-agnostic variant of the greedy routing protocol. While greedy routing in GIRGs is known to explain the algorithmic small-world phenomenon by finding ultra-short paths of length $Θ(\log \log n)$, it assumes additional knowledge of vertex weights beyond geometry, an assumption that is often restrictive or unavailable. We investigate whether the underlying geometry alone is sufficient for efficient navigation. We prove that for power-law weight exponent $τ\in (2,3)$ and geometric decay parameter $α> τ- 1$, geometric routing succeeds with constant probability and finds ultra-short paths of length $Θ(\log \log n)$, matching the optimal asymptotic guarantees for greedy routing. Our analysis further reveals that, upon success, both protocols follow a similar two-phase trajectory, consisting of a rapid ascent to the heavy vertices, followed by efficient navigation to the target. These results demonstrate that, in the appropriate regime, the network's geometry alone implicitly guides the path to the target through its high-weight core.