Groupe d’études et de recherche en analyse des décisions

G-2014-11

Adding cohesion constraints to models for modularity maximization in networks

, et

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 of a partition have been suggested. It has recently been observed that one of the best known such properties, i.e., Radicchi et al.'s weak condition [F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, D. Parisi, Proc. Natl. Acad. Sci. USA, 101, 2658 (2004)] 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. [J-G. Wang, L. Wang, Y-Q. Qui, Y. Wang, X-S. Zhang, Lect. Notes in Oper. Res., 11, 142 (2009)] to merge both approaches by maximizing a criterion subject to the weak condition. We consider the effect of adding five cohesion conditions, one at a time, to a modularity maximization problem. We solve the problems exactly. Strong, semi-strong, and almost-strong cohesion conditions appear to be too restrictive and the extra-weak condition too lax. The weak cohesion condition is verified by some but not all modularity maximizing partitions of real-world problems considered. 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.

, 16 pages