Как выделить наиболее связные группы элементов в графе?
Почти то, что вам нужно, называется поиск мостов — ребер, удаление которых делает граф(в частности компоненту связности) несвязным.
Почитать об этом можно тут.
Может быть нужен поиск минимального сбалансированного разреза? Как вариант можно сформулировать так: разбить вершины графа на две доли равного размера, чтобы число ребер между ними было минимально.

Здесь есть кое-что: theory.stanford.edu/~trevisan/cs359g/