Скрыть
Раскрыть

ISSN 1998-0663 (print),
ISSN 2587-8166 (online)

English version: ISSN 2587-814X (print),
ISSN 2587-8158 (online)

Лобанова С. Ю., Чеповский А. А.1
  • 1 НИУ ВШЭ, 101000, Россия, Москва, ул. Мясницкая, д.20

Комбинированный алгоритм выделения сообществ в графах взаимодействующих объектов

2017. № 4 (42). С. 64–73 [содержание номера]

С.Ю. Лобанова - студент бакалавриата, Московский институт электроники и математики им. А.Н. Тихонова, Национальный исследовательский университет «Высшая школа экономики»
Адрес: 101000, г. Москва, ул. Мясницкая, д. 20
E-mail: s.lobanova@usabilitylab.net

А.А. Чеповский - кандидат физико-математических наук, доцент департамента прикладной математики, Московский институт электроники и математики им. А.Н. Тихонова, Национальный исследовательский университет «Высшая школа экономики»
Адрес: 101000, г. Москва, ул. Мясницкая, д. 20
E-mail: aachepovsky@hse.ru

      В статье предложен и реализован алгоритм выделения пересекающихся и вложенных сообществ в графах взаимодействующих объектов различной природы. Для этого рассмотрены два классических алгоритма: иерархический агломеративный и основанный на поискеk-клик. Представленный комбинированный алгоритм основан на последовательном их применении. Кроме того, разработаны параметрические опции, отвечающие за действия с сообществами, размеры которых меньше заданногоk, а также с единичными вершинами. Варьирование этих параметров позволяет учитывать различия в топологии исходного графа и корректировать тем самым алгоритм.
      Проведено тестирование на реальных данных, в том числе на группе графов социальной сети, исследовано качественное содержание полученного разбиения. Для оценки различий, получаемых интегрированным методом и классическими алгоритмами выделения сообществ, была использована общепринятая мера подобия. В результате явно показано, что результирующие разбиения значительно отличаются. Выявлено, что для предложенного в статье подхода показатель числовой характеристики корректности разбиений, модулярности, может быть ниже соответствующего значения при применении других подходов. При этом содержательно результат интегрированного метода зачастую более информативен в силу пересечений и вложенной структуры сообществ.
      Представлена визуализация разбиения, получаемого для одного из примеров интегрированным методом на первом и последнем шагах. Наряду с успешно найденным набором параметров интегрированного метода для малых сообществ и отсеченных вершин в случае социальных сетей отмечены некоторые недостатки предложенной модели. Сделаны предложения по развитию данного подхода в виде использования набора параметрических алгоритмов.

Работа выполнена при поддержке Российского фонда фундаментальных исследований (проекты №16-29-09546 и №16-07-00641)

Библиографическое описание:

Лобанова С.Ю., Чеповский А.А. Комбинированный алгоритм выделения сообществ в графах взаимодействующих объектов // Бизнес-информатика. 2017. № 4 (42). С. 64–73. DOI: 10.17323/1998-0663.2017.4.64.73.

BiBTeX
RIS
 
 
Rambler's Top100 rss