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

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
Liste complète des métadonnées
Contributeur : Céline Smith Connectez-vous pour contacter le contributeur
Soumis le : mardi 15 avril 2014 - 15:09:38
Dernière modification le : mardi 19 octobre 2021 - 11:02:49




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⟩



Consultations de la notice