Adding Cohesion Constraints to Models for Modularity Maximization in Networks - Archive ouverte HAL Accéder directement au contenu
Article Dans Une Revue Journal of Complex Networks Année : 2015

Adding Cohesion Constraints to Models for Modularity Maximization in Networks

(1) , (2) , (3)
1
2
3

Résumé

Finding communities in complex networks is a topic of much current research and has applications in many domains. On the one hand, criteria for doing so have been proposed, the most studied of which is modularity. On the other hand, properties to be satisfied by each community have been suggested. It has recently been observed that one of the best known such properties, i.e. the weak condition, proposed by Radicchi et al. (2004, Proc. Natl. Acad. Sci. USA, 101, 2658) was not satisfied by one or more communities in a partition which maximizes (approximately) some of the best known criteria. It was therefore proposed by Wang et al. (2009, Lect. Notes in Oper. Res., 11, 142) to merge both approaches by maximizing a criterion subject to the weak condition. We consider five community-defining conditions, which we call cohesion conditions (strong, semi-strong, almost-strong, weak and extra-weak conditions). We add cohesion conditions, one at a time, as constraints to a modularity maximization problem, thus obtaining new mathematical optimization models, which we solve exactly. We study the impact of cohesion conditions on modularity maximization. Strong, semi-strong and almost-strong cohesion conditions appear to be generally too restrictive and the extra-weak condition too lax. The weak condition is verified by some but not all modularity maximizing partitions of the considered real-world networks. Imposition of this condition on those partitions for which some communities do not verify it reduces modularity moderately but sometimes changes the optimal number of communities and their composition. We also show, on a known example, that the strong, semi-strong and almost-strong conditions allow us to overcome the resolution limit of modularity. The behaviour of modularity maximization subject to cohesion constraints appears to be coherent with the detectability of the modular structure of the considered networks.
Fichier principal
Vignette du fichier
Cafieri_GERAD2014.pdf (271.26 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00991694 , version 1 (15-05-2014)

Identifiants

Citer

Sonia Cafieri, Alberto Costa, Pierre Hansen. Adding Cohesion Constraints to Models for Modularity Maximization in Networks. Journal of Complex Networks, 2015, 3 (3), pp 388-410. ⟨10.1093/comnet/cnu045⟩. ⟨hal-00991694⟩
257 Consultations
342 Téléchargements

Altmetric

Partager

Gmail Facebook Twitter LinkedIn More