Metraipolis › archive › dc_7b6a79ebafb2
Navigating Small-World Networks with Distance Predictions — arXiv:2609.10885
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.10885
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T05:44:47.862Z
- SHA-256 of the archived text
7b2b8c02b487f3b1427a3dc8ca6e3b59fbf4dfc9d4aec9edc0d9cfbcef5b60b0- Stable URL of this page
https://metraipolis.com/documento/dc_7b6a79ebafb2
How to cite
Navigating Small-World Networks with Distance Predictions — arXiv:2609.10885 — arXiv (en), https://arxiv.org/abs/2609.10885 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_7b6a79ebafb2 (Metraipolis archive dc_7b6a79ebafb2, sha256 7b2b8c02b487f3b1427a3dc8ca6e3b59fbf4dfc9d4aec9edc0d9cfbcef5b60b0)
BibTeX
@misc{dc7b6a79ebafb2,
title = {Navigating Small-World Networks with Distance Predictions — arXiv:2609.10885},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.10885},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_7b6a79ebafb2; sha256 7b2b8c02b487f3b1427a3dc8ca6e3b59fbf4dfc9d4aec9edc0d9cfbcef5b60b0},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.10885. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The small-world phenomenon was given an algorithmic foundation by Kleinberg, who showed that in an augmented $k$-dimensional lattice a decentralized greedy algorithm delivers a message in $O(\log^2 n)$ expected steps. We study predicted-greedy routing, in which a mobile agent forwarding the message moves at each step to the neighbor minimizing a noisy $(\varepsilon,\delta)$-prediction of its distance to the target, redrawn at every step from an oracle conditioned on the full routing history. Two cases arise from what this agent can observe. An agent with the coordinate awareness can still compute lattice distance exactly, but not graph distance in the shortcut-augmented network, since that depends on the shortcuts of nodes it has not yet visited; given an $(\varepsilon,\delta)$-prediction of graph distance, information the classical model never supplies, it achieves expected delivery time $O(\log n/(1-4k\varepsilon\delta))$, an asymptotic improvement over $\Theta(\log^2 n)$. An agent with no coordinate awareness at all, the natural model for a privacy-preserving network whose nodes never disclose their coordinates, cannot compute even lattice distance; given an $(\varepsilon,\delta)$-prediction of lattice distance instead, it still reaches the target in $O(n/(1-4k\varepsilon\delta))$ expected steps. Together these results show that a modest amount of predicted information, of the right kind, is enough to accelerate decentralized routing well below Kleinberg's classical bound, and that even when nodes reveal no coordinates at all, reliable delivery remains achievable. Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-11 in cs.DC). Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2609.10885 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T05:26:44.588Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-11?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).