Accéder directement au contenu Accéder directement à la navigation
Nouvelle interface
Article dans une revue

Locally optimal heuristic for modularity maximization of networks

Abstract : Community detection in networks based on modularity maximization is currently done with hierarchical divisive or agglomerative as well as partitioning heuristics, hybrids, and, in a few papers, exact algorithms. We consider here the case of hierarchical networks in which communities should be detected and propose a divisive heuristic which is locally optimal in the sense that each of the successive bipartitions is done in a provably optimal way. This heuristic is compared with the spectral-based hierarchical divisive heuristic of Newman [Proc. Natl. Acad. Sci. USA 103, 8577 (2006).] and with the hierarchical agglomerative heuristic of Clauset, Newman, and Moore [Phys. Rev. E 70, 066111 (2004).]. Computational results are given for a series of problems of the literature with up to 4941 vertices and 6594 edges. They show that the proposed divisive heuristic gives better results than the divisive heuristic of Newman and than the agglomerative heuristic of Clauset et al.
Type de document :
Article dans une revue
Liste complète des métadonnées

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

https://hal-enac.archives-ouvertes.fr/hal-00934660
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : mardi 8 avril 2014 - 16:25:26
Dernière modification le : mardi 19 octobre 2021 - 11:02:49
Archivage à long terme le : : mardi 8 juillet 2014 - 10:43:20

Fichier

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

Identifiants

Collections

Citation

Sonia Cafieri, Pierre Hansen, Leo Liberti. Locally optimal heuristic for modularity maximization of networks. Physical Review E : Statistical, Nonlinear, and Soft Matter Physics, 2011, 83 (5), pp 056105-1 - 056105-8. ⟨10.1103/PhysRevE.83.056105⟩. ⟨hal-00934660⟩

Partager

Métriques

Consultations de la notice

211

Téléchargements de fichiers

323