Применение разреженной фильтрации в обнаружении сообщества: часть 1

Глубокое погружение в решение проблем обнаружения сообществ с помощью методов машинного обучения.

Статья из трех частей, написанная Брайсом Шуртсом, Эшли Дженато и Майклом Амбергом. Ссылки на части 2 и 3 находятся внизу.

Обнаружение сообщества: обзор

Сетевые сообщества:

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

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

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

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

Алгоритмическое обнаружение сообщества:

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

Алгоритм, на котором мы сосредоточимся по сравнению с нашим собственным методом обнаружения сообщества, — это алгоритм Гирвана-Ньюмена. Этот алгоритм идентифицирует «между» соседними узлами, находя, какие ребра используются для обхода пути чаще всего. Наиболее часто используемое ребро удаляется на каждой итерации алгоритма, и вычисляется модульность. По мере продвижения алгоритма и модульности достигает определенной точки, алгоритм прекращает работу. Полученный граф содержит сообщества сети с удаленными соединяющими их ребрами. Этот метод довольно популярен, так как он возвращает разумный результат для обнаружения. Однако это довольно сложный вычислительный процесс, занимающий O(m²n) времени с m ребрами и n вершинами. Таким образом, алгоритм становится непрактичным для больших сетей.

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

Обнаружение сообщества с помощью машинного обучения

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

Метод машинного обучения, который мы применяем, использует разреженную фильтрацию для уменьшения сложности сети, а затем решает проблему обнаружения сообщества с помощью алгоритма кластеризации K-средних. Первым шагом в этом процессе является передача сети в виде матрицы смежности разреженному фильтру. На первый взгляд, разреженная фильтрация уменьшает матрицу сходства графа до простейшей возможной версии, сохраняя при этом всю важную информацию. Это делается через нейронную сеть и может быть пропущено любое количество раз, прежде чем продолжить обнаружение сообщества. Однако лучше всего всю сложность этого процесса объяснил наш эксперт Бирс Шуртс в следующей части нашей серии.

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

Узнайте, как наш метод сравнивается с алгоритмом Гирвана Ньюмана в статье Эшли в третьей части.

Об авторе:

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