GUILLAUME Jean-Loup

Déterminisme et non-déterminisme au service de la détection de communautés dynamiques

De nombreux systèmes, tels que des réseaux sociaux ou des réseaux informatiques, peuvent être modélisés par des graphes, que l’on 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 d’autres et notamment ils possèdent tous une structure communautaire assez forte, c’est-à-dire qu’ils sont formés de sous-ensembles de sommets densément connectés. Si l’on se restreint à une partition en communautés, on dispose de méthodes efficaces pour calculer cette structure, notamment la méthode de Louvain que j’ai 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 l’ajout 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é dans ce mémoire à l’approche 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 n’est pas utilisable directement car une modification mineure de la topologie peut engendrer des modifications très importantes de la structure communautaire, d’où un phénomène d’instabilité. 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 d’abord 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 s’il 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 qu’ils sont naturellement stables et que les modifications qu’ils peuvent subir sont cette fois très corrélées aux modifications topologiques.

Phd defence : 11/19/2012

Jury members :

Nicolas Hanusse, Directeur de Recherche CNRS, Université Bordeaux I, LABRI. [Rapporteur]
Bertrand Jouve, Professeur, Université Lyon 2, ERIC [Rapporteur]
Paul Van Dooren, Professeur, Université Catholique de Louvain, INMA [Rapporteur]
Jens Gustedt, Directeur de recherche INRIA, Université de Lorraine, LORIA
Jean-François Marcotorchino, Directeur scientifique Thales
Michèle Soria, Professeur, Université Pierre et Marie Curie, LIP6
Emmanuel Viennet, Professeur, Université Paris 13, L2TI