Influence d'une distribution des degrés en loi de puissance sur la navigabilité des petits mondes

Résumé : Cette note résume nos travaux sur le routage décentralisé dans les petits mondes, et plus spécifiquement dans ceux qui combinent un plongement spatial avec une grande variabilité des degrés. Plus précisément, nous considérons une variante du modèle des treillis augmentés dû à J.~Kleinberg (STOC 2000) pour laquelle le nombre de contacts lointains par sommet suit une loi de puissance. Ce modèle est motivé par des observations concordantes qu'un grand nombre de réseaux ont une telle distribution de degré. Pour ces réseaux, l'exposant $\alpha$ de la loi de puissance est généralement entre 2 et 3. Nous prouvons que, dans notre modèle, et pour cet intervalle de valeurs $2 < \alpha < 3$, l'espérance du nombre d'étapes du routage glouton de n'importe quelle source à n'importe quelle destination est au plus $\Oh(\log^{\alpha-1} n)$. Cette borne est exacte au sens fort. En effet, nous montrons également que l'espérance du nombre d'étapes du routage glouton entre une source et une destination choisies aléatoirement uniformément est au moins $\Omega(\log^{\alpha-1} n)$. Pour $\alpha < 2$ ou $\alpha \geq 3$, nous montrons également que le routage glouton s'exécute en $\Theta(\log^2 n)$ étapes en espérance. Et, pour $\alpha = 2$, $\Theta(\log^{1+\eps} n)$ étapes sont nécessaires en espérance, où $1/3\leq\eps\leq1/2$. A notre connaissance, ces résultats sont les premiers permettant de quantifier l'influence d'une distribution des degrés en loi de puissance sur la navigabilité des petits mondes. De surcroît, nous montrons que cette influence est significative. En particulier, lorsque l'exposant de la loi approche 2 par excès, l'espérance du nombre d'étapes du routage glouton dans un treillis augmenté dont les degrés suivent une oi de puissance approche la racine carrée du nombre d'étapes du routage glouton dans un treillis augmenté dont les degrés sont fixés, même lorsque les deux graphes possèdent un degré moyen identique.
Type de document :
Communication dans un congrès
Chaintreau, Augustin and Magnien, Clemence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00383862
Contributeur : George Giakkoupis <>
Soumis le : mercredi 13 mai 2009 - 16:47:01
Dernière modification le : jeudi 15 novembre 2018 - 20:26:56
Document(s) archivé(s) le : jeudi 10 juin 2010 - 23:07:02

Fichier

scale-free-Algotel.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00383862, version 1

Collections

Citation

Pierre Fraigniaud, George Giakkoupis. Influence d'une distribution des degrés en loi de puissance sur la navigabilité des petits mondes. Chaintreau, Augustin and Magnien, Clemence. AlgoTel, 2009, Carry-Le-Rouet, France. 2009. 〈inria-00383862〉

Partager

Métriques

Consultations de la notice

159

Téléchargements de fichiers

169