A Doubling dimension Threshold !(log log n) for augmented graph navigability

Pierre Fraigniaud (1) , Emmanuelle Lebhar (1) , Zvi Lotker (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

In his seminal work, Klein leinberg showed how to augment meshes using randoomedges, so that they become navigable; that is, greedy routing computes paths of polylogarithmic expected length between any pairs of nodes. This yields thecrucial question of determmining wether such an augmentation is possible for allgraphs. In this his paper, we answer negatively to this question by exhibiting athreshold on the doubling dimension, above which an infinite family of Cayley 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(lo log n) are navigable.We show that for do doubling dimension >> log log n, an infinite family of Cayley graphs cannot be augmented to become navigable. Our proof relies on a result of independent interest : we show that the analysis of greedy routing worst performances on graphs augmented by arbitrary distributions of edges can be reduced to the analysis assuming a symmetric distribution. Finally, we complete our result by studying square meshes, that we prove to always be augmentable to become navigable.

Kleinberg a montré comment augmenter les grilles par des liens aléatoires de façon à 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 nœuds. 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 de Cayley ne peut pas être augmentée pour devenir navigable, quelle que soir 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 de Cayley ne peut être augmentée pour devenir navigable. Notre preuve repose sur un résultat d'intérêt indépendant : nous montrons que l'analyse des pires performances du routage glouton sur les graphes augmentés par des distributions arbitraires peut être réduite à son analyse sous l'hypothèse de distributions symétriques. Enfin, nous complétons notre résultat en étudiant les grilles que nous démontrons pouvoir toujours être augmentées pour devenir navigables.

Mots clés: Greedy routing; Small world; Cayley graphs; Duobling dimension

Mots clés: Petit monde; Routage glouton; Dimension doublante; Graphes de Cayley

Domaines: Informatique [cs]

Pierre Fraigniaud, Emmanuelle Lebhar, Zvi Lotker. A Doubling dimension Threshold !(log log n) for augmented graph navigability. [Research Report] LIP RR-2006-09, Laboratoire de l'informatique du parallélisme. 2006, 2+9p. ⟨hal-02102264⟩