Jean-Loup Guillaume
lundi 19 novembre 2012 à 14h, salle 25-26/105
De nombreux systèmes, tels que des réseaux sociaux ou des réseaux informatiques, peuvent être modélisés par des graphes, que lon appelle alors graphes de terrain. Un certain nombre de travaux ont montré que ces graphes, bien que différents par bien des aspects, sont aussi semblables par beaucoup dautres et notamment ils possèdent tous une structure communautaire assez forte, cest-à-dire quils sont formés de sous-ensembles de sommets densément connectés. Si lon se restreint à une partition en communautés, on dispose de méthodes efficaces pour calculer cette structure, notamment la méthode de Louvain que jai contribué à créer et qui est la plus efficace dans le domaine. Or, la plupart de ces réseaux réels sont dynamiques et évoluent au cours du temps par lajout ou la suppression de sommets et de liens. Cette dynamique touche naturellement les communautés et il faut donc proposer de nouvelles méthodes pour les calculer et les analyser. Nous nous sommes intéressés dans ce mémoire à lapproche naturelle qui consiste à considérer un graphe dynamique comme une succession de graphes statiques, puis à calculer une partition en communautés à chaque instant et, enfin, à essayer de faire le lien entre les communautés à différents instants. Nous avons montré que cette approche nest pas utilisable directement car une modification mineure de la topologie peut engendrer des modifications très importantes de la structure communautaire, doù un phénomène dinstabilité. Nous avons alors proposé deux approches pour tenter de résoudre ce problème. La première approche considère que si le graphe évolue peu, ses communautés devraient rester globalement stables. Nous avons donc tout dabord tenté de stabiliser un algorithme existant en gardant la mémoire des calculs passés, ce qui a donné des résultats bien meilleurs mais avec toujours une instabilité résiduelle. Puis, nous avons étendu cette solution en calculant des partitions multi-pas de bonne qualité sur plusieurs instants de temps. Nous avons couplé cela avec une méthode de décomposition hiérarchique du temps afin de calculer des plages temporelles sur lesquelles ces partitions multi-pas ont un sens. Cette méthode à été appliquée avec succès à des données réelles. La seconde approche considère que même sil y a de nombreuses partitions de qualité, elles ne sont pas complètement différentes. Nous avons donc proposé une méthode pour calculer en pratique ces similitudes, qui permettent de définir des coeurs de communautés. Nous avons montré que les coeurs sont pertinents dans les graphes de terrain et permettent de les distinguer des graphes sans réelle structure communautaire (comme les graphes aléatoires par exemple). Nous avons également entamé des travaux pour montrer que les coeurs peuvent être utilisés dans le cas dynamique et quils sont naturellement stables et que les modifications quils peuvent subir sont cette fois très corrélées aux modifications topologiques.