4 / 11
Предсказание атрибутов профиля пользователя социальной сети…
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
69
+
α
∪
,
,
|
| |
| > max(2, |
|)
:= { },
v a
v a
v
v
v
Q
K K a
где
α
— доля, определяющая большинство для атрибута;
∈ ∧ ∈
= { |
{ , } };
v
n n V n v E
′
∈ ∧ ∈
,
= { |
( )};
v a
v
u u
a f u
,
= { |
}.
v a
v
u
Q u u
a K
∈ ∧ ∈
Итерации прекращаются, когда на последнем шаге не было произведено ни
одного изменения.
Затем вершины объединяются в сообщества по атрибутам из множества
ключевых:
= { |
},
a
v
C v a K
∈
т. е. каждому атрибуту ставится в соответствие множество вершин, у которых
этот атрибут имеется в множестве ключевых атрибутов. Каждое из сообществ
разбивается на компонентны связности, и тривиальные компоненты из одной
или двух вершин отбрасываются. Наконец, сообщества, множества вершин ко-
торых совпадают, объединяются в одно, которому сопоставляется набор атри-
бутов всех сообществ. Таким образом, результатом работы алгоритма является
список сообществ
, каждому из которых поставлен в соответствие один или
несколько атрибутов:
= {( , ) |
,
}.
A C A F C V
⊆ ⊆
Поскольку центральная вершина состоит во всех сообществах графа ее
ближайшего окружения, то она, скорее всего, будет иметь все атрибуты, связан-
ные с этими сообществами. Предлагаемый метод предсказания профиля
p
цен-
тральной вершины заключается в объединении всех атрибутов сообществ, по-
лученных алгоритмом:
( , )
=
.
A C
p
A
∈
Таким образом, данный метод объединяет два распространенных подхода к
решению проблемы: выделение сообществ и перенос атрибутов. В работе [10]
особое внимание уделено выделению сообществ в условиях, когда часть инфор-
мации об атрибутах вершин недоступна, поэтому можно утверждать, что пред-
ложенный подход, основанный на данном алгоритме, также будет толерантен к
частичному отсутствию атрибутов вершин.
Как показали эксперименты, не все атрибуты профиля могут быть предска-
заны на основе информации о структуре графа и атрибутах вершин. Примером
таких атрибутов может служить имя пользователя или пол. Поэтому перед
применением алгоритма необходимо отбросить те атрибуты, которые невоз-
можно предсказать.
Метод оценки качества предсказания.
Точность предсказания предложен-
ного метода была сравнена с несколькими известными подходами, использую-
щими информацию о связях и атрибутах пользователей. В сравнении не рас-