Mixed integer programming formulations for clustering problems related to 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.