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 ?