Skip to Main content Skip to Navigation
Journal articles

Adding Cohesion Constraints to Models for Modularity Maximization in Networks

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal-enac.archives-ouvertes.fr/hal-00991694
Contributor : Céline Smith <>
Submitted on : Thursday, May 15, 2014 - 5:15:26 PM
Last modification on : Tuesday, April 7, 2020 - 4:34:03 PM
Long-term archiving on: : Friday, August 15, 2014 - 11:25:52 AM

File

Cafieri_GERAD2014.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00991694, version 1

Collections

Citation

Sonia Cafieri, Alberto Costa, Pierre Hansen. Adding Cohesion Constraints to Models for Modularity Maximization in Networks. Journal of Complex Networks, Oxford University Press, 2015, 3 (3), pp 388-410. ⟨hal-00991694⟩

Share

Metrics

Record views

472

Files downloads

405