Данный алгоритм является одним из первых алгоритмов по выделению сообществ в сетях. Его главный недостаток — время работы. На практике мы вычисляем отношения между сообществами, используя быстрый алгоритм Ньюмена [3], который вычисляет коэффициент посредничества для всех m ребер в графе из n вершин за время O(mn). Поскольку этот расчет должен быть повторен один раз для удаления каждого ребра весь алгоритм работает в худшем случае за время O(m^2 n). Это значит, что данный метод не подходит для графов с большим количеством вершин.
Содержание
Введение 3
Постановка задачи 5
Обзор литературы 6
Глава 1. Предметная область 8
1.1 Основные определения 8
1.2 Социальный граф 10
1.3 Сообщества 12
1.4 Модулярность 13
Глава 2: Алгоритмы поиска сообществ 16
2.1 Betweenness 16
2.2 Fastgreedy 17
2.3 Multilevel 18
2.4 LabelPropogation 19
2.5 Walktrap 20
2.6 Infomap 23
Глава 3: Реализация 26
3.1 Улучшение методов поиска сообществ 26
3.2 Выявление лучшего алгоритма 28
3.3 Анализ структуры графа 29