Кластеризация графов на основе оценок изменения модулярности

Кластеризация графов является одной из постоянно актуальных задач анализа данных. Существуют различные постановки данной задачи. Рассматривается задача поиска разбиения множества вершин на непересекающиеся подмножества таким образом, чтобы плотность связей между вершинами одного подмножества была выше, чем между вершинами различных подмножеств. Для решения данной задачи применяются различные подходы, многие из которых используют такую апостериорную оценку качества кластеризации, как модулярность. Функционал модулярности, принимая значение из $[-1, 1]$, позволяет в формальном виде оценить качество кластеризации (разбиения на подмножества).
Предложен подход, позволяющий вместо расчета модулярности пользоваться менее вычислительно сложной оценкой ее изменения при операции объединения кластеров. Для разных видов графов сформулирован ряд теорем, показывающих возможность применения предлагаемой оценки вместо прямого вычисления модулярности.
Описана жадная алгоритмическая схема кластеризации, а также AMVE (Algorithm based on Modularity Variation Estimation) — простейший жадный алгоритм на ее основе. На тестовом проблемсете произведен сравнительный анализ AMVE с эвристическими алгоритмами кластеризации, реализованными в современных пакетах анализа графов: демонстрируется сравнительное преимущество AMVE как по скорости, так и по качеству кластеризации.
Также приводятся сведения об использовании разработанного программного обеспечения для анализа данных в социологии и литературоведении. В этих исследованиях рассматривались графы, построенные на данных социальных сетей (в качестве ребер использовалось отношение «дружбы» в социальной сети между пользователями). Продемонстрировано небольшое превосходство AMVE по качеству кластеризации по сравнению с известными алгоритмами Louvain и Walktrap.