5 / 11
В.О. Чесноков
70
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
сматривались методы, основанные на машинном обучении, так как оно не все-
гда применимо, и методы, которые используют сведения о предпочтениях поль-
зователей, поскольку они требуют более разнородных данных, получение кото-
рых может быть затруднительным.
Первый простейший подход основан на переносе атрибутов голосованием и
заключается в объединении наиболее часто встречающихся атрибутов соседей
вершины. Если доля вершин, имеющих некоторый атрибут, превышает уста-
новленный порог, то считается, что и центральная вершина имеет данный атри-
бут.
Второй подход — анализ сообществ графа ближайшего окружения пользо-
вателя. Для каждого сообщества выбирается наиболее частый атрибут или
набор атрибутов, которые присутствуют у большинства вершин в сообществе.
Большинство вершин определяется порогом. В качестве алгоритмов выделения
сообществ были выбраны два распространенных метода: максимизация моду-
лярности [11] и Infomap [12]. Кроме того, были использованы три метода, кото-
рые также опираются на гипотезу об образовании сообществ по модели присо-
единения: AGM-fit [9], BigCLAM [13] и CESNA [14].
Третий подход основан на информации о связи между атрибутами вершин и
сообществами. Алгоритм CESNA [14] предоставляет веса для каждой пары атри-
бут–сообщество. Чем больше вес, тем больше вероятность того, что сообщество
было образовано по этому атрибуту. Значимые веса также определялись порогом.
Для тестирования подходов были использованы два набора данных от
Stanford Network Analisys Project [15]: графы ближайшего окружения пользова-
телей Facebook и Twitter. Их характеристики приведены в табл. 1. В данных
наборах предоставлена информация об эталонных сообществах, поэтому во
втором подходе к предсказанию профиля помимо сообществ, выделенных пя-
тью алгоритмами, были использованы эти сообщества. Кроме того, были ис-
пользованы графы ближайшего окружения 2000 случайно выбранных пользо-
вателей социальной сети ВКонтакте, полученные в [16].
Таблица 1
Характеристики наборов данных
Социальная
сеть
Число
графов
Среднее число
вершин
N
ребер
E
атрибутов
F
сообществ
C
10
417
17 017
228
19.3
973
138
2350
665
4,17
ВКонтакте
2000
164
1561
1665
n/a
В качестве меры качества предсказания была использована мера
1
:
F
+
∩ +
*
*
*
1
( , ) = 2 / (
) = 2 |
| /(| | | |),
F p p PR P R p p p p
где
*
p
— предсказанный профиль;
p
— истинный профиль;
*
*
= |
|| |
P p p p
∩
—
точность;
∩
*
=|
| / | |
R p p p
— полнота. Для всех графов были получены множе-