Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Complete list of metadata

Cited literature [12 references]  Display  Hide  Download
Contributor : Guy Melançon Connect in order to contact the contributor
Submitted on : Tuesday, September 5, 2006 - 6:52:18 PM
Last modification on : Friday, August 5, 2022 - 10:46:38 AM
Long-term archiving on: : Thursday, September 20, 2012 - 10:17:52 AM


  • HAL Id : lirmm-00091339, version 1


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. ⟨lirmm-00091339⟩



Record views


Files downloads