Analysis of the Modern Algorithms’ Accuracy for Communities Identification on Networks when Working with Graph Databases

Full Text

ВВЕДЕНИЕ

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

Существует множество известных исследователей изучающих обнаружение сообществ, которые внесли значительный вклад в развитие этой области: Мишель Гирван (Michelle Girvan), Марк Ньюман (Mark Newman), Стивен Фортуин (Steven Fortunato), Альберто Баррабаши (Albert-László Barabási) и Жан-Шарль Делен (Jean-Charles Delvenne).

Альберто Баррабаши и Река Альберт были первыми, кто ввел основополагающий термин «структура-собственность сообщества» (community structure-property) в рамках исследования социальных сетей для описания комплексной структуры взаимодействий индивидуальных узлов и их влияния на все сообщество сети. [Barabasi, Albert, 1999]. Ключевой вопрос методологии выделения самих сообществ для анализа типах сетей был исследован в дальнейшем. Мишель Гриван в соавторстве с Марком Ньюманом представили метод на основе оптимизированной модулярной функции для анализа социальных и биологических сетей [Girvan, Newman, 2002].

Современные методы обнаружения сообществ позволяют проводить аналитику социальных, экономических (финансовых), информационных, экологических и других сетей. При поддержке машинного обучения, оптимизируется и автоматизируется процесс выявления групп со смежными интересами, потребностями, свойствами в зависимости от параметров конкретной сети. [Bruna, 2017; Hamilton, William et al., 2017; Mehta et al., 2019]

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

1. ОБЩИЕ ПОНЯТИЯ О СЕТЯХ И ИХ ВИДАХ

В графе G порядок задается N = |V|, в то время как размер задается M = |E|.

Например, граф на рис. 1 характеризуется множеством вершин V = {1, 2, 3, 4, 5} и множеством ребер E = {(1, 2), (1, 5), (2, 3), (2, 5), (3, 4)}. Порядок и размер графа G равны |V| = 5 и |E| = 5 соответственно.

Рис. 1. Пример простого графа

Fig. 1. Example of the simple graph

Множество вершин, смежных с вершиной v ∈ V, называется множеством соседей v, которое обозначается Г_v. Степенью v является d(v) = |Г_v|.

Из порядка и размера можно получить глобальное значение связности вершин неориентированного графа, известное как средняя степень узла ⟨k⟩ = 2M/N.

Для неориентированного графа плотность рассчитывается по формуле:

$D_G=\frac{2\left|E\right|}{\left|V\right|\left(\left|V\right|-1\right)}.$ (1)

Максимальное число ребер равно 1/2 |V|(|V| – 1), так что максимальная возможная плотность равна 1 (для полных графов, которые содержат все возможные ребра) и минимальная равна 0 (для графа, состоящего из изолированных вершин).

Например, множеством соседей вершины 1 на 05 является Г(1) = {2, 5}, а ее степень равна d(1) = |Г(1)| = 2. Средняя степень узла в графе G рассчитывается как ⟨k⟩ = (2 ∙ 5)/5 = 2. Плотность графа равна

$D_G=\frac{2\cdot 5}{5\cdot \left(5-1\right)}=\frac{10}{20}=\mathrm{0,5.}$

Понятия пути и длины пути имеют решающее значение для понимания того, как соединены какие-либо две вершины.

Путь графа G – это подграф Р формы

V(P) = {x₀, x₁, … , x_l},

E(P) = {(x₀, x₁), (x₁, x₂), … , (x_l – 1, x_l)},

такой, что V(P) ⊆ V и E(P) ⊆ E. Вершины x₀ и x_l являются концевыми вершинами Р, а l = |E(P)| – это длина пути Р. Граф называется связным, если для любых двух вершин v_i, v_j ∈ V существует конечный путь из v_i в v_j.

Если начальная и конечная вершины пути совпадают (v_i = v_j), то путь называется петлей, или циклом.

Рассмотрим граф G и вершины v_i и v_j. Кратчайшим путем между v_i и v_j называется путь, которому соответствует минимальное значение из набора {|P₁|, |P₂|, … , |P_k|}, содержащего длины всех путей, концевыми вершинами которых являются v_i и v_j.

Например, на 0 примерами путей между вершинами 1 и 4 могут быть P_{1, 4} = {1 – 2 – 3 – 4} с длиной l_p = 3 и Pʹ_{1, 4} = {1 – 5 – 2 – 3 – 4} с длиной lʹ_p = 4. Следовательно, кратчайшим путем между вершинами 1 и 4 является P_{1, 4}.

Расстояние между вершинами 1 и 4 равно d(1, 4) = 3, а между вершинами 1 и 5 – d(1, 5) = 1.

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

Промежуточностью b(v) вершины v ∈ V называется величина

$b\left(v\right)=\sum _{v\ne s,t}{\sigma }_{st}\left(v\right),$ (2)

где величина σ_st(v) = 1, если кратчайший путь между вершинами s и t проходит через вершину v, и равна 0 в иных случаях.

Например, на 0 вершина 2 присутствует в следующих кратчайших путях: P_{1, 3}, P_{1, 4}, P_{3, 1}, P_{3, 5}, P_{4, 1}, P_{4, 5}, P_{5, 3}, P_{5, 4}, следовательно, промежуточность вершины 2 равна b(2) = 8.

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

Рассмотрим значение промежуточности l отдельного узла графа как случайную величину. Тогда функция

L_k = {v ∈ G: b(v) = l} (3)

называется вероятностным распределением промежуточности (betweenness probability distribution) графа G.

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

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

2. ХАРАКТЕРИСТИКИ БАЗ ЗНАНИЙ В СЕТЕВОМ АНАЛИЗЕ

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

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

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

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

• информацию об узлах – идентификаторы, названия, описания, атрибуты, метки;
• информацию о связях – тип связи, направление, вес, время создания, атрибуты;
• дополнительные данные – статистические показатели, результаты анализа и прогнозирования.

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

Существуют несколько наиболее важных требований к данным, хранящимся в базе знаний. Они должны быть:

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

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

• иерархические базы знаний, где данные организованы в виде иерархических структур, например, в виде дерева. Каждый узел дерева содержит информацию, которая расширяется в подузлах;
• сетевые базы знаний, в которых данные организованы в виде графа, где узлы представляют собой объекты, а ребра – отношения между объектами;
• реляционные базы знаний, в которых данные организованы в таблицы, где каждая строка представляет объект, а каждый столбец – атрибуты объектов;
• объектно-ориентированные базы знаний, в которых данные организованы в объекты, где каждый объект содержит данные и методы для работы с данными.

3. ГРАФОВАЯ БАЗА ДАННЫХ, ЕЕ СТРУКТУРА И ОСОБЕННОСТИ

В графовых базах данных (graph databases) данные хранятся в виде графа, состоящего из узлов (вершин) и связей между ними (ребер). Графовые базы данных используются в задачах, связанных с анализом связей, таких как социальные сети, транспортные сети, логистика, телекоммуникации и другие. В графовых базах данных каждый узел может иметь свой набор свойств, которые хранятся в виде пар «ключ–значение». Связи между узлами также могут иметь свои атрибуты. Важной особенностью графовых баз данных является возможность быстрого выполнения запросов на основе связей между узлами, таких как поиск путей или нахождение кратчайшего пути между двумя узлами. Среди популярных графовых баз данных можно выделить Neo4j, OrientDB, ArangoDB, JanusGraph и другие. Они используют разные алгоритмы хранения данных, структуры индексов и поддерживают разные языки запросов. Некоторые из них также поддерживают распределенную архитектуру, что позволяет масштабировать хранение и обработку данных на больших объемах.

Neo4j – это транзакционная база данных, что означает, что она поддерживает ACID-транзакции (Atomicity, Consistency, Isolation, Durability) и обеспечивает целостность данных. Neo4j использует язык запросов Cypher для выполнения операций с данными в графовой базе значительно упрощая поиск информации. Также она была разработана с учетом высокой производительности, и она способна обрабатывать огромные графы с миллиардами узлов и связей.

ArangoDB – это мульти-модельная база данных, которая включает в себя графовую модель, модель документов и модель ключ-значение. Соответственно, ArangoDB позволяет выполнять запросы, объединяя данные из нескольких разных моделей данных. ArangoDB использует язык AQL (ArangoDB Query Language), который похож на SQL, и предоставляет встроенную поддержку полнотекстового поиска, что делает ее полезной для приложений, где требуется поиск текстовой информации.

OrientDB позволяет хранить данные в различных моделях, что облегчает их интеграцию с другими приложениями и базами данных. В отличие от некоторых других графовых баз данных, OrientDB не требует строгой схемы данных. Это означает, что данные могут быть добавлены или изменены без необходимости изменять структуру базы данных. OrientDB может быть развернут в кластере, что позволяет обрабатывать большие объемы данных и обеспечивать отказоустойчивость, и имеет свой язык запросов, называемый OrientDB SQL, который поддерживает запросы в графовой и документной моделях данных.

4. АЛГОРИТМЫ ВЫДЕЛЕНИЯ СООБЩЕСТВ В СЕТЯХ

Алгоритм Гирвана–Ньюмена (Girvan–Newman algorithm) является одним из самых популярных методов обнаружения сообществ в сетях. Он был разработан М. Гирваном и М. Ньюменом в 2002 г.

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

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

Лувенский алгоритм (Louvain algorithm) – это итеративный алгоритм выделения сообществ в сети. Он был предложен В. Блондо и его коллегами в 2008 г.

Алгоритм Лувэна основан на минимизации функции модулярности, которая измеряет степень разбиения сети на сообщества. Он начинается с каждого узла сети, находящегося в отдельном сообществе, и на каждой итерации переназначает узлы из одного сообщества в другое так, чтобы увеличить значение модулярности. Этот процесс повторяется до тех пор, пока не будет достигнут максимум модулярности. Алгоритм Лувэна является быстрым и эффективным для анализа больших сетей. Он также имеет преимущество в том, что он не требует знания заранее заданного количества сообществ, а определяет их автоматически [Blondel et al., 2008]

$\begin{array}{c}M= \frac{1}{2m}\underset{i,j}{}\left(A_{ij}- p_{ij}\right)\delta \left(c_i, c_j\right)=\\ =\frac{1}{2m}\underset{i,j}{}\left(A_{ij}- \frac{k_i{k}_j}{2m}\right)\delta \left(c_i, c_j\right),\end{array}$

где A_ij – элемент матрицы смежности, представляющий вес ребер, соединяющих узлы i и j; k_i – степень узла i,

$k_i=\sum _{}_{i,j}{A}_{ij};$

c_i – сообщество, которому он принадлежит; функция δ(u, v) равна 1 = v и 0 в противном случае; m – сумма весов всех ребер в графе,

$m=\frac{1}{2}\sum _{i,j}{A}_{ij}.$

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

Лейденский алгоритм (Leiden algorithm) – это алгоритм выделения сообществ в сетях, который был разработан в университете Лейдена в Нидерландах в 2018 г. Этот алгоритм основан на комбинации двух методов: метода оптимизации модулярности и метода оптимизации улучшения пересечения.

Модулярность является мерой качества разбиения сети на сообщества и вычисляется как отношение количества ребер внутри сообщества к ожидаемому количеству ребер внутри сообщества. Чем больше модулярность, тем лучше разбиение сети на сообщества. Метод оптимизации улучшения пересечения используется для улучшения качества разбиения на сообщества, в котором учитывается пересечение между сообществами. Он основан на максимизации оценки качества разбиения, которая учитывает как модулярность, так и пересечение между сообществами. Лейденский алгоритм является одним из современных и эффективных алгоритмов выделения сообществ в сетях и широко используется в научных исследованиях и приложениях. [Girvan et al., 2002].

Алгоритм Walktrap является одним из алгоритмов выделения сообществ в сетях. Он был разработан Пьером Понсом (Pierre Pons), Маттиасом Латапи (Matthias Latapy) и Мишелем Бартиером (Michel Barthelemy) в 2005 г.

Основная идея алгоритма Walktrap заключается в том, что схожие узлы сети скорее будут оказываться в одном и том же сообществе, чем в разных. Алгоритм начинается с разбиения графа на множество подграфов, которые содержат только по одному узлу. Затем выполняются следующие шаги.

1. На каждом шаге находится расстояние между каждой парой узлов в графе, используя меру сходства, например, косинусное расстояние или евклидово расстояние.
2. Расстояния между каждой парой узлов затем используются для создания матрицы расстояний.
3. Для каждого узла в графе вычисляется его среднее расстояние до каждого другого узла.
4. Схожие узлы объединяются в сообщества на основе их среднего расстояния.
5. Процесс объединения сообществ продолжается, пока в результате не будет получено заданное число сообществ или все узлы не будут объединены в одно сообщество.

Алгоритм Walktrap хорошо работает на больших сетях с плотной структурой и не имеет проблем с обработкой сетей с различными типами связей и взаимодействиями между узлами. Однако он может иметь проблемы с обнаружением сообществ в сетях с малой плотностью и сетях с многими шумовыми связями [Pons, Pascal и др., 2006].

Алгоритм спектрального разбиения (spectral clustering algorithm) – это алгоритм кластеризации данных, основанный на спектральной теории графов. Он используется для разбиения множества данных на несколько кластеров. Алгоритм спектрального разбиения состоит из следующих шагов:

1) строится граф, где вершины представляют данные, а ребра – связи между ними;

2) вычисляется матрица смежности или матрица расстояний между вершинами графа;

3) вычисляется матрица Лапласа графа;

4) вычисляются собственные значения и собственные векторы матрицы Лапласа;

5) выбираются первые k собственных векторов, соответствующие k наименьшим собственным значениям;

6) строится матрица, состоящая из k столбцов собственных векторов;

7) применяется метод кластеризации к полученной матрице.

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

Алгоритм Маркавея–Ньюмана (Markov Cluster algorithm, MCL) – это алгоритм кластеризации, который использует матрицу переходных вероятностей Марковской цепи для обнаружения сообществ в сети. Принцип работы алгоритма заключается в следующем:

1) исходная матрица смежности преобразуется в матрицу переходных вероятностей марковской цепи путем нормализации каждой строки;

2) матрица переходных вероятностей марковской цепи возводится в степень, чтобы увеличить различия между вероятностями переходов внутри кластеров и вероятностями переходов между кластерами;

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

Алгоритм Маркавея–Ньюмана является одним из наиболее эффективных методов обнаружения сообществ. Итоговый результат представляет собой набор сообществ, каждое из которых состоит из вершин графа, которые имеют высокую вероятность принадлежности к данному сообществу.

5. СОЗДАНИЕ И АНАЛИЗ ГРАФОВОЙ БАЗЫ ДАННЫХ

Для создания графовой базы данных был использован полный и последний дамп википедии, представленный в формате XML. Следует отметить, что данный формат в настоящее время не рекомендуется для использования, как указано на официальной странице. Тем не менее, файл дампа был сжат с использованием алгоритма bz2, что позволило существенно сократить его размер в гигабайтах. После этого был разработан парсер, который переводил всю необходимую информацию из файла в формат CSV. Результатом работы парсера были два файла – Nodes.csv и links.csv. Первый файл содержал информацию обо всех узлах базы данных, а второй – информацию о связях между ними. Для реализации данного парсинга XML дампа был разработан модуль, который за это отвечает. В основе него использовались библиотеки bz2 и xml языка программирования Python.

Функции были созданы для обработки информации из дампа Википедии в формате XML. Они определяют названия тегов и извлекают информацию о страницах, что позволяет преобразовать XML-файл в формат CSV, содержащий необходимую информацию о названиях узлов и связях между ними. Для получения данных о конкретной странице использовался MediaWiki API, который предоставляет данные в формате JSON. Из полученных данных программа извлекает информацию о названии статьи, ее длине и список ссылок на другие статьи. В результате все узлы и ссылки сразу формируют граф networkx (рис. 2), с которым дальнейшее взаимодействие и анализ.

Рис. 2. Полученный граф networkx

Fig. 2. Graph retained from the networkx

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

Рис. 3. Итоговая база данных

Fig. 3. Complete database

В данной работе рассматриваются четыре метода выделения сообществ для графа, состоящего из 637 узлов и 18057 связей. Согласно уровню центральности, наиболее центральным узлом графа является статья «Robotics». Это не удивительно, так как именно от этого узла начиналось дальнейшее исследование связей. Статьи «Artificial Intelligence», «Nanotechnology» и «Robot» оказались ближайшими к центральному узлу, если не учитывать ссылки на идентификаторы ISBN и DOI, так как они присутствуют в большинстве статей. Распределение центральности представлено на рис. 4.

Рис. 4. Центральность узлов

Fig. 4. Node centrality graph

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

Алгоритм Гирвана-Ньюмена

Первым из алгоритмов, рассматриваемых в теории, был алгоритм Гирвана–Ньюмена – один из самых распространенных и классических алгоритмов выявления сообществ. Однако, согласно проведенным моделям, на текущем наборе данных алгоритм Гирвана–Ньюмана работает некорректно, поскольку при различных уровнях отсечения дендрограммы он выделяет всего 2–3 сообщества. На третьем уровне разбиения полученного набора данных алгоритм разбил его на 4 подгруппы, однако три из четырех сообществ состояли всего из 1 элемента. Это продемонстрировано на графическом представлении графа на рис. 5.

Лувенский алгоритм

Следующим был использован Лувенский алгоритм, являющийся одним из самых быстрых и наиболее эффективных алгоритмов обнаружения сообществ. Алгоритм Лувена реализуется на основе итеративно повторяющихся двух фаз. Алгоритм обнаружения сообществ очень популярен из-за простоты реализации, а также скорости алгоритма. Его применение на созданном наборе, позволило выделить 4 сообщества (рис. 6).

Лейденский алгоритм

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

Рис. 5. Выделение сообществ алгоритмом Гирвана–Ньюмена

Fig. 5. Identification of communities by the Girvan-Newman algorithm

Рис. 6. Выделение сообществ Лувенским алгоритмом

Fig. 6. Identification of communities by the Louvain algorithm

Алгоритм Walktrap

Последний рассмотренный метод – алгоритм Walktrap, применяется для обнаружения сообществ в больших сетях с использованием случайных блужданий. При использовании этого метода было обнаружено 7 сообществ (рис. 8), что отличается от предыдущих результатов, но схоже с результатами, полученными с помощью алгоритма Лувена. Следует отметить, что данный метод учитывает только одно сообщество на узел, что может быть ошибочной гипотезой в некоторых случаях. Хотя метод достаточно быстрый, он может быть менее точным по сравнению с более классическими методами, которые были рассмотрены ранее.

Рис. 7. Выделение сообществ Лейденским алгоритмом

Fig. 7. Identification of communities by the Leiden algorithm

Рис. 8. Выделение сообществ алгоритмом Walktrap

Fig. 8. Identification of communities by the Walktrap algorithm

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

Используемые метрики качества следующие.

1. Среднее расстояние – средняя длина пути через всевозможные пары узлов сообщества. Следует отметить, что в табл. 1 представлены результаты выполнения всех метрик, и видно, что чем больше разделения на сообщества, тем больше среднее расстояние.
2. Средняя вложенность узлов в сообщество. Наибольшее значение вложенности имеет алгоритм Гирвана–Ньюмана, при этом самую низкую оценки – алгоритм Лейдена.
3. Средняя транзитивность – средний коэффициент кластеризации его узлов относительно их связи внутри самого сообщества. Средняя транзитивность оценивается выше при меньшем количестве сообществ, что видно в табл. 1. Наибольшую метрику имеет алгоритм Гирвана–Ньюмана, а наименьшую алгоритм случайного блуждания.
4. Модульность Гирвана–Ньюмана – оценка качества разделения графа на кластеры. Наилучшую оценку имеют алгоритмы, которые разделили граф на среднее количество сообществ. Алгоритм Гирвана–Ньюмана, который разделил граф всего на 2 сообщества, имеет отрицательную оценку.
5. Доля узлов сообщества, имеющих внутреннюю степень выше медианного значения степени.
6. Количество ребер, внутренних для алгоритмов. Большую оценку имеют алгоритмы, которые минимально разделяют граф на сообщества, как например, алгоритм Гирвана–Ньюмана.
7. Доля существующих ребер (из всех возможных ребер), выходящих из алгоритмов. Наивысшая оценка получается у алгоритма, который имеет наиболее массовые сообщества, то есть, где граф разделяется минимальным количеством графов.
8. Модульность Эрдёша–Реньи. Данный параметр показывает высокое значение на большем разделении сообществ, так, например, в алгоритме Гирвана–Ньюмана значение стремится к нулю, у алгоритмов Лейдена и Лувейна примерно схожие показатели, как и результат разбиения на сообщества, а модель случайного блуждания имеет наибольшее значение.
9. Модульная плотность – включение информации о размере алгоритмов в ожидаемую плотность алгоритмов, чтобы избежать небрежности небольших и плотных сообществ. Данная метрика, показывает высокое качество на моделях, которые определили среднее количество сообществ, то есть на алгоритмах Лейдена и Лувейна.

По всем данным параметрам также выполняется ранговый тест Фридмана, который проверяет гипотезу о том, что в наборе из k групп зависимых выборок (где k> = 2) по крайней мере две группы представляют совокупности с разными средними значениями. На рис. 9 представлены результаты рангового теста Фридмана. Наивысшая оценка оказывается у алгоритма Лейдена, а наихудшая – у алгоритма Гирвана–Ньюмана.

Таблица 1. Метрики качества алгоритмов

[Algorithm quality metrics]

Рис. 9. Ранговый тест Фридмана

Fig. 9. Friedman rank test

Согласно полученным результатам выделения сообществ, что внутри одного кластера находятся узлы с длиной не более 2. При этом алгоритмы Лейдена и случайного блуждания достаточно одинаково выделили сообщества, что матрице похожести этих двух методов (рис. 10).

Рис. 10. Матрица похожести алгоритмов случайного блуждания и Лейдена

Fig. 10. Similarity matrix for random walk and Leiden algorithms

6. ЗАКЛЮЧЕНИЕ

В данной исследовательской работе разобран теоретический базис современных алгоритмов выявления сообществ в сетях, а также проведено сравнение четырех алгоритмов выделения сообществ в графе. Полученные результаты были сохранены в графовую базу данных Neo4j, где каждый узел содержит атрибуты, соответствующие номеру сообщества, в зависимости от используемого алгоритма. Кроме того, были использованы различные метрики качества сообществ, чтобы оценить результаты, полученные с помощью каждого алгоритма. Результаты показали, что наилучшие результаты показали алгоритмы Лейдена и Лувена с разрешающей способностью, равной единице.

В качестве дальнейшего направления работы планируется на базисе алгоритмов Лейдена и Лувена обучить нейронную сеть для оптимизации процесса определения сообществ в разных типах сетей. А также проанализировать перспективы развития этого направления с учетом доступных вычислительных мощностей и инструментов для более точного анализа.

About the authors

Ekaterina D. Kazakova

Author for correspondence.
Email: 191841@edu.fa.ru

student at the Faculty of Information Technology and Big Data Analysis of the Financial University under the Government of the Russian Federation

References

Supplementary files

Supplementary Files

Action

1. JATS XML

Download

2. Fig. 1. Example of the simple graph

Download (21KB)

Indexing metadata

3. Fig. 2. Graph retained from the networkx

Download (250KB)

Indexing metadata

4. Fig. 3. Complete database

Download (171KB)

Indexing metadata

5. Fig. 4. Node centrality graph

Download (51KB)

Indexing metadata

6. Fig. 5. Identification of communities by the Girvan-Newman algorithm

Download (236KB)

Indexing metadata

7. Fig. 6. Identification of communities by the Louvain algorithm

Download (230KB)

Indexing metadata

8. Fig. 7. Identification of communities by the Leiden algorithm

Download (233KB)

Indexing metadata

9. Fig. 8. Identification of communities by the Walktrap algorithm

Download (227KB)

Indexing metadata

10. Algorithm quality metrics

Download (542KB)

Indexing metadata

11. Fig. 9. Friedman rank test

Download (48KB)

Indexing metadata

12. Fig. 10. Similarity matrix for random walk and Leiden algorithms

Download (37KB)

Indexing metadata