Исследование структуры сообществ пользователей в графах онлайновых социальных сетей

• Автор: Коршунов, Антон Викторович
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Москва
• Количество страниц: 134 с. : ил.

1 Сообщества пользователей в социальном графе
1.1 Социальная сеть и социальный граф
1.2 Сообщества пользователей
1.3 Структурные свойства сообществ
1.4 Метрики качества сообществ
1.5 Выводы
2 Определение структуры сообществ пользователей
2.1 Методы определения структуры сообществ
2.1.1 Локальная оптимизация
2.1.2 Вероятностные модели
2.1.3 Распространение меток
2.1.4 Методы, основанные на эго-сообществах
2.1.5 Масштабируемые методы
2.2 Критерии оценки качества
2.2.1 Качество восстановления эталонных покрытий
2.2.2 Качество приложений
2.3 Выводы
3 Распределённый метод генерации случайных социальных графов с заданной структурой сообществ
3.1 Постановка задачи
3.2 Общая схема метода
3.3 Генерация двудольного графа “пользователь-сообщество”
3.3.1 Кратные рёбра
3.4 Генерация рёбер внутри сообществ

3.4.1 Модель АОМ
3.4.2 Схема генерации рёбер внутри сообществ
3.4.3 Средний коэффициент кластеризации
3.4.4 Средняя степень
3.5 Результаты экспериментов
3.5.1 Оценка свойств структуры сообществ
3.5.2 Оценка с помощью метрик качества
3.5.3 Производительность и масштабируемость
3.6 Выводы
4 Распределённый метод определения структуры сообществ в социальном графе
4.1 Постановка задачи
4.2 Общая схема метода
4.3 Определение структуры эго-сообществ
4.4 Распространение меток сообществ
4.5 Определение подсообществ
4.6 Результаты экспериментов
4.6.1 Восстановление известной структуры сообществ
4.6.2 Определение атрибутов пользователей
4.6.3 Оценка свойств структуры сообществ
4.6.4 Оценка с помощью метрик качества
4.6.5 Производительность и масштабируемость
4.7 Выводы
Заключение
Литература
А Свойства графов с сообществами
В Метрики качества сообществ

Актуальность
Работа посвящена актуальной теме исследования структуры сообществ пользователей онлайновых социальных сетей. Данная задача рассматривается как частный случай задачи категоризации вершин графа, основанной исключительно на его структурных свойствах. В случае социальных сетей под структурными свойствами понимается специфическая для конкретного социального графа конфигурация рёбер (социальных связей) между его вершинами (пользовательскими аккаунтами).
В современном понимании онлайновая социальная сеть — это Интернет-сервис, позволяющий пользователям публиковать на своих страницах персональные и иные данные и предназначенный для упрощения коммуникации и обмена информацией между пользователями сети Интернет. Социальные сети являются важным инструментом компьютерно-опосредованной коммуникации, стремительно набирающим популярность по всему миру в течение последних двух десятилетий. К примеру, в марте 2015 года социальная сеть Facebook сообщает об 1,39 миллиарде1, a Twitter — о 288 миллионах пользователей2, которые совершают какие-либо действия в сети хотя бы 1 раз в месяц.
Помимо коммуникационной функции, сервисы социальных сетей играют роль баз пользовательских данных, в которых с каждым пользователем ассоциирован набор персональной информации, составляющий его “виртуальную личность”. Данные всех пользователей некоторой сети образуют её социальный граф, — динамическую структуру, полностью описывающую состояние и поведение составляющих её пользователей, а также их отношения между собой и объектами внешнего мира в некоторый момент времени. Вершинами

Хс ^ X ^ , VХс • Хтт .Тс ^ Хпгах‘ (3.2)
Сначала генерируются ожидаемые последовательности степеней в долях графа В(У,С,А4) с11 = (с?},) и й2 = ) для количества сообществ у пользователя и размеров сообществ соответственно. Количество пользователей задаётся в виде параметра, а количество сообществ ЛТ2 сначала должно быть вычислено исходя из остальных параметров генерации. Элементы последовательностей независимо семплируются из распределений т-51 и х~@2.
Отметим, что приведённый ниже способ генерации рёбер не обеспечивает точной реализации последовательностей степеней и с12. Однако математические ожидания Еrrij] числа вхождений пользователей в сообщества и Е[жс] размеров сообществ приблизительно соответствуют математическим ожиданиям степеней вершин в долях генерируемого графа, откуда получаем следующее выражение для количества сообществ:
, (3,3)
Щхс
Отметим, что к-й момент случайной величины у,- ~ у_/3 при условии /уг : У пап Д Уг Д Утах рзвен.
Е[у-'1 = / УіРІуМуі = / —ЧддУ* ^ (3-4)
**У тій Утіїї Утах У 711 Іїі
Таким образом,
..*1 = ^-Шш1+1-Уш/п+1)
(Утах — Утіп)(к + 1 — /3)
ВД = , 1-е Те,,, „3 0-5)
а при к — /3 +
%?] = -(з.б)
Утах ~ У„пп Утт
Для случая /с = 1и/3у^2в формуле 3.3 получаем формулы зависимости математических ожиданий и хс от параметров генерации: