A mixed integer linear programming approach for soft graph clustering

This paper proposes a Mixed-Integer Linear Pro-gramming (MILP) formulation for Soft Graph Clustering that can be applied to both weighted and unweighted graphs and is polynomial in size. It can provide proven optimal solutions or solutions with proven optimality gap. The solutions will partition the set of vertices in a graph into K (possibly over-lapping) clusters, for K predetermined. The MILP approach can also simultaneously allocate membership proportion for vertices that lie in multiple clusters, and handle restrictions such as cardinality constraints on the size of the overlaps and equal balance of cluster memberships. Our approach requires neither a threshold on edge weights to be predetermined nor the finding of clique neighbourhoods of any size. It does not require the maximum number of clusters to be predetermined. We compare our approach numerically with four existing algorithms: one that requires the finding of clique neighbourhoods, one that performs well on weighted graphs only, one that requires the maximum number of clusters be predetermined, and one that is statistical analysis-based; and discuss in what way our approach outperform these methods.