Communautés dynamiques : détection et stabilité
Communautés dynamiques : détection et stabilité
Jean-Loup Guillaume, Matthieu Latapy (Lip6, Paris).
4 mars 2010.
Résumé :
La détection de groupes denses, ou communautés, est un problème fondamental permettant de mieux comprendre la structure sous-jacente des réseaux par une approche à la fois microscopique et macroscopique. L’aspect dynamique des réseaux a été très peu étudié jusqu’ici et c’est en particulier vrai pour la dynamique des communautés.
L’approche classique de détection de communautés sur des graphes dynamiques consiste à étudier l’évolution des groupes d’un instant à l’autre. On constate généralement des modifications significatives de la structure communautaire même si le graphe lui-même reste relativement stable. Ceci est notamment du au caractère non déterministe de la plupart des algorithmes et pas seulement à l’évolution des réseaux.
Dans cet exposé, nous présenterons tout d’abord le contexte général des recherches sur les graphes de terrain, puis nous nous intéresserons à un algorithme classique de détection de communautés pour des graphes statiques. Enfin, nous présenterons quelques résultats empiriques afin de comprendre pourquoi et comment la structure communautaire évolue lors de modifications simples du graphe.