# Name of graph partition that balances edges between sets with edges remaining within sets

Is there a common name for this problem:

Let G=(V, E) be an undirected graph. Partition V into sets $S_1$, $S_2$, ..., $S_k$, such that (the number of edges between sets) + (the number of "non"-edges within sets) is minimized.

To be clear: define "extra edges" to be the set of edges with endpoints in different sets; define "missing edges" to be the set of edges in the complement of G with endpoints in the same set. The goal is to find a partition that minimizes the sum of "extra edges" and "missing edges".

(The sets need not be of similar size.)

• It's worth noting that the value of $k$ (the number of clusters) is not part of the input for correlation clustering; the algorithm is free to choose whatever number of clusters it thinks is best. – Andrew Morgan Jun 4 '16 at 7:34