Loops and multiple edges in modularity maximization of networks

Abstract : The modularity maximization model proposed by Newman and Girvan for the identification of communities in networks works for general graphs possibly with loops and multiple edges. However, the applications usually correspond to simple graphs. These graphs are compared to a null model where the degree distribution is maintained but edges are placed at random. Therefore, in this null model there will be loops and possibly multiple edges. Sharp bounds on the expected number of loops, and their impact on the modularity, are derived. Then, building upon the work of Massen and Doye, but using algebra rather than simulation, we propose modified null models associated with graphs without loops but with multiple edges, graphs with loops but without multiple edges and graphs without loops nor multiple edges. We validate our models by using the exact algorithm for clique partitioning of Grötschel and Wakabayashi.
Type de document :
Article dans une revue
Physical Review E : Statistical, Nonlinear, and Soft Matter Physics, American Physical Society, 2010, 81 (4), pp 046102. 〈10.1103/PhysRevE.81.046102〉
Liste complète des métadonnées

https://hal-enac.archives-ouvertes.fr/hal-00979205
Contributeur : Céline Smith <>
Soumis le : mardi 15 avril 2014 - 15:09:38
Dernière modification le : jeudi 11 janvier 2018 - 06:19:44

Identifiants

Collections

Citation

Sonia Cafieri, Pierre Hansen, Leo Liberti. Loops and multiple edges in modularity maximization of networks. Physical Review E : Statistical, Nonlinear, and Soft Matter Physics, American Physical Society, 2010, 81 (4), pp 046102. 〈10.1103/PhysRevE.81.046102〉. 〈hal-00979205〉

Partager

Métriques

Consultations de la notice

147