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

Alain Lelu (1, 2) , Martine Cadot (3)

1 KIWI - Knowledge Information and Web Intelligence
2 LASELDI - Laboratoire de Semio-Linguistique, Didactique et Informatique
3 ABC - Machine Learning and Computational Biology

Determining 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 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. We validate our approach first on an artificial sparse and power-law type graph, with two intermingled clusters, then on a real-world social graph ("Football-league"), where the actual, intrinsic dimension appears to be 11 ; we illustrate the optimality of this transformed dataspace both visually and numerically, by means of a density-based clustering technique and a decision tree.

Mots clés: graphe; laplacien d'un graphe; réduction de dimensions; dimension intrinsèque; test de randomisation; clustering de graphe; méthode densitaire de clustering; graphe petit monde; extraction de communautés

Domaines: Méthodologie [stat.ME]

Alain Lelu, Martine Cadot. Espace intrinsèque d'un graphe et recherche de communautés. Première conférence sur les Modèles et l'Analyse des Réseaux : Approches Mathématiques et Informatique - MARAMI 2010, Oct 2010, Toulouse, France. pp.1. ⟨hal-00516865⟩