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

Column generation algorithms for exact modularity maximization in networks

Abstract : Finding modules, or clusters, in networks currently attracts much attention in several domains. The most studied criterion for doing so, due to Newman and Girvan [Phys. Rev. E 69, 026113 (2004)], is modularity maximization. Many heuristics have been proposed for maximizing modularity and yield rapidly near optimal solution or sometimes optimal ones but without a guarantee of optimality. There are few exact algorithms, prominent among which is a paper by Xu et al. [Eur. Phys. J. B 60, 231 (2007)]. Modularity maximization can also be expressed as a clique partitioning problem and the row generation algorithm of Grötschel and Wakabayashi [Math. Program. 45, 59 (1989)] applied. We propose to extend both of these algorithms using the powerful column generation methods for linear and non linear integer programming. Performance of the four resulting algorithms is compared on problems from the literature. Instances with up to 512 entities are solved exactly. Moreover, the computing time of previously solved problems are reduced substantially.
Type de document :
Article dans une revue
Liste complète des métadonnées

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

https://hal-enac.archives-ouvertes.fr/hal-00934661
Contributeur : Laurence Porte Connectez-vous pour contacter le contributeur
Soumis le : mardi 15 avril 2014 - 13:34:10
Dernière modification le : mardi 19 octobre 2021 - 11:02:49
Archivage à long terme le : : mardi 15 juillet 2014 - 10:37:12

Fichier

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

Identifiants

Collections

Citation

Daniel Aloise, Sonia Cafieri, Gilles Caporossi, Pierre Hansen, Leo Liberti, et al.. Column generation algorithms for exact modularity maximization in networks. Physical Review E : Statistical, Nonlinear, and Soft Matter Physics, American Physical Society, 2010, 82 (4), pp 046112-1 - 046112-9. ⟨10.1103/PhysRevE.82.046112⟩. ⟨hal-00934661⟩

Partager

Métriques

Consultations de la notice

184

Téléchargements de fichiers

700