2-way Graph Partitioning problem
You're looking for a maximum cut in the graph &ndash; maximizing the number of edges between the partitions minimizes the number within them.

Unfortunately, Max Cut is NP-hard on general graphs and also hard to approximate. There's a polynomial-time algorithm on planar graphs, if that's of any use to you.