Kleinberg's grid unchained

Céline Comte, Fabien Mathieu (Corresponding author)

Research output: Contribution to journalArticleAcademicpeer-review

1 Citation (Scopus)


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 asymptotic 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.

Original languageEnglish
Pages (from-to)25-39
Number of pages15
JournalTheoretical Computer Science
Early online date2020
Publication statusPublished - 24 Jul 2020
Externally publishedYes


  • Kleinberg's grid
  • Rejection sampling
  • Simulation
  • Small-world routing


Dive into the research topics of 'Kleinberg's grid unchained'. Together they form a unique fingerprint.

Cite this