Mixed integer programming formulations for clustering problems related to structural balance

• We define and formalize graph clustering problems associated with structural balance.
• We prove worst-case complexity of a problem (RCC) introduced by Durian et al. in 2009.
• We provide a first mathematical model for RCC problem.
• We present an integer linear formulation for each clustering problem we described.
• We discuss alternative models for relaxed structural balance.

In this work, we study graph clustering problems associated with structural balance. One of these problems is known in computer science literature as the correlation-clustering (CC) problem and another (RCC) can be viewed as its relaxed version. The solution of CC and RCC problems has been previously used in the literature as tools for the evaluation of structural balance in a social network. Our aim is to solve these problems to optimality. We describe integer linear programming formulations for these problems which includes the first mathematical formulation for the RCC problem. We also discuss alternative models for the relaxed structural balance and the solution of clustering problems associated with these new models. Numerical experiments are carried out with each formulation on a set of benchmark instances available in the literature.