РЕАЛИЗАЦИЯ И СРАВНИТЕЛЬНЫЙ АНАЛИЗ АЛГОРИТМОВ КЛАСТЕРИЗАЦИИ СОЦИАЛЬНЫХ СЕТЕЙ

IMPLEMENTATION AND COMPARATIVE ANALYSIS OF SOCIAL NETWORK CLUSTERING ALGORITHMS

Tatyana Balashova

student, Faculty of Computer Science and Information Technologies, Saratov State University,

Russia, Saratov

Marina Ogneva

scientific advisor, PhD in Physics and Mathematics, associate professor, Faculty of Computer Science and Information Technologies, Saratov State University,

Russia, Saratov

АННОТАЦИЯ

Рассмотрены алгоритмы кластеризации социальных сетей, проведена их оценка и сравнительный анализ на различных примерах реальных данных.

ABSTRACT

Algorithms for clustering social networks are considered, their assessment and comparative analysis are carried out using various examples of real data.

Ключевые слова: машинное обучение, кластеризация, графы.

Keywords: machine learning, clustering, graphs.

Введение

Задачи машинного обучения находят очень широкое применение в различных сферах человеческой жизни: медицине, спорте, музыке, социальной среде и т.д.

Задача поиска сообществ в неориентированных графах является одной из задач кластеризации, которая связывает машинное обучение с теорией графов. Данная задача возникает, например, тогда, когда нужно выделить сообщества по интересам (например, для проведения рекламных компаний), разбить страны мира на группы схожих по экономическому положению государств или по результатам социологических опросов выявить группы общественных проблем, вызывающих схожую реакцию у общества и т.д.

Задача кластеризации

Машинное обучение – обширный подраздел искусственного интеллекта, изучающий методы построения алгоритмов, способных обучаться [1]. Одной из задач машинного обучения является задача кластеризации.

Кластеризация – задача разбиения множества объектов на группы, называемые кластерами [2]. Главное отличие кластеризации от классификации состоит в том, что перечень групп не задан и определяется в процессе работы алгоритма.

Алгоритмы

В данной статье были рассмотрены пять алгоритмов кластеризации графов, основанные на следующих механизмах:

• случайные блуждания (Infomap, Walktrap);
• жадная оптимизация модулярности (Fastgreedy, Louvain);
• распространение близости (Labelpropagation).

Оценка качества

Не менее значимым, чем сама кластеризация, является этап оценки качества. Принято выделять две группы методов оценки качества кластеризации:

А) Внешние методы – методы, основанные на сравнении результата с априори известным разделением на кластеры, так называемыми, ground-truth сообществами.

Б) Внутренние методы – методы, определяющие качество кластеризации только по признаковым описаниям объектов, без истинного разбиения [3].

Были рассмотрены внешние (индекс Rand, индекс Фоулкса-Мэлова) и внутренние (модулярность, индекс компактности, индекс разделимости) методы.

Эксперименты на готовых датасетах

Для тестирования и сравнения алгоритмов на первом этапе были использованы готовые датасеты, составленные на основе данных Amazon и Facebook. Они были взяты из коллекции наборов данных больших сетей Стэнфордского университета [4].

Для набора данных социальной сети Facebook вершинами графа являлись пользователи этой сети, а между вершинами строилось ребро, если два пользователя имеют одинаковые политические взгляды.

На данном примере у всех алгоритмов оказалось достаточно высокое значение модулярности (), что может свидетельствовать о хорошем качестве кластеризации. Самое высокое значение модулярности показал алгоритм Lovain, самое низкое – алгоритм Fastgreedy, что может быть связано с небольшими размерами передаваемой на вход сети.

Полученные значения нормализованной взаимной информации лежат в диапазоне , что означает, что в целом разбиения, полученные различными алгоритмами, похожи.

Самыми быстрыми оказались алгоритмы Labelpropagation и Louvain.  На небольших данных модели этих алгоритмов работают соизмеримо. Это вполне объяснимо и связано с их вычислительной сложностью.

Далее были рассмотрены данные продуктовой сети, собранные с сайта Amazon с заранее известным разделением на кластеры. Вершинами графа здесь являлись продукты, ребро (i, j) проводилось в том случае, если продукт i часто покупается вместе с продуктом j. Каждая категория продуктов, представляемая Amazon, определяла ground-truth сообщество.

Самым быстрым на этот раз оказался алгоритм Lovain – данных стало больше, количество ребер в графе сильно возросло.

Самое высокое значение модулярности продемонстрировал снова алгоритм Lovain, однако Fastgreedy в этот раз лучше справился с оптимизацией модулярности.

Значения нормализованной взаимной информации свидетельствуют о том, что между собой разбиения в целом схожи, однако с ground-truth сообществами не очень хорошо совпадают. Это связано с тем, что изначально в данных были пропуски.

Эксперимент на самостоятельно-сгенерированном наборе данных

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

Рассмотрим общие результаты.

По времени выполнения самыми быстрыми оказались алгоритмы Labelprogation и Louvain.

Значение модулярности получилось небольшим у всех алгоритмов, поскольку анализируемый участок сети является очень узким, ибо рассматриваются друзья всего лишь одного пользователя. Однако результаты расчетов внешних оценок качества показывают, что достаточно большое количество объектов ground-truth сообществ в результате кластеризации алгоритмами также оказываются в одном сообществе.

Исходя из получившихся значений нормализованной взаимной информации, можно сказать о том, что в целом разбиения похожи друг на друга и не совсем похожи на ground-truth сообщества. Поскольку данные не обезличены, можно посмотреть, как выглядят разбиения, полученные с помощью алгоритмов.

Рассмотрим три самых больших ground-truth сообщества – родственников, спортсменов и творческую молодежь.

Среди родственников алгоритм Labelpropagation выделяет отдельно родственников по линии матери и по линии отца, алгоритм Walktrap определяет в отдельные сообщества двоюродных братьев и сестер.

Членов творческой молодежи алгоритмы в основном относят к одному сообществу, причем оно формируется в соответствии с возрастным порогом (около 30 лет).

Среди спортсменов алгоритмы выделяют два крупных сообщества. Представители одного из них преимущественно городские, второго – деревенские жители.

Теперь проанализируем сообщества, определяемые алгоритмами. Для этого рассмотрим три крупнейших из них.

Первое сообщество можно назвать спортивным, так как в разбиениях всех алгоритмов их количество доминирует. В разбиение алгоритма Labelpropagation попало большее количество родственников, так как сам алгоритм является неустойчивым и даже в некоторых случаях может объединить все сообщества в одно.

Во втором сообществе алгоритм Labelpropagation объединяет всех одногруппников и преподавателей в одно сообщество. Это справедливо, поскольку данное сообщество можно было назвать университетом. Алгоритмы Infomap, Fastgreedy и Walktrap исключают из сообщества некоторых преподавателей, работающих в компаниях. Алгоритм Fastgreedy также присоединяет к данному сообществу трех членов творческой молодежи и одного родственника, которые учились в университете, чьи преподаватели и студенты объединены в одно сообщество.

Опираясь на результаты разбиений для третьего сообщества, можно сказать, что алгоритм Lovain в целом правильно разделяет преподавателей и студентов, что является очень хорошим результатом.

Таким образом, можно сделать вывод о том, что по времени выполнения самыми быстрыми являются Lovain и Labelpropagation – на небольших данных работают примерно одинаково, однако с увеличением объема данных Lovain начинает выигрывать. Если же говорить о разбиениях, то несмотря на то, что каждый делит по-своему, получаются вполне осмысленные группы. Например, алгоритм Labelpropagation склонен к объединению и образованию более крупных сообществ, а алгоритм Lovain делит более четко. Но в целом то, какой вариант разбиения лучше, зависит от условий решаемой в данной момент задачи.

Заключение

Обобщив все полученные результаты, можно сделать вывод о том, что задача поиска сообществ в неориентированных графах до сих пор является открытой и не до конца изученной. Для ее решения на данный момент существует много алгоритмов, и в конкретном случае каждый из них ведет себя по-своему, имеет свои преимущества, недостатки, ограничения.

Следует отметить, что очень важно иметь доступ к внутреннему содержанию предоставляемых данных, поскольку без этого нельзя объективно оценить качество кластеризации, важно получать не только общие результаты, но и анализировать частные случаи.

Список литературы:

1. Машинное обучение [Электронный ресурс] – URL: http://www.machinelearning.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%BD%D0%BE%D0%B5_%D0%BE%D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5 (Дата обращения: 24.09.2020)
2. Кластеризация [Электронный ресурс] – URL: http://www.machinelearning.ru/wiki/index.php?title=%D0%9A%D0%BB%D0%B0%D1%81%D1%82%D0%B5%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F (Дата обращения: 30.09.2020)
3. Оценка качества в задаче кластеризации [Электронный ресурс]  – URL: http://neerc.ifmo.ru/wiki/index.php?title=Оценка_качества_в_задаче_кластеризации#.D0.9A.D0.BE.D0.BC.D0.BF.D0.B0.D0.BA.D1.82.D0.BD.D0.BE.D1.81.D1.82.D1.8C_.D0.BA.D0.BB.D0.B0.D1.81.D1.82.D0.B5.D1.80.D0.BE.D0.B2_.28.D0.B0.D0.BD.D0.B3.D0.BB._Cluster_Cohesion.29 (Дата обращения: 04.11.2020)
4. Stanford Large Network Dataset Collection [Электронный ресурс] – URL: https://snap.stanford.edu/data/ (Дата обращения: 16.05.2021)
5. Дюран Б. Кластерный анализ. – Казань: Издательство «Книга по требованию», 2012. – С.15-16.