Adding Cohesion Constraints to Models for Modularity Maximization in NetworksReport as inadecuate

Adding Cohesion Constraints to Models for Modularity Maximization in Networks - Download this document for free, or read online. Document in PDF available to download.

1 MAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l-Aérien 2 Singapore University of Technology and Design 3 HEC Montréal - HEC Montréal

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.

Keywords : complex networks modularity clustering community detection mathematical modelling cohesion conditions

Author: Sonia Cafieri - Alberto Costa - Pierre Hansen -



Related documents