A Doubling dimension Threshold $\Theta(\log\log n)$ for augmented graph navigability

Abstract

(eng) In his seminal work, Kleinberg showed how to augment meshes using random edges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields the crucial question of determining wether such an augmentation is possible for all graphs. In this paper, we answer negatively to this question by exhibiting a threshold on the doubling dimension, above which an infinite family of graphs cannot be augmented to become navigable whatever the distribution of random edges is. Precisely, it was known that graphs of doubling dimension at most O(log log n) are navigable. We show that for doubling dimension >> log log n, an infinite family of graphs cannot be augmented to become navigable. Finally, we complete our result by studying square meshes, that we prove to always be augmentable to become navigable. (fre) Kleinberg a montré comment augmenter les grilles par des liens aléeatoires de façcon à ce qu'elles deviennent navigables; c'est-à-dire que le routage glouton calcule des chemins de longueur polylogarithmique en espérance entre toute paire de noeuds. Cela conduit à la question cruciale de déterminer si une telle augmentation est possible pour tout graphe. Dans cet article, nous répondons négativement à cette question en exhibant un seuil sur la dimension doublante, au-dessus duquel une famille infinie de graphes ne peut pas être augmentée pour devenir navigable, quelle que soit la distribution de liens. Précisément, il était connu que les graphes de dimension doublante au plus O(log log n) sont navigable. Nous montrons que pour une dimension doublante >> log log n, une famille infinie de graphes ne peut être augmentée pour devenir navigable. Enfin, nous complétons notre résultat en étudiant les grilles que nous démontrons pouvoir toujours être augmentées pour devenir navigables.