8494 articles  [english version]

hal-00692548, version 1

Finding cohesive communities with C³

Adrien Friggeri (, http://friggeri.net/) 1, 2, Eric Fleury a, 1, 2, 3

N° RR-7947 (2012)

Résumé : Social communities have drawn a lot of attention in the past decades. We have previously introduced and validated the use of the cohesion, a graph metric which quantitatively captures the community-ness in a social sense of a set of nodes in a graph. Here we show that the problem of maximizing this quantity is NP-Hard. Furthermore, we show that the dual problem of minimizing this quantity, for a fixed set size is also NP-Hard. We then propose a heuristic to optimize the cohesion which we apply to the graph of voting agreement between U.S Senators. Finally we conclude on the validity of the approach by analyzing the resulting agreement communities.

  • a –  INRIA
  • 1 :  DNET (ENS / LIP Laboratoire de l'Informatique du Parallélisme / INRIA Grenoble Rhône-Alpes)
  • École Normale Supérieure - Lyon – INRIA – Laboratoire d'informatique du Parallélisme
  • 2 :  Institut Rhône-Alpin des systèmes complexes (IXXI)
  • INRIA – École Normale Supérieure - Lyon – Institut National des Sciences Appliquées (INSA) - Lyon – Université Claude Bernard - Lyon I – Université Joseph Fourier - Grenoble I – CNRS – Institut de recherche pour le développement [IRD]
  • 3 :  Laboratoire de l'Informatique du Parallélisme (LIP)
  • Université de Lyon – CNRS : UMR5668 – INRIA – École Normale Supérieure - Lyon – Université Claude Bernard - Lyon I
  • Domaine : Informatique/Algorithme et structure de données
    Informatique/Réseaux et télécommunications
    Sciences de l'Homme et Société/Sociologie
  • Référence interne : RR-7947
 
  • hal-00692548, version 1
  • http://hal.inria.fr/hal-00692548
  • oai:hal.inria.fr:hal-00692548
  • Contributeur : Adrien Friggeri <>
  • Soumis le : Lundi 30 Avril 2012, 19:04:46
  • Dernière modification le : Mercredi 2 Mai 2012, 09:40:11