A Quality Measure for Multi-Level Community Structure - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2006

A Quality Measure for Multi-Level Community Structure

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.
Fichier principal
Vignette du fichier
Paper_170_Delest_Fedou_Melancon.pdf (126.4 Ko) Télécharger le fichier
Loading...

Dates and versions

lirmm-00091339 , version 1 (05-09-2006)

Identifiers

  • HAL Id : lirmm-00091339 , version 1

Cite

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⟩
414 View
282 Download

Share

More