Open Research Index

Geometric Routing in Geometric Inhomogeneous Random Graphs

Yu-Cheng Chiu, Marc Kaufmann, Kostas Lakis, Ulysse Schaller

arXivarxiv/2606.02856Jun 1, 2026math.PRscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2606.02856
curl -X POST /api/v1/records/arxiv/2606.02856/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.02856/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'