Материалы по решению задачи на кеггл Learning Social Circles in Networks, в которой нужно распределить друзей пользователя по кругам.
Рассматриваются три подхода:
Дивизивный алгоритм кластеризации. Суть - удаление ребер, которые принадлежат разным сообществам. Есть несколько мер определения, какие ребра являются центральными. Например, промежуточной центральности, где оценивается уровень важности ребра. Можно использовать количество наиболее коротких путей через ребро в качестве такой метрки.
Предыдущий алгоритм, улучшеный за счет моудльности. "glutton" - тип алгоритма, который максимизирует модульность, сливая сообщества на каждом шаге, чтобы получить наибольшее значение. Разрешается объединять только те сообщества, у которых есть общие ребра. Качество алгоритма хуже, но сложность линейная.
Быстро работает на больших взвешенных графах. Не гарантирует оптимальное разбиение. Вначале все вершины находятся в одном сообществе. Для каждого узла i вычисляется выигрыш веса модульности при размещении рядом с узлом j, а затем выбирается наилучшее сообщество. Короче обычный агломеративный алгоритм.