Sujet : Graphes petit-monde et conception de réseaux virtuels pour
les réseaux pair à pair.
Responsables : Nicolas Hanusse, Cyril Gavoille
Equipe : Combinatoire et Algorithmique
Ce sujet porte sur la conception de réseaux logiques pair à pair
induisant des structures de données compactes et efficaces pour la recherche
d'information dans des environnements statiques ou dynamiques. L'approche est
basée sur l'algorithmique de graphes et plus particulièrement sur des graphes
petits-mondes.
Les études récentes montrent que grand nombre des réseaux réels (Web, Internet, graphes des relations
humaines, Hollywood graph - graphe dont les acteurs définissent les noeuds et
il existe une arête entre deux acteurs s'ils ont joué dans le même film, ...)
possèdent les caractéristiques des ``petits-mondes'': petit diamêtre, le graphe
sous-jacent est trés fortement connexe, peu dense globalement mais dense
localement.
D'autre part, Kleinberg a montré que pour un modèle de graphe basé sur des
grilles augmentées d'arêtes supplémentaires (appelées liens longs), il est
possible de trouver des courts chemins pour toute paire de sommets de manière
distribuée; (sans connaissance globale du graphe). Cette idéee peut se généraliser
en prenant comme graphe de base n'importe quel graphe (au lieu de grilles). Les
perspectives et implications sont nombreuses: les graphes petits mondes
peuvent être utilisés comme structure d'index aussi bien dans des cadres
statiques que dynamiques. Cependant, de nombreuses questions restent en
suspens:
(1) Quelles familles de graphes peuvent être transformées en
petit-monde avec le rajout de quelques arêtes ?
transformer en petit-monde ?
(2) Comment utiliser les petit-mondes en tant que réseau virtuel de
faible coût pour les opérations usuelles de
recherche/indexation/diffusion dans les réseaux pair à pair
?
(3) De manière plus générale, comment proposer des versions
distribuées de l'opération de petite-mondisation ?