@ARTICLE{26583204_216770576_2017, 
	author = {С. Ю. Лобанова and А. А. Чеповский}, 
	keywords = {, граф, анализ графа, выделение сообществ, структура графа, анализ социальной сетибольшие данные},
	title = {Комбинированный алгоритм выделения сообществ в графах взаимодействующих объектов},
	journal = {Бизнес-информатика},
	year = {2017},
	number = {4 (42)},
	pages = {64-73},
	url = {https://bijournal.hse.ru/2017--4 (42)/216770576.html},
	publisher = {},
	abstract = {С.Ю. Лобанова - студент бакалавриата, Московский институт электроники и математики им. А.Н. Тихонова, Национальный исследовательский университет «Высшая школа экономики»Адрес: 101000, г. Москва, ул. Мясницкая, д. 20E-mail: s.lobanova@usabilitylab.netА.А. Чеповский - кандидат физико-математических наук, доцент департамента прикладной математики, Московский институт электроники и математики им. А.Н. Тихонова, Национальный исследовательский университет «Высшая школа экономики»Адрес: 101000, г. Москва, ул. Мясницкая, д. 20E-mail: aachepovsky@hse.ru      В статье предложен и реализован алгоритм выделения пересекающихся и вложенных сообществ в графах взаимодействующих объектов различной природы. Для этого рассмотрены два классических алгоритма: иерархический агломеративный и основанный на поискеk-клик. Представленный комбинированный алгоритм основан на последовательном их применении. Кроме того, разработаны параметрические опции, отвечающие за действия с сообществами, размеры которых меньше заданногоk, а также с единичными вершинами. Варьирование этих параметров позволяет учитывать различия в топологии исходного графа и корректировать тем самым алгоритм.      Проведено тестирование на реальных данных, в том числе на группе графов социальной сети, исследовано качественное содержание полученного разбиения. Для оценки различий, получаемых интегрированным методом и классическими алгоритмами выделения сообществ, была использована общепринятая мера подобия. В результате явно показано, что результирующие разбиения значительно отличаются. Выявлено, что для предложенного в статье подхода показатель числовой характеристики корректности разбиений, модулярности, может быть ниже соответствующего значения при применении других подходов. При этом содержательно результат интегрированного метода зачастую более информативен в силу пересечений и вложенной структуры сообществ.      Представлена визуализация разбиения, получаемого для одного из примеров интегрированным методом на первом и последнем шагах. Наряду с успешно найденным набором параметров интегрированного метода для малых сообществ и отсеченных вершин в случае социальных сетей отмечены некоторые недостатки предложенной модели. Сделаны предложения по развитию данного подхода в виде использования набора параметрических алгоритмов.Работа выполнена при поддержке Российского фонда фундаментальных исследований (проекты №16-29-09546 и №16-07-00641)},
	annote = {С.Ю. Лобанова - студент бакалавриата, Московский институт электроники и математики им. А.Н. Тихонова, Национальный исследовательский университет «Высшая школа экономики»Адрес: 101000, г. Москва, ул. Мясницкая, д. 20E-mail: s.lobanova@usabilitylab.netА.А. Чеповский - кандидат физико-математических наук, доцент департамента прикладной математики, Московский институт электроники и математики им. А.Н. Тихонова, Национальный исследовательский университет «Высшая школа экономики»Адрес: 101000, г. Москва, ул. Мясницкая, д. 20E-mail: aachepovsky@hse.ru      В статье предложен и реализован алгоритм выделения пересекающихся и вложенных сообществ в графах взаимодействующих объектов различной природы. Для этого рассмотрены два классических алгоритма: иерархический агломеративный и основанный на поискеk-клик. Представленный комбинированный алгоритм основан на последовательном их применении. Кроме того, разработаны параметрические опции, отвечающие за действия с сообществами, размеры которых меньше заданногоk, а также с единичными вершинами. Варьирование этих параметров позволяет учитывать различия в топологии исходного графа и корректировать тем самым алгоритм.      Проведено тестирование на реальных данных, в том числе на группе графов социальной сети, исследовано качественное содержание полученного разбиения. Для оценки различий, получаемых интегрированным методом и классическими алгоритмами выделения сообществ, была использована общепринятая мера подобия. В результате явно показано, что результирующие разбиения значительно отличаются. Выявлено, что для предложенного в статье подхода показатель числовой характеристики корректности разбиений, модулярности, может быть ниже соответствующего значения при применении других подходов. При этом содержательно результат интегрированного метода зачастую более информативен в силу пересечений и вложенной структуры сообществ.      Представлена визуализация разбиения, получаемого для одного из примеров интегрированным методом на первом и последнем шагах. Наряду с успешно найденным набором параметров интегрированного метода для малых сообществ и отсеченных вершин в случае социальных сетей отмечены некоторые недостатки предложенной модели. Сделаны предложения по развитию данного подхода в виде использования набора параметрических алгоритмов.Работа выполнена при поддержке Российского фонда фундаментальных исследований (проекты №16-29-09546 и №16-07-00641)}
}