3 / 11
В.О. Чесноков
68
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 2
и публикациях в виртуальных сообществах (группах), числе просмотров и поло-
жительных оценок публикаций.
Стоит отметить, что большинство алгоритмов разработаны с расчетом на
то, что для обучения доступна вся информация о социальной сети и ее атрибу-
тах [8]. Только некоторые алгоритмы предсказания профилей допускают ча-
стичное отсутствие информации об атрибутах пользователей [1, 5, 8].
Постановка задачи.
Рассмотрим неориентированный невзвешенный граф
( ,
)
G V E
′ ′ ′
с диаметром, равным двум, и для которого есть такая вершина
u
, что
,
{ , }
.
v V v u u v E
′
′
∀ ∈ ≠ ∃ ∈
Определим
′
= \ { };
V V u
= \ {{ , } |
}.
E E u v v V
′
∈
Пусть у каждой вершины есть набор признаков (атрибутов) из множества
признаков
,
F
т. е. задана функция
:
2 .
F
f V
′ →
Очевидно, что не всегда суще-
ствует возможность получить полную информацию о признаках вершины (из-
за ошибок при передаче данных, цензуры, при неизвестном или неуказанном
состоянии и т. п.). Поэтому определим функцию
:
2
F
f V
′
′ →
получения призна-
ков такую, что
: ( ) ( ).
v V f v f v
′
∀ ∈ ⊆
Пусть при этом данные о центральной вершине отсутствуют, т. е. ( ) = .
f u
′
∅
Задача предсказания профиля
p
состоит в том, чтобы максимально точно
определить атрибуты центральной вершины:
: ( ( ), ) max,
p F f u p
⊆ δ
→
где
δ
— некоторая мера схожести двух множеств.
Разработанный метод.
Предлагаемый метод основан на гипотезе о том, что
сообщества образуются по модели присоединения (
affiliation model
) [9]. Гипоте-
за предполагает, что сообщества формируются из-за того, что вершины имеют
один или несколько общих признаков, а не наоборот, т. е. атрибуты порождают
сообщества.
Алгоритм выделения пересекающихся сообществ, предложенный в [10], для
каждого выделенного сообщества предоставляет собой набор атрибутов, по ко-
торым оно было предположительно образовано. Он основан на переносе атри-
бутов. Изначально каждой вершине
v
из
V
ставится в соответствие пустое
множество ключевых атрибутов
.
v
K
На каждой итерации алгоритма проводит-
ся обход всех вершин и множества их ключевых атрибутов обновляются по сле-
дующему правилу: если квалифицированное большинство соседей вершины
v
имеет некий атрибут
а
, то он добавляется в множество ключевых атрибутов
данной вершины
:
v
K