Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00383862
Contributor : George Giakkoupis <>
Submitted on : Wednesday, May 13, 2009 - 4:47:01 PM
Last modification on : Friday, November 20, 2020 - 3:36:03 PM
Long-term archiving on: : Thursday, June 10, 2010 - 11:07:02 PM

File

scale-free-Algotel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00383862, version 1

Citation

Pierre Fraigniaud, George Giakkoupis. Influence d'une distribution des degrés en loi de puissance sur la navigabilité des petits mondes. AlgoTel, 2009, Carry-Le-Rouet, France. ⟨inria-00383862⟩

Share

Metrics

Record views

186

Files downloads

251