Skip to Main content Skip to Navigation
Conference papers

A propos des schémas d'augmentation universels pour la navigation dans les réseaux

Résumé : La notion de graphes augmentés a été introduite dans le but d'analyser le phénomène des "six degrés de séparation entre individus" observé empiriquement par le psychologue Milgram dans les années 60. De façon formelle, un graphe augmenté est une paire (G,\varphi), où G est un graphe et \varphi une collection de distributions de probabilité {\varphi_{u}, u\in V(G)}. Un lien supplémentaire est attribué à chaque noeud u\in V(G), pointant vers un noeud v, appelé contact longue-distance de u. La destination v de ce lien est choisie aléatoirement selon Pr{u->v}=\varphi_{u}(v). Dans un graphe augmenté, le routage glouton correspond au processus de routage sans mémoire dans lequel chaque noeud intermédiaire choisit parmi ses voisins (dont le voisin supplémentaire) celui qui est le plus proche de la cible selon la distance mesurée dans le graphe de départ G, et lui envoie le message. Grossièrement, les graphes augmentés ont pour but de modéliser la structure des réseaux sociaux tandis que le routage glouton a pour but de modéliser le procédé de recherche utilisé dans l'expérience de Milgram. Notre objectif est de concevoir des schémas d'augmentation universels efficaces, c'est-à-dire des schémas d'augmentation qui attribuent à tout graphe G une collection de distributions de probabilité \varphi telle que le routage glouton dans (G,\varphi) soit rapide. Il est connu que le schéma d'augmentation uniforme \varphi_{unif} est un schéma universel qui garantit que, pour tout graphe G de n noeuds, le routage glouton dans (G,\varphi_{unif}) s'achève en O(\sqrt{n}) étapes en espérance. Notre résultat principal est la conception d'un schéma d'augmentation universel \varphi tel que le routage glouton dans (G,\varphi) s'achève en \Otilde(n^{1/3}) étapes en espérance pour tout graphe G de n noeuds. Nous montrons également que sous l'hypothèse d'un modèle plus restreint, la borne \sqrt{n} ne peut être diminuée.
Complete list of metadata

Cited literature [4 references]  Display  Hide  Download

https://hal.inria.fr/inria-00176942
Contributor : David Coudert <>
Submitted on : Friday, October 5, 2007 - 12:06:57 AM
Last modification on : Friday, November 20, 2020 - 3:36:12 PM
Long-term archiving on: : Monday, September 24, 2012 - 1:11:11 PM

File

10-Algotel07.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : inria-00176942, version 1

Citation

Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar, Zvi Lotker. A propos des schémas d'augmentation universels pour la navigation dans les réseaux. 9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.23-26. ⟨inria-00176942⟩

Share

Metrics

Record views

287

Files downloads

69