Searching for optimal paths in long-range contact networks.
Résumé
Since Milgram experiment in 1967, that demonstrated the ability of people to find short paths efficiently in networks, based only on their own local view of the network, different models have been proposed to study the ``small world phenomenon''. In 2000, Kleinberg shows that most of the previously known models for small world fail to capture an important feature of the phenomenon: no local information based (i.e., decentralized) algorithm can find short paths in these graphs, when they exists. He then introduces a model composed of a lattice (representing the local acquaintances) augmented with directed links (symbolizing long-range contacts) distributed harmonically. He proposes to model people behavior by the greedy algorithm that forwards the message to the contact (local or long-range) of the current holder, which is the closest to its destination. He shows that this greedy algorithm computes paths of expected length $\Theta(\log^2n)$ between any pair of nodes. The present paper questions the choice of the greedy strategy to model social behavior. We proposes a new strategy in which nodes consult their acquaintances near by, before deciding where to forward the message. Our algorithm presents the same computational characteristics as Kleinberg's original algorithm: uses $\Theta(\log n)$ bits of memory and visits $O(\log^2n)$ nodes. However, it computes much shorter paths, of expected length $O(\log n(\log \log n)^2)$, between any pair of nodes. This algorithm demonstrates that consulting their acquaintances near by, leads to considerable improvements in performances. It also shows that this consultation is less and less useful as one gets closer to the target. As far as we know, this is the first algorithm to ``break the $\Theta(\log^2 n)$ barrier'' for the paths length in Kleinberg's network.
Depuis l’expérience de Milgram de 1967, qui démontre que les individus trouvent efficacement des courts chemins dans de grands graphes en utilisant uniquement leur vision locale du graphe, plusieurs modèles ont été proposés pour étudier ce phénomène de ”petit monde”. En 2000, Kleinberg a montré que la plupart des modèles précédemment connus manquaient une caractéristique importante du phénomène:aucun algorithme décentralisé ne pouvait trouver les courts chemins lorsqu’ils existaient. Il a alors introduit un modèle composé d’une grille carrée (représentant les connaissances locales) augmentée de liens dirigés (symbolisant les contacts distants) distribués harmoniquement. Il propose de modéliser le comportement des individus par l’algorithme glouton qui passe le message au contact (local ou distant) du possesseur actuel du message qui est le plus proche du destinataire. Il montre que cet algorithme glouton calcule un chemin de longueur moyenne Θ(log2n) entre toute paire de nœuds. Nous nous poserons la question de la pertinence du choix de la stratégie gloutonne pour modéliser les comportements sociaux. Nous proposons une nouvelle stratégie dans laquelle les nœuds consultent leurs connaissances avant de décider à qui envoyer le message. Notre algorithme présente les mêmes caractéristiques de complexité que l’algorithme original de Kleinberg: il utilise Θ(log2n) bits de mémoire et visite O(log2n) nœuds. Il calcule des chemins plus courts, de longueur moyenne O(logn(log logn)2), entre toute paire de nœuds. Cet algorithme montre que consulter son voisinage conduit à des am améliorations de performances, il montre aussi que cette consultation est de moins en moins utile lorsque l’on s’approche de la destination
| Origine | Fichiers produits par l'(les) auteur(s) |
|---|
Loading...