https://hal-enac.archives-ouvertes.fr/hal-01205967Cafieri, SoniaSoniaCafieriMAIAA - ENAC - Laboratoire de Mathématiques Appliquées, Informatique et Automatique pour l'Aérien - ENAC - Ecole Nationale de l'Aviation CivileCosta, AlbertoAlbertoCostaSysmo - LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau] - X - École polytechnique - CNRS - Centre National de la Recherche ScientifiqueHansen, PierrePierreHansenGERAD & HEC Montréal - Groupe d'études et de recherche en analyse des décisions - Groupe d'études et de recherche en analyse des décisionsModularity maximization clustering with cohesion conditionsHAL CCSD2015[MATH.MATH-OC] Mathematics [math]/Optimization and Control [math.OC]Porte, LaurenceJeunes Chercheuses et Jeunes Chercheurs - Optimisation du trafic aérien via des méthodes mixtes (discretes-continus) - - ATOMIC2012 - ANR-12-JS02-0009 - JC - VALID - 2015-09-28 11:34:402021-10-19 11:02:482015-09-28 11:34:40enConference papers1The study of systems composed of interacting components through their representation as graphs is attracting a growing attention in a wide variety of domains. A modular structure characterizes many of these systems, that means that they contain subgroups of entities sharing some common properties. Therefore, a topic of particular interest is the identification of modules, called clusters or communities. The problem can be formulated using mathematical programming, where the idea is to optimize a function expressing the quality of the clustering partition. The most studied of these functions is the so-called modularity. We consider modularity maximization, formulated as a mixed-integer quadratic optimization problem that has a convex continuous relaxation. We address the problem of combining different clustering criteria and the corresponding impact on the optimization problem. Defining a good clustering criterion is in fact difficult. On the one hand, quality functions to be optimized have been proposed, and on the other hand, properties to be satisfied by each cluster of a partition have been suggested. It has recently been observed that one of the best known such properties, i.e., the weak condition [Proc. Natl. Acad. Sci. USA, 2004] was not satised by one or more clusters in a partition which maximizes some of the best known criteria. We consider five cluster-defining conditions, that we call cohesion conditions (including the weak one). We then modify the modularity optimization problem to add these conditions, one at a time, as constraints. These can be expressed as linear constraints (applying, for one of the considered conditions, a Fortet's linearization). Then, the obtained optimization models are still mixed-integer quadratic optimization problems that we solve by exact methods. We thus discuss the solution of the new models that enable to understand the impact of cohesion conditions on modularity maximization.