Incompatibility boundaries for properties of community partitions

Arnaud Browet 1 Julien Hendrickx 1 Alain Sarlette 2
2 QUANTIC - QUANTum Information Circuits
ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, UPMC - Université Pierre et Marie Curie - Paris 6, MINES ParisTech - École nationale supérieure des mines de Paris, CNRS - Centre National de la Recherche Scientifique : UMR8551
Abstract : We prove the incompatibility of certain desirable properties of community partition quality functions. Our results generalize the impossibility result of [Kleinberg 2003] by considering sets of weaker properties. In particular, we use an alternative notion to solve the central issue of the consistency property. (The latter means that modifying the graph in a way consistent with a partition should not have counterintuitive effects). Our results clearly show that community partition methods should not be expected to perfectly satisfy all ideally desired properties. We then proceed to show that this incompatibility no longer holds when slightly relaxed versions of the properties are considered, and we provide examples of simple quality functions satisfying these relaxed properties. An experimental study of these quality functions shows a behavior comparable to established methods in some situations, but more debatable results in others. This suggests that defining a notion of good partition in communities probably requires imposing additional properties.
Type de document :
Article dans une revue
IEEE Transactions on Network Science and Engineering, IEEE, 2016
Liste complète des métadonnées

Littérature citée [20 références]  Voir  Masquer  Télécharger
Contributeur : Alain Sarlette <>
Soumis le : vendredi 11 novembre 2016 - 01:14:00
Dernière modification le : samedi 15 décembre 2018 - 01:42:43
Document(s) archivé(s) le : jeudi 16 mars 2017 - 11:24:37


boundary_communities_BHS - wit...
Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01395589, version 1


Arnaud Browet, Julien Hendrickx, Alain Sarlette. Incompatibility boundaries for properties of community partitions. IEEE Transactions on Network Science and Engineering, IEEE, 2016. 〈hal-01395589〉



Consultations de la notice


Téléchargements de fichiers