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.)
Name of graph partition that balances edges between sets with edges remaining within sets
graph theory;max cut;max flow min cut
This is the Min-Disagreements version of the correlation clustering problem (on complete graphs), defined by Bansal, Blum, and Chawla (full version). They give a (huge) constant factor approximation for the problem and prove it's NP-hard. Charikar, Guruswami, and Wirth show the problem is APX-hard, and improve the approximation factor to 4 via region growing. There is a beautiful and simple combinatorial algorithm (a variant of QuickSort), due to Ailon, Charikar, and Newman, that gives a factor 3 approximation. I believe the current best known approximation ratio is due to Chawla, Makarychev, Schramm, and Yaroslavtsev, and is around 2.06.