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.

Last modified: Wed Nov 12 09:59:42 CET 2014