Recherche et représentation de communautés dans des grands graphes

Nathalie Villa (1, 2) , Taoufiq Dkaki (3, 4) , Sébastien Gadat (1) , Jean-Michel Inglebert (5) , Quoc-Dinh Truong (6)

1 IMT - Institut de Mathématiques de Toulouse UMR5219
2 TSE-R - Toulouse School of Economics
3 IRIT-SIG - Systèmes d’Informations Généralisées
4 UT2J - Université Toulouse - Jean Jaurès
5 IRIT-MELODI - MEthodes et ingénierie des Langues, des Ontologies et du DIscours
6 CTU - Can Tho University [Vietnam]

This paper deals with the analysis and the visualization of large graphs. Our interest in such a subject-matter is related to the fact that graphs are convenient widespread data structures. Indeed, this type of data can be encountered in a growing number of concrete problems: Web, information retrieval, social networks, biological interaction networks... Furthermore, the size of these graphs becomes increasingly large as the progression of the means for data gathering and storage steadily strengthens. This calls for new methods in graph analysis and visualization which are now important and dynamic research fields at the interface of many disciplines such as mathematics, statistics, computer science and sociology. In this paper, we propose a method for graphs representation and visualization based on a prior clustering of the vertices. Newman and Girvan (2004) points out that “reducing [the] level of complexity [of a network] to one that can be interpreted readily by the human eye, will be invaluable in helping us to understand the large-scale structure of these new network data”: we rely on this assumption to use a priori a clustering of the vertices as a preliminary step for simplifying the representation of the graphs - as a whole. The clustering phase consists in optimizing a quality measure specifically suitable for the research of dense groups in graphs. This quality measure is the modularity and expresses the “distance” to a null model in which the graph edges do not depend on the clustering. The modularity has shown its relevance in solving the problem of uncovering dense groups in a graph. Optimization of the modularity is done through a stochastic simulated annealing algorithm. The visualization/representation phase, as such, is based on a force-directed algorithm described in Truong et al. (2007). After giving a short introduction to the problem and detailing the vertices clustering and representation algorithms, the paper will introduce and discuss two applications from the social network field.

Mots clés: Fouille de données; Recherche de communautés; Réseaux sociaux; Classification; Représentation de graphes; Graphes

Domaines: Statistiques [math.ST]; Théorie [stat.TH]; Machine Learning [stat.ML]; Autre [cs.OH]

Nathalie Villa, Taoufiq Dkaki, Sébastien Gadat, Jean-Michel Inglebert, Quoc-Dinh Truong. Recherche et représentation de communautés dans des grands graphes. Veille Stratégique Scientifique & Technologique, Mar 2009, Nancy, France. Recherche et représentation de communautés dans des grands graphes. ⟨hal-00371956⟩