Recherche et représentation de communautés dans un grand graphe : Une approche combinée

Résumé Fr En

Ce travail concerne l’analyse, la compréhension et la représentation de grands graphes. La progression des moyens de recueil et de stockage des données rend la taille de ces graphes croissante : le développement de méthodes permettant leur analyse et leur représentation est donc un domaine de recherche dynamique et important. Dans cet article, nous développons une méthode de représentation de graphes basée sur une classification préalable des sommets avant sa représentation complète. La phase de classification consiste en l’optimisation d’une mesure de qualité spécialement adaptée à la recherche de groupes denses dans les graphes. La représentation finale est basée sur un algorithme de « forces » contraint. Deux exemples issus de l’analyse de réseaux sociaux sont présentés.

This paper deals with the analysis and the visualization of large graphs. The sizes of these graphs become increasingly large as data acquisition and storage are developing. Hence the development of methods for graph analysis and visualization is a dynamic research area. In this paper, we propose a method for graphs representation and visualization based on a prior clustering of the vertices. The clustering step consists in optimizing a quality measure specifically suited for the search of dense groups in graphs. The visualization step is based on a constrained force-directed algorithm. Finally, the approach is illustrated by two applications coming from the social network field.