Algorithmes de routages dans les réseaux "petits-mondes"
Contexte: La notion de
réseaux "petits-mondes" tente de regrouper de très
nombreux divers et variés ayant comme point commun qu'ils
émergent tous de manière plus ou moins "spontanée"
dans la "nature". Des exemples classiques de tels réseaux sont
les réseaux sociaux (ou réseaux de connaissances), les
réseaux métaboliques en biologie, les réseaux
Pair-à-Pair ou le graphe du web en informatique...
L'étude et la compréhension de ces réseaux
constitue un enjeux très important. Comment ces réseaux
se construisent-ils ? Comment circule l'information (on peut penser
à la propagation de virus) ? Comment peut-on retrouver de
l'information pertinente (problème des moteur de recherche) ?
... Ainsi ces dernières années ont vu l'apparition d'une
pléthore de modèles de génération de
réseaux petits mondes. Une des propriétés
communément admise pour ces réseaux est la
possibilité de router un message en un nombre très
limité d'étapes entre n'importe quelle paire de noeuds.
Travail: Dans ce contexte, J.
Kleinberg a proposé en 2000 un modèle très simple
basé sur la grille qui admet un algorithme de routage glouton
très simple et efficace. Plus récemment plusieurs
variantes de ce modèle ont été
étudiées. Il s'agira dans ce travail de comparer ces
variantes et leurs algorithmes de routage.
Pour ceci, il faudra construire un générateur
aléatoire pour le modèle de Kleinberg et
implémenter les différentes méthodes de routage.
Les résultats expérimentaux obtenus devrons alors
être comparer avec les complexités théoriques
avancées. Enfin, une interface de visualisation des routes
sélectionnées par les algorithmes sera envisagées.
Tuteur: Christophe PAUL
(paul@lirmm.fr)
Prérequis: Module
d'algorithmes distribués