Thomas Aynaud
Mercredi 30 novembre 2011 à 14h en salle 25-26 / 105
La plupart des graphes de terrain ont une structure particulière constituée de communautés. Les noeuds sont organisés suivant des groupes appelés des communautés avec beaucoup de connexions internes mais peu entre eux. L’identification des communautés apporte un éclairage nouveau sur la structure du graphe et est importante dans de nombreux contextes. Elle a, par exemple, déjà été utilisée pour la visualisation de graphes et pour étudier différents types de réseaux comme des réseaux sociaux ou biologiques. Nous allons étudier cette structure dans le cas des réseaux dynamiques. Pour cela, nous allons suivre deux approches. La première consiste à suivre des communautés au cours du temps en les détectant à chaque instant et en suivant leur évolution. Nous verrons que bien que très naturelle, cette approche pose de nombreuses questions de stabilité : les algorithmes ont tendance à modifier beaucoup leur résultat même si le réseau change peu. Cela implique que les transformations observées dans les communautés sont en fait liées à l’algorithme et non à l’évolution de la structure du réseau. Nous proposerons donc une analyse de l’instabilité de trois algorithmes et une solution que nous validerons sur plusieurs graphes de terrain. La deuxième approche consiste à détecter la structure communautaire non pas juste pour un instant mais pour une période donnée appelée la fenêtre de temps. La durée de la période est alors un problème crucial et nous proposons une méthode de décomposition en fenêtres de temps dans un graphe dynamique. Une particularité de la méthode est que le résultat est un regroupement hiérarchique : les fenêtres de temps sont elles-mêmes susceptibles d’en contenir. En outre, les fenêtres n’ont pas besoin d’être contiguës ce qui permet par exemple de détecter une structure se répétant. Enfin, nous conclurons par des applications à la détection d’événements sur Internet et la segmentation de vidéos. Nous montrerons que l’on peut détecter des événements en trouvant les moments où la structure change brutalement et montrerons que nous détectons à la fois de nouveaux événements et des événements déjà identifiés par d’autres méthodes. Pour la segmentation de vidéos, nous avons aussi eu des problème de stabilité et nous avons donc développé une méthode plus stable de suivi et de détection.