Le rôle de la dimension dans la recherche de chemins optimaux dans les petits mondes

We consider Kleinberg's celebrated small-world model (2000). This model is based on a d-dimensional grid graph of n nodes, augmented by a constant number of ''long-range links'' per node. It is known that this graph has diameter Θ(log n), and that a simple greedy search algorithm visits an expected number of O(log^2 n) nodes, which is asymptotically optimal over all decentralized search algorithms. Besides the number of nodes visited, a relevant measure is the length of the path constructed by the search algorithm. A decentralized algorithm by Lebhar and Schabanel (2003) constructs paths of expected length O(log n * (loglog n)^2) by visiting the same number of nodes as greedy search. A natural question, posed by Kleinberg (2006), is whether there are decentralized algorithms that construct paths of length O(log n) while visiting only a poly-logarithmic number of nodes. In this paper we resolve this question. For grid dimension d=1, we answer the question in the negative, by showing that any decentralized algorithm that visits a poly-logarithmic number of nodes constructs paths of expected length Ω(log n * loglog n). Further we show that this bound is tight; a simple variant of the algorithm by Lebhar and Schabanel matches this bound. For dimension d ≥ 2, however, we answer the question in the affirmative; the bound is achieved by essentially the same algorithm we used for d=1. This is the first time that such a dichotomy, based on the dimension d, has been observed for an aspect of this model. Our results may be applicable to the design of peer-to-peer networks, where the length of the path along which data are transferred is critical for the network's performance.
Dans cet article, nous apporterons une réponse exacte (asymptotiquement) et surprenante à une question ouverte depuis plusieurs années dans le domaine de la modélisation des comportements sociaux: est-il possible de naviguer dans un graphe petit-monde de Kleinberg en temps optimal ? C'est-à-dire, est-il possible de suivre un chemin optimal d'un point à un autre en utilisant seulement les informations disponibles localement. Cette question a clairement des applications dans le design de tables de routage et de protocoles pair-à-pair. La réponse que nous apportons est la suivante: si la dimension sous-jacente du graphe petit-monde est 1, la réponse est non, les chemins optimaux sont de longueur Θ(log n) alors que le mieux que l'on puisse faire à partir des informations locales est Θ(log n * loglog n); lorsque la dimension sous-jacente est ≥ 2, on démontre qu'un simple algorithme de parcours en largeur réussit à naviguer optimalement.