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