A Quality Measure for Multi-Level Community Structure

Maylis Delest 1 Jean-Marc Fédou 2 Guy Melançon 3, 4
3 GRAVITE - Graph Visualization and Interactive Exploration
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR
4 TATOO - Fouille de données environnementales
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Mining relational data often boils down to computing clusters, that is finding sub-communities of data elements forming cohesive sub-units, while being well separated from one another. The clusters themselves are sometimes terms “communities” and the way clusters relate to one another is often referred to as a “community structure”. We study a modularity criterionMQ introduced by Mancoridis et al. in order to infer community structure on relational data. We prove a fundamental and useful property of the modularity measure MQ, showing that it can be approximated by a gaussian distribution, making it a prevalent choice over less focused optimization criterion for graph clustering. This makes it possible to compare two different clusterings of a same graph as well as asserting the overall quality of a given clustering relying on the fact that MQ is gaussian. Moreover, we introduce a generalization extending MQ to hierarchical clusterings of graphs which reduces to the original MQ when the hierarchy becomes flat.
Type de document :
Communication dans un congrès
SYNASC'06: 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Sep 2006, pp.63-68, 2006
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00091339
Contributeur : Guy Melançon <>
Soumis le : mardi 5 septembre 2006 - 18:52:18
Dernière modification le : jeudi 24 mai 2018 - 15:59:23
Document(s) archivé(s) le : jeudi 20 septembre 2012 - 10:17:52

Identifiants

  • HAL Id : lirmm-00091339, version 1

Citation

Maylis Delest, Jean-Marc Fédou, Guy Melançon. A Quality Measure for Multi-Level Community Structure. SYNASC'06: 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Sep 2006, pp.63-68, 2006. 〈lirmm-00091339〉

Partager

Métriques

Consultations de la notice

534

Téléchargements de fichiers

209