• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Статья

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

Бизнес-информатика. 2017. Т. 42. № 4. С. 64-73.
Чеповский А. А., Лобанова С. Ю.

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