То, что вы описываете очень напоминает задачу “graph partitioning”.
en.wikipedia.org/wiki/Graph_partition
Если есть желание разобраться – посмотрите работы Gerorge Karypis. Он живой классик в этой области и его пакет Metis является state-of-art на сегодня. Если у вас ну очень большой граф, то можно использовать параллельную версию ParMETIS. Еще существует пакет Zoltan разработанный в рамках проекта Trilinos в Sandia National Lab. Примечателен тем, что использует гиперграф подход, что дает лучшее (в теории) качество разбиения. Однако у них явные проблемы с производительностью, да и сборка Trilinos – то еще удовлольствие. Вообще, для более детального анализа нужно знать, что у вас за граф: характерные размеры и степень связности (т.е. заполненость матрицы связности).
Удачи...
P.S. русскоязычной терминологией владею слабо, так что заранее прошу прощения за англицизмы...
