Введение
1 Сообщества пользователей в социальном графе 13
1.1 Социальная сеть и социальный граф 13
1.2 Сообщества пользователей 16
1.3 Структурные свойства сообществ 18
1.4 Метрики качества сообществ 24
1.5 Выводы 27
2 Определение структуры сообществ пользователей 28
2.1 Методы определения структуры сообществ 29
2.1.1 Локальная оптимизация 29
2.1.2 Вероятностные модели 30
2.1.3 Распространение меток 31
2.1.4 Методы, основанные на эго-сообществах 34
2.1.5 Масштабируемые методы 35
2.2 Критерии оценки качества 36
2.2.1 Качество восстановления эталонных покрытий 36
2.2.2 Качество приложений 43
2.3 Выводы 44
3 Распределённый метод генерации случайных социальных графов с заданной структурой сообществ 45
3.1 Постановка задачи 46
3.2 Общая схема метода 47
3.3 Генерация двудольного графа "пользователь-сообщество" 49
3.3.1 Кратные рёбра 52
3.4 Генерация рёбер внутри сообществ
3.4.1 Модель AGM 55
3.4.2 Схема генерации рёбер внутри сообществ 57
3.4.3 Средний коэффициент кластеризации 60
3.4.4 Средняя степень 61
3.5 Результаты экспериментов 64
3.5.1 Оценка свойств структуры сообществ 65
3.5.2 Оценка с помощью метрик качества 70
3.5.3 Производительность и масштабируемость 72
3.6 Выводы 73
4 Распределённый метод определения структуры сообществ в социальном графе 74
4.1 Постановка задачи 75
4.2 Общая схема метода 75
4.3 Определение структуры эго-сообществ 78
4.4 Распространение меток сообществ 80
4.5 Определение подсообществ 84
4.6 Результаты экспериментов 86
4.6.1 Восстановление известной структуры сообществ 86
4.6.2 Определение атрибутов пользователей 87
4.6.3 Оценка свойств структуры сообществ 89
4.6.4 Оценка с помощью метрик качества 90
4.6.5 Производительность и масштабируемость 90
4.7 Выводы 91
Заключение 94
Литература
