TY - JOUR TI - Комбинированный алгоритм выделения сообществ в графах взаимодействующих объектов T2 - Бизнес-информатика IS - Бизнес-информатика KW - граф KW - анализ графа KW - выделение сообществ KW - структура графа KW - анализ социальной сети KW - большие данные AB - С.Ю. Лобанова - студент бакалавриата, Московский институт электроники и математики им. А.Н. Тихонова, Национальный исследовательский университет «Высшая школа экономики»Адрес: 101000, г. Москва, ул. Мясницкая, д. 20E-mail: s.lobanova@usabilitylab.netА.А. Чеповский - кандидат физико-математических наук, доцент департамента прикладной математики, Московский институт электроники и математики им. А.Н. Тихонова, Национальный исследовательский университет «Высшая школа экономики»Адрес: 101000, г. Москва, ул. Мясницкая, д. 20E-mail: aachepovsky@hse.ru      В статье предложен и реализован алгоритм выделения пересекающихся и вложенных сообществ в графах взаимодействующих объектов различной природы. Для этого рассмотрены два классических алгоритма: иерархический агломеративный и основанный на поискеk-клик. Представленный комбинированный алгоритм основан на последовательном их применении. Кроме того, разработаны параметрические опции, отвечающие за действия с сообществами, размеры которых меньше заданногоk, а также с единичными вершинами. Варьирование этих параметров позволяет учитывать различия в топологии исходного графа и корректировать тем самым алгоритм.      Проведено тестирование на реальных данных, в том числе на группе графов социальной сети, исследовано качественное содержание полученного разбиения. Для оценки различий, получаемых интегрированным методом и классическими алгоритмами выделения сообществ, была использована общепринятая мера подобия. В результате явно показано, что результирующие разбиения значительно отличаются. Выявлено, что для предложенного в статье подхода показатель числовой характеристики корректности разбиений, модулярности, может быть ниже соответствующего значения при применении других подходов. При этом содержательно результат интегрированного метода зачастую более информативен в силу пересечений и вложенной структуры сообществ.      Представлена визуализация разбиения, получаемого для одного из примеров интегрированным методом на первом и последнем шагах. Наряду с успешно найденным набором параметров интегрированного метода для малых сообществ и отсеченных вершин в случае социальных сетей отмечены некоторые недостатки предложенной модели. Сделаны предложения по развитию данного подхода в виде использования набора параметрических алгоритмов.Работа выполнена при поддержке Российского фонда фундаментальных исследований (проекты №16-29-09546 и №16-07-00641) AU - С. Ю. Лобанова AU - А. А. Чеповский UR - https://bijournal.hse.ru/2017--4 (42)/216770576.html PY - 2017 SP - 64-73 VL -