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.
Type de document :
Communication dans un congrès
9ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, May 2007, Ile d'Oléron, France. pp.23-26, 2007
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00176942
Contributeur : David Coudert <>
Soumis le : vendredi 5 octobre 2007 - 00:06:57
Dernière modification le : samedi 17 février 2018 - 17:46:02
Document(s) archivé(s) le : lundi 24 septembre 2012 - 13:11:11

Fichier

10-Algotel07.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : inria-00176942, version 1

Collections

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, 2007. 〈inria-00176942〉

Partager

Métriques

Consultations de la notice

229

Téléchargements de fichiers

51