Skip to Main content Skip to Navigation
Journal articles

Kleinberg's grid unchained

Abstract : One of the key features of small-world networks is the ability to route messages in a few hops, using a decentralized algorithm in which each node has a limited knowledge of the topology. In 2000, Kleinberg proposed a model based on an augmented grid that asymptotically exhibits such a property. In this paper, we revisit the original model with the help of numerical simulations. Our approach is fueled by a new algorithm that can sample augmenting links in an almost constant time. The speed gain allows us to perform detailed numerical evaluations. We first observe that, in practice, the augmented scheme proposed by Kleinberg is more robust than what is predicted by the asymptotic behavior, even in very large finite grids. We also propose tighter bounds on the asymtotic performance of Kleinberg's greedy routing algorithm. We finally show that, if the model is fed with realistic parameters, the results are in line with real-life experiments.
Document type :
Journal articles
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Fabien Mathieu Connect in order to contact the contributor
Submitted on : Thursday, February 28, 2019 - 3:18:41 PM
Last modification on : Friday, January 8, 2021 - 11:22:05 AM
Long-term archiving on: : Wednesday, May 29, 2019 - 5:38:14 PM


Files produced by the author(s)



Céline Comte, Fabien Mathieu. Kleinberg's grid unchained. Theoretical Computer Science, Elsevier, 2020, 826-827, pp.25-39. ⟨10.1016/j.tcs.2018.09.025⟩. ⟨hal-02052607⟩



Record views


Files downloads