Программная реализация, анализ эффективности и оценка качества алгоритмов кластеризации графовых моделей социальных сетей

Рассматривается задача поиска сообществ (кластеров) в неориентированных графах (задача кластеризации). Кластеризация — объединение в группы схожих объектов — является одной из фундаментальных задач в области анализа данных. Список прикладных областей, где она применяется, широк: сегментация изображений, маркетинг, борьба с мошенничеством, прогнозирование, анализ текстов и многие другие. На сегодняшний момент не существует универсального эффективного решения данной задачи. Число методов объединения в группы, максимально похожих друг на друга объектов, довольно велико — несколько десятков алгоритмов и еще больше их модификаций. В статье описаны алгоритмы решения данной задачи, приведены оценки их асимптотической сложности, традиционные метрики и функционалы качества, необходимые для оценки результатов их работы. Предложен вариант решения проблемы, противоположной проблеме resolution limit, — нахождение мелких относительно всего графа сообществ. Выполнена программная реализация алгоритма Smart Local Moving, который является улучшением известного алгоритма Louvain. Приведено экспериментальное сравнение эффективности рассмотренных алгоритмов для больших разреженных графов, содержащих несколько сотен тысяч вершин и ребер и соответствующих реальным данным сайтов YouTube, Amazon, Live Journal. Сравнительный анализ выполнялся на этих трех «обезличенных» наборах данных с заранее известным разделением на сообщества, а также на наборе данных со всей доступной информацией о вершинах (пользователях) из социальной сети Вконтакте. Выполнялось сравнение друг с другом сообществ, найденных разными алгоритмами на одном и том же наборе данных. Оценивались такие характеристики, как время выполнения алгоритмов, показатели модулярности и нормализованной взаимной информации.