Материал: Алгоритм нахождения кластеров

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

На рисунке изображено разбиение, предложенное Захарием, полученное с использованием алгоритма Форда-Фалкерсона [23].

Случайно генерируемые графы

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

Модель Эрдеша - Реньи

Модель Эрдеша-Реньи [24] является одной из основных моделей генерации случайных графов. Она названа в честь Пола Эрдеша и Реньи, которые впервые представили ее в 1959 году. Другая, схожая модель была введена независимо и одновременно с моделью Эрдеша-Реньи Эдгаром Гилбертом [25]. В модели, описанной Эрдешом и Реньи, ребро между каждой парой вершин существует с некой вероятностью, заданной для всего графа.

В модели Гильберта каждое ребро имеет индивидуальную фиксированную вероятность существования, независимо от других ребер.

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

Важным достоинством этой модели является тот факт, что при количестве вершин, стремящихся к бесконечности и вероятности большей 2ln(n)/n вероятность того, что полученный граф будет связным стремится к 1.

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

Граф с выраженной структурой сообществ

Для того, чтобы генерировать графы с сообществами, алгоритм Эрдеша-Реньи был модифицирован следующим образом: Все вершины графа заранее распределяются по заданному количеству кластеров, после соединяются ребрами с вероятностью p для ребер между вершинами в одном сообществе и q - для ребер, соединяющих вершины из разных сообществ. При достаточно малых q (< 0.1) и больших p (> 0.5) такой метод позволяет получить граф с различимой структурой сообществ.

Оптимизация найденной структуры

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

Модулярность

Данная мера качества была предложена Гирваном и Ньюманом во время разработки алгоритма кластеризации вершин графа [7]. Модулярность является скалярной величиной, значение которой находится на отрезке [-1,1]. Высокое значение модулярности означает, что найденное разбиение достаточно качественно и количество ребер, лежащих внутри сообществ велико, а ребер вне сообществ мало. Практика показывает, что сети, для которых существует разбиение с модулярностью, лежащей в диапазоне от 0.3 до 1 имеют достаточно различимую структуру с сообществами.

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

Связь между количеством кластеров, модулярностью и спектром

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

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

Тем не менее, если граф обладает такой структурой, спектральный анализ позволяет заранее узнать количество сообществ в графе, а после использовать алгоритмы, требующие этой информации, такие как алгоритм Гирвана-Ньюмана или k-means, не прибегая к методу максимизации модулярности.

Связь между структурой графа и спектром

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

Были сгенерированы случайные графы, имеющие структуру с сообществами. При генерации вероятность нахождения ребра между вершинами из одного кластера была взята за p=0.4, а между вершинами из разных кластеров за q<0.4 и уменьшалась для каждого последующего эксперимента. Количество точек в графах было взято за V=500, а число кластеров за n=2. Конечно это частный случай, и на графах с другими параметрами будет наблюдаться немного другая картина, однако общий характер процесса будет схожим, за исключением разве что графов с малым количеством вершин.

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

Программная реализация

Для программной реализации описанных алгоритмов поиска сообществ и генерации графов, а также для их визуализации и составления статистики был выбран язык программирования Python и набор научных библиотек, таких как graph-tool, numpy, matplotlib и др.

Основной модуль graph-tool [27] является эффективным инструментом для манипулирования графами и их статистического анализа. В отличие от большинства других подобных модулей, обладающих схожей функциональностью, большинство методов и структур данных в graph-tool реализованы на языке программирования C++, что даёт алгоритмам, написанным с использованием этой библиотеки, высокую скорость работы.

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

Библиотека предоставляет возможности визуализации и отрисовки графов в отдельном потоке с использованием пакетов Cairo, GTK+ и Graphviz. Так же несомненным плюсом является подробная и понятная документация с множеством примеров.

Выводы

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

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

Список источников

. Kernighan, B. W.; Lin, Shen (1970). "An efficient heuristic procedure for partitioning graphs". Bell System Technical Journal 49: 291-307.

. Cheetam A.H., Hazel J.E. Binary (presence-absence) similarity coefficients // J. Paleontology, V. 43, № 5. 1969. P. 1130-1136.

3. Tan, Pang-Ning; Steinbach, Michael; Kumar, Vipin (2005), Introduction to Data Mining, ISBN 0-321-32136-7.

. Hamming, Richard W. (1950), "Error detecting and error correcting codes"

. Lloyd S. (1957). Least square quantization in PCM’s. Bell Telephone Laboratories Paper.

. Steinhaus H. (1956). Sur la division des corps materiels en parties. Bull. Acad. Polon. Sci., C1. III vol IV: 801-804.

. Girvan M. and Newman M. E. J., Community structure in social and biological networks, Proc. Natl. Acad. Sci. USA 99, 7821-7826 (2002)

8. Dragoš Cvetković, Peter Rowlinson, Slobodan Simić. Eigenspaces of Graphs. 1997. - ISBN 0-521-57352-1 <https://ru.wikipedia.org/wiki/%D0%A1%D0%BB%D1%83%D0%B6%D0%B5%D0%B1%D0%BD%D0%B0%D1%8F:%D0%98%D1%81%D1%82%D0%BE%D1%87%D0%BD%D0%B8%D0%BA%D0%B8_%D0%BA%D0%BD%D0%B8%D0%B3/0521573521>.

. Dragoš M. Cvetković, Michael Doob, Horst Sachs. Spectra of Graphs. - 1980.