Finding cohesive communities with C³

Adrien Friggeri 1, 2 Eric Fleury 1, 2, 3
Résumé : Les communautés sociales ont attiré beaucoup d'attention ces dernières années. Nous avions précédemment proposé et validé l'utilisation de la cohésion, une métrique de graphe qui capture quantitativement la qualité communautaire, au sens social, d'un ensemble de sommets d'un graphe. Nous montrons que le problème de trouver un ensemble de cohésion maximum dans un graphe non orienté est NP-dur. Par ailleurs, nous montrons que le problème dual de minimiser cette quantité, pour une taille donnée, est aussi NP-dur. Nous proposons ensuite une heuristique pour optimiser la cohésion que nous appliquons au graph d'agrément de vote entre Sénateurs des États-Unis. Finalement nous concluons sur la validité de l'approche en analysant les communautés résultantes.
Liste complète des métadonnées

Littérature citée [2 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00692548
Contributeur : Adrien Friggeri <>
Soumis le : lundi 30 avril 2012 - 19:04:46
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : jeudi 15 décembre 2016 - 03:48:02

Fichier

RR-7947.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00692548, version 1

Citation

Adrien Friggeri, Eric Fleury. Finding cohesive communities with C³. [Research Report] RR-7947, INRIA. 2012. 〈hal-00692548〉

Partager

Métriques

Consultations de la notice

487

Téléchargements de fichiers

250