Разбиение графа было давней проблемой и имеет широкий спектр приложений. В этом посте рассказывается о методологии разбиения графа как с теоретическими объяснениями, так и с практическими реализациями некоторых популярных алгоритмов разбиения графа с кодами Python.
Уточнение
«Кластеризация» может сбивать с толку в разных контекстах. В этой статье под кластеризацией понимается кластеризация узлов, то есть разбиение графов на кластеры (или сообщества). Мы взаимозаменяемо используем разделение графа, кластеризацию (узла) и обнаружение сообщества. Другими словами, мы нигде в этой статье не рассматриваем пересекающиеся сообщества. (Обратите внимание, что более широкое определение обнаружения сообщества может включать перекрывающиеся сообщества)
В нескольких словах …
Разделение графа обычно представляет собой неконтролируемый процесс, в котором мы определяем желаемую меру качества, то есть метрики оценки кластеризации, а затем используем некоторые алгоритмы для поиска наилучшего решения для разделения на основе определенных метрик оценки. В оставшемся контенте мы сначала пройдемся по двум наиболее часто используемым метрикам оценки. Затем мы вводим два метода, которые могут эффективно найти (приближенное) решение для каждой оценочной метрики.
Кластеризация показателей оценки
Поскольку кластеризация обычно является неконтролируемой задачей, важно иметь меру качества или целевую функцию для оценки решений кластеризации. Кластеризация в других областях обычно использует различные функции на основе расстояния по точкам данных для измерения качества кластеризации. Однако, поскольку графики представляют собой неевклидовы данные, а расстояние между точками данных гораздо менее важно, чем связи на графике, нам нужны разные измерения для кластеризации на графике. Другими словами, мера качества должна быть определена по связности графа.
Вырезать и нормализовать-вырезать
Как правило, часть узлов и ребер признаются одним сообществом (или одним кластером), если они плотно связаны друг с другом, в противном случае рассматриваются как разные сообщества. Поэтому естественно сгруппировать граф таким образом, чтобы узлы имели максимальное количество ребер в пределах одного кластера и минимальное количество ребер в разных кластерах. Сумма весов ребер в разных кластерах определяется как «разрез» графа. Другими словами, «разрез» — это общий вес удаленных ребер, чтобы полностью разъединить граф на отдельные подграфы.
Математически «разрез» графа G на два непересекающихся множества A и B можно вычислить следующим образом:
Чтобы найти наилучший способ кластеризации графа G, задача эквивалентна поиску минимального значения «отрезка», т. е. min-cut. Однако также нетрудно увидеть, что одним из возможных вырожденных решений минимального разреза является отсечение небольшого числа узлов от всего графа, что приводит к тривиальным кластерам, в которых удалено всего несколько ребер. Одно вырожденное решение показано на
Чтобы преодолеть эту проблему, [1] предложил метод нормализации разрезов по измерению объема ребер внутри каждого кластера, определяемого как ассоциация (Assoc).
Normalized-cut (n-cut) эффективно наказывает вырожденные решения в min-cut, делая его надежной и популярной мерой кластеризации во многих приложениях, включая сегментацию изображений и обнаружение сообщества графов. .
Модульность
Модульность графов была введена в [2] как функция качества для оценки компактности сообществ. Модульность Q определяется как:
где 2m — объем ребер, A — матрица смежности графа, k_i и k_j — степени узла i и узел j, s_i и s_j — индикатор сообщества.
Интерпретация модульности графа:
A_ij — это фактическое количество ребер между каждыми двумя узлами, поскольку матрица смежности графа определяет связность графа. А выражение (k_i*k_j)/2m дает ожидаемое количество ребер (при условии, что ребра расположены случайным образом) между каждыми двумя узлами, или, другими словами, вероятность существования ребра между узлом iи узел j(если ребра расположены случайным образом).
Следовательно, модульность можно интерпретировать как разницу между фактическим количеством ребер и ожидаемым количеством ребер (при условии, что ребра размещены случайным образом) для каждой пары узлов в одном сообществе (или одном кластере).
Модульность принимает значение между [-0,5, 1] и достигает максимума, когда сообщество отключено от остальной части графа, и минимально, когда сообщество содержит полностью отключенные узлы.
Алгоритмы разбиения графа
Мы можем легко протестировать решение для разбиения графа, используя две оценочные метрики, упомянутые ранее. Однако известно, что поиск (наилучшего) решения для разбиения графа является NP-полным. Другими словами, не существует известного эффективного алгоритма, который мог бы решить эту проблему более эффективно, чем грубая сила. С точки зрения непрофессионала, единственный возможный способ гарантироватьнаилучшее решение — это попробовать каждую возможную комбинацию… Из-за размера графиков он почти демонстрирует исчерпывающий тест (например, Brute Force ) для всех комбинаций решений кластеризации графов. Поэтому на протяжении многих лет были предложены различные эффективные алгоритмы для поиска приближенных решений для кластеризации графов.
Спектральная кластеризация
Хорошо известно, что задача min-cut может быть эффективно решена с помощью алгоритма Форда-Фалкерсона. Однако, когда накладывается условие балансировки размера (например, normalized-cut), эта проблема становится NP-полной. Спектральная кластеризация - это метод аппроксимации решений для нормализованного разреза посредством разложения собственного значения / собственного вектора по лапласиану нормализованного графа.
- Получите лапласиан графа по: L = D-A
- Выполните собственное разложение лапласиана графа. Lv=λv
- Спроектируйте граф на собственные векторы, соответствующие k наименьшим собственным значениям, с каждым столбцом спроецированных собственных векторов собственной функцией для каждого узла.
- выполнить кластеризацию k-mean на собственных функциях
Собственные значения указывают на связность графа. Собственные значения лапласиана графа дают нам представление об изменении, когда мы перемещаемся по графу. Наименьшее собственное значение всегда равно нулю. Количество обнуленных собственных значений указывает количество компонентов связности в графе. Это видно из приведенных ниже примеров.
Если вы внимательно посмотрите на собственные значения, вы заметите внезапное изменение спектра. Обычно я называю это «собственным зазором» (хотя я заметил, что для этого существуют разные определения). Разрыв указывает на количество естественно существующих кластеров на графике. Это можно наблюдать на примерах ниже:
Обратите внимание, что место возникновения «пробела» меняется с «3» на «2», что точно соответствует количеству кластеров на графике.
Это наблюдение дает нам интуицию для использования собственных значений для определения количества кластеров на графике, особенно когда мы не знаем фактическое или ожидаемое количество кластеров в наших данных (что очень часто бывает в реальных случаях использования). .
Далее все, что нам нужно сделать, это спроецировать собственные векторы на каждый узел графа. В приведенном ниже примере мы ранее определили три кластера на графике собственных значений. Поэтому мы берем только первые три собственных вектора, соответствующие трем наименьшим собственным значениям. Обратите внимание, что каждый собственный вектор содержит ровно N чисел, где N — количество узлов в графе. Мы проецируем первые три собственных вектора на каждый узел с каждым столбцом в качестве собственных признаков. Кластеризация K-средних (или любой другой метод кластеризации точек данных, который вы предпочитаете) выполняется для поиска кластеров на основе собственных признаков. Цвета в следующем примере обозначают идентифицированные кластеры. Обратите внимание, что в вычислении используются только первые три строки (т. е. первые три собственных вектора). Вы можете сделать быструю проверку, посмотрев на расстояния собственных признаков в каждом кластере. Обратите внимание, что я намеренно делаю {1,5,6} в одном кластере на графике, чтобы показать, что индекс узла не имеет значения.
Хорошо, это математика спектральной кластеризации. В реальных случаях вам не нужно проходить через все эти сложные реализации, если вы не исследователь или не хотите полностью понимать, что вы делаете. Более простой способ использования спектральной кластеризации — реализация в sklearnLibrary. Пример показан в блоке кода ниже:
import networkx as nx
from sklearn.cluster import SpectralClustering
from sklearn.metrics.cluster import normalized_mutual_info_score
import numpy as np
# Here, we create a stochastic block model with 4 clusters for evaluation
sizes = [150, 150, 150, 150]
probs = [[0.20, 0.05, 0.02, 0.03], [0.05, 0.30, 0.07, 0.02], [0.02, 0.07, 0.30, 0.05], [0.03, 0.02, 0.05, 0.50]]
G = nx.stochastic_block_model(sizes, probs, seed=0)
adj = nx.adjacency_matrix(G)
n_clusters = 4
node_labels = [G.nodes[n]['block'] for n in np.sort(G.nodes)]
spectral_clusters = SpectralClustering(n_clusters=n_clusters, assign_labels="discretize", affinity='precomputed').fit_predict(adj)
# Get the result
nmi = normalized_mutual_info_score(spectral_clusters, node_labels)
print("nmi:", nmi)
Ограничения:
- Собственное разложение большой матрицы требует больших вычислительных ресурсов. Это демонстрирует спектральную кластеризацию, которую можно применять к большим графам.
- Спектральная кластеризация является лишь приближением для оптимальных решений кластеризации.
Кластеризация Лувена
Метод Лувена [3] представляет собой быстрый алгоритм оптимизации модульности графа. Он оптимизирует модульность графа в двухэтапном итеративном процессе. На этапе 1 он начинается с назначения каждому узлу графа отдельного сообщества. После этого для каждой вершины i алгоритм оценивает изменение модульности графа при:
- узел iудален из исходного сообщества
- узел i вставляется в сообщество соседнего узла j
Фаза 1 повторяется до тех пор, пока модульность не прекратится и не будет достигнут локальный максимум.
На этапе 2 создается новый граф путем замены всех узлов в одном сообществе на объединенные в один узел, представляющий сообщество. Ребра внутри сообщества заменяются самопетлей к узлу, а ребра вне сообщества заменяются взвешенными ребрами к другим узлам. Как только новый график создан, он повторяет фазу 1 на новом графике.
Мы будем использовать реализацию в sknetwork для проверки метода Лувена. Пример показан в блоке кода ниже:
import networkx as nx
from sknetwork.clustering import Louvain
from sklearn.metrics.cluster import normalized_mutual_info_score
import numpy as np
# Here, we create a stochastic block model with 4 clusters for evaluation
sizes = [150, 150, 150, 150]
probs = [[0.20, 0.05, 0.02, 0.03], [0.05, 0.30, 0.07, 0.02], [0.02, 0.07, 0.30, 0.05], [0.03, 0.02, 0.05, 0.50]]
G = nx.stochastic_block_model(sizes, probs, seed=0)
adj = nx.adjacency_matrix(G)
n_clusters = 4
node_labels = [G.nodes[n]['block'] for n in np.sort(G.nodes)]
louvain = Louvain()
clusters = louvain.fit_transform(adj)
# Get the result
nmi = normalized_mutual_info_score(clusters, node_labels)
print("nmi:", nmi)
Заключение
В этой статье мы кратко представили разделение графа, две оценочные метрики для разделения графа и два типа алгоритмов, которые оптимизируют n-cut и модульность графа соответственно. Эти алгоритмы являются ранними методами, которые можно проследить до 2000-х годов, но они до сих пор широко используются во многих приложениях для разделения графов из-за их высокой эффективности и осуществимости.
Однако графики в недавних приложениях обычно содержат обширную информацию о функциях узла. Поэтому, хотя эти методы являются мощными и эффективными, они становятся все менее и менее применимыми к современным графовым приложениям. Ограничение этих методов заключается в том, что они только разбивают графы на основе связности графов, но не учитывают никакой информации в функциях узлов. Хотя были проделаны некоторые работы по кодированию части признаков узлов в веса ребер и выполнению разбиения взвешенного графа, количество информации, которое может быть представлено весами ребер, по-прежнему ограничено. Недавно появились методы, использующие Graph Neural Network для разделения графа, которые могут совместно учитывать связность графа и функции узлов для обнаружения сообществ в графе.
Использованная литература:
[1] Дж. Ши и Дж. Малик, «Нормализованные разрезы и сегментация изображений», IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE,vol. 22, нет. 8, стр. 888–905, 2000.
[2] М. Э. Дж. Ньюман, Модульность и структура сообщества в сетях, Phy. Ред., 2006 г.
[3] Блондель, Винсент Д., Гийом, Жан-Лу, Ламбиотт, Рено, Лефевр, Этьен, Быстрое развертывание сообществ в больших сетях, Журнал статистической механики, 2008 г.
