Espace intrinsèque d'un graphe et recherche de communautés.

National audienceDetermining the number of relevant dimensions in the eigen-space of a graph Laplacian matrix is a central issue in many spectral graph-mining applications. We tackle here the problem of finding out the "right" dimensionality of Laplacian matrices, especially those often encountered in the domains of social or biological graphs: the ones underlying large, sparse, unoriented and unweighted graphs, often endowed with a power-law degree distribution. We present here the application of a randomization test to this problem. After a small introductive example, we validate our approach first on an artificial sparse and scale-free graph, with two intermingled clusters, then on two real-world social graphs ("Football-league", "Mexican Politician Network"), where the actual, intrinsic dimensions appear to be 10 and 2 respectively ; we illustrate the optimality of the transformed dataspaces both visually and numerically, by means of a densitybased clustering technique and a decision tree.La recherche de communautés dans un graphe se heurte à des problèmes épineux de représentation (formes convexes, recouvrantes, individus isolés...) dont l'abord optimal est réalisé par les méthodes spectrales, basées sur les dimensions propres du Laplacien de ce graphe. Déterminer le nombre de dimensions à prendre en considération est essentiel pour beaucoup d'applications. On s'attaque ici à ce problème dans le cadre de graphes non-orientés et non pondérés, qui inclut un type de graphe courant dans les applications de réseaux biologiques et sociaux, ceux munis d'une distribution des degrés de leurs noeuds en loi de puissance. Nous proposons à cet effet un test de randomisation, indépendant des lois de distribution. Après un petit exemple introductif, nous validons d'abord notre approche sur un graphe artificiel de ce type comportant deux communautés, puis sur deux graphes de test " Football League " et " Mexican Politician Network ", où nous montrons à partir des résultats d'une méthode densitaire de clustering le caractère optimal du nombre de dimensions extraites