Heuristics for graph bisection
(transferred from a comment above)

The problem you want to solve is called Graph Bisection and is NP-hard. A simple heuristic that might work well in your case is to find two nodes that are as far apart as possible, and then grow out their neighborhoods till you get roughly equal sizes on both. Another local improvement heuristic is to take a candidate solution, and find two vertices to swap that will reduce the cut size.