| Title: |
A Quality Measure for Multi-Level Community Structure |
| Authors: |
Delest, Maylis; Fédou, Jean-Marc; Melançon, Guy |
| Contributors: |
Laboratoire Bordelais de Recherche en Informatique (LaBRI); Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS); Laboratoire d'Informatique, Signaux, et Systèmes de Sophia Antipolis (I3S); Université Nice Sophia Antipolis (1965 - 2019) (UNS)-Centre National de la Recherche Scientifique (CNRS)-Université Côte d'Azur (UniCA); Graph Visualization and Interactive Exploration (GRAVITE); Université Sciences et Technologies - Bordeaux 1 (UB)-Centre Inria de l'Université de Bordeaux; Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS); Fouille de données environnementales (TATOO); Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM); Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS)-Université de Montpellier (UM)-Centre National de la Recherche Scientifique (CNRS) |
| Source: |
SYNASC'06: 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing ; https://hal-lirmm.ccsd.cnrs.fr/lirmm-00091339 ; SYNASC'06: 8th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, Sep 2006, pp.63-68 |
| Publisher Information: |
CCSD |
| Publication Year: |
2006 |
| Collection: |
Université de Montpellier: HAL |
| Subject Terms: |
[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]; [MATH.MATH-ST]Mathematics [math]/Statistics [math.ST]; [STAT.TH]Statistics [stat]/Statistics Theory [stat.TH]; [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS] |
| Description: |
International audience ; 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. |
| Document Type: |
conference object |
| Language: |
English |
| Availability: |
https://hal-lirmm.ccsd.cnrs.fr/lirmm-00091339; https://hal-lirmm.ccsd.cnrs.fr/lirmm-00091339v1/document; https://hal-lirmm.ccsd.cnrs.fr/lirmm-00091339v1/file/Paper_170_Delest_Fedou_Melancon.pdf |
| Rights: |
info:eu-repo/semantics/OpenAccess |
| Accession Number: |
edsbas.D72CB347 |
| Database: |
BASE |