Identification multi-échelle de la structure communautaire de très grands graphes

Résumé : L'identification de sous-groupes denses dans les grands réseaux d'interactions est un problème complexe auquel on se retrouve confronté dès lors que l'on essaye de décrire précisément la structure d'un grand graphe. Le calcul de ces groupes, ou communautés, revient à chercher une partition de l'ensemble des sommets qui maximise une fonction de qualité telle que la modularité. Malheureusement, la maximisation de cette fonction est un problème NP-complet et nécessite donc l'utilisation de méthodes heuristiques pour pouvoir obtenir de bonnes partitions. Nous proposons ici une méthode très efficace pour résoudre ce problème sur de très grands graphes (centaines de millions de sommets) et nous en illustrons les résultats en la comparant à plusieurs approches classiques.
Type de document :
Communication dans un congrès
David Simplot-Ryl; Sébastien Tixeuil. 10ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'08), May 2008, Saint-Malo, France. pp.61-64, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00374457
Contributeur : David Coudert <>
Soumis le : mercredi 8 avril 2009 - 17:02:38
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : jeudi 10 juin 2010 - 20:06:39

Fichier

16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00374457, version 1

Collections

Citation

Vincent Blondel, Jean-Loup Guillaume, Renaud Lambiotte, Etienne Lefebvre. Identification multi-échelle de la structure communautaire de très grands graphes. David Simplot-Ryl; Sébastien Tixeuil. 10ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'08), May 2008, Saint-Malo, France. pp.61-64, 2008. 〈inria-00374457〉

Partager

Métriques

Consultations de la notice

475

Téléchargements de fichiers

239