Итеративная модульность

Я думаю, что ответ находится в рандомизирующей части алгоритма. Вы можете найти более подробную информацию здесь:

https://github.com/gephi/gephi/wiki/Modularity

https://sites.google.com/site/findcommunities/

http://lanl.arxiv.org/abs/0803.0476

Я нашел решение своей проблемы, используя консенсусную кластеризацию. Вот бумага, которая описывает это. Один из способов получить оптимальные кластеры без необходимости решать их в многомерном пространстве с использованием спектральной кластеризации — многократно запускать алгоритм до тех пор, пока не будет достигнуто больше разбиений. Вот статья и полное объяснение деталей:

НАУЧНЫЕ ОТЧЕТЫ | 2 : 336 | DOI: 10.1038/srep00336 Согласованная кластеризация в сложных сетях Андреа Ланчичинетти и Санто Фортунато

Матрица консенсуса. Предположим, что мы хотим объединить nP разделов, найденных алгоритмом кластеризации в сети с n вершинами. Матрица консенсуса D представляет собой матрицу размера n x n, запись Dij которой указывает количество разделов, в которых вершины i и j сети были отнесены к одному и тому же кластеру, деленное на количество разделов nP. Матрица D обычно намного плотнее, чем матрица смежности A исходной сети, потому что в матрице консенсуса есть ребро между любыми двумя вершинами, которые хотя бы один раз встречались в одном и том же кластере. С другой стороны, веса велики только у тех вершин, которые наиболее часто группируются в кластеры, тогда как малые веса указывают на то, что вершины, вероятно, находятся на границе между разными (реальными) кластерами, поэтому их отнесение к одному кластеру маловероятно и, по существу, обусловлено к шуму. Мы хотим сохранить большие веса и отбросить меньшие, поэтому необходима процедура фильтрации. Среди прочего, в отсутствие фильтрации матрица консенсуса быстро превратилась бы в очень плотную матрицу, что сделало бы применение любого алгоритма кластеризации вычислительно затратным. Мы отбрасываем все элементы D ниже порога t. Подчеркнем, что могут быть некоторые зашумленные вершины, все ребра которых могут быть ниже порога, и они больше не будут связаны. Когда это происходит, мы просто соединяем их с их соседями с наибольшим весом, чтобы граф оставался связанным на протяжении всей процедуры.

Затем мы применяем тот же алгоритм кластеризации к D и создаем другой набор разделов, который затем используется для построения новой матрицы консенсуса D9, как описано выше. Процедура повторяется до тех пор, пока матрица консенсуса не превратится в блочно-диагональную матрицу Dfinal, веса которой равны 1 для вершин в одном блоке и 0 для вершин в разных блоках. Матрица Dfinal обеспечивает структуру сообщества исходной сети. В наших расчетах обычно достаточно одной итерации, чтобы получить стабильные результаты. Отметим, что для того, чтобы все время использовать один и тот же метод кластеризации, последний должен уметь обнаруживать кластеры во взвешенных сетях, поскольку матрица консенсуса является взвешенной. Это необходимое ограничение на выбор методов, для которых можно было бы использовать предложенную здесь процедуру. Однако это не является серьезным ограничением, так как большинство описанных в литературе алгоритмов кластеризации могут обрабатывать взвешенные сети или могут быть тривиально расширены для работы с ними.