Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 18 Novembre 2014

Découverte de communautés compactes dans des graphes complexes

par Jean Creusefond (GREYC, Caen)

L'étude de réseaux sociaux est à mi-chemin entre la sociologie et l'analyse de graphes. Des difficultés émergent des deux domaines : il est quasi-impossible de définir formellement des structures qui conviennent à ce que l'on cherche, et la taille des jeux de données implique des contraintes importantes sur la complexité algorithmique.

Le problème de détection de communautés en est un bon exemple. Une communauté est une structure très intuitive, mais une définition formelle satisfaisante est loin d'être évidente. De plus, les applications se font sur de grands jeux de données issus du web, les algorithmes répondant à ce problème doivent donc avoir une complexité proche du linéaire pour être utilisables.

Dans cet exposé, je donnerai une définition de la notion de communauté, basée sur l'idée qu'une communauté doit être compacte. Je présenterai une nouvelle méthode de détection basée sur l'algorithme de LexDFS. Celui-ci est un parcours de graphe en profondeur qui, lors du choix du prochain noeud à visiter, priorise les noeuds dont les voisins ont étés visités récemment. Je présenterai ensuite les résultats de diverses mesures sur cette méthode appliquée à divers graphes réels.

Enfin, j'évoquerai des possibilités d'extension de ce travail : communautés intersectantes, évolution de la méthode par l'utilisation du LexDFS+ (un LexDFS complètement déterministe qui réutilise les informations d'un précédent parcours) et des intervalles communs de permutation.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr