Исследование задач кластеризации графа

Актуальность работы. Изучение графов является актуальной задачей, по-
скольку на практике графы часто возникают при упрощении сложных систем. К
примеру в виде графа отображают:
– взаимосвязи различных сайтов в интернете,
– социальные сети (сети контактов),
– генные сети в молекулярной биологии,
– порты, аэропорты, города (в качестве узлов графа) и соединяющие пути (в
качестве ребер).
При работе с графами часто бывает полезно обнаружить в нем какую–нибудь
структуру, например, группы вершин, внутри которых связей много, а между
группами – мало. На практике сталкиваемся с большими графами, и для опре-
деления групп вершин, необходима помощь компьютера. Поэтому и создаются
огромное количество алгоритмов, обладающих всевозможными свойствами.
Обзор литературы. В связи с растущим интересом исследователей к задачам
кластеризации графа за последние годы было написано немало статей, освещаю-
щих разные аспекты данной темы. Граф – конечный набор объектов произволь-
ной природы, называемых вершинами, и связей между некоторыми вершинами,
называемых ребрами. В работе [8] собраны основные термины и основопола-
гающие понятия и утверждения теории графов. Кластеризация графа [1, 15] –
это задача о нахождении таких кластеров вершин, имеющих мало ребер между
группами, и много ребер внутри кластеров. В литературе рассмотрены несколько
задач кластеризации графа [35, 19]. Например, в обзорной статье, о задач кла-
стеризации графа [9, 18, 33], рассматриваются три задачи кластеризации графа и
предложены приближенные алгоритмы. В статье [26, 27] обсуждается более 15
алгоритмов, которые классифицированы по нескольким группам. Наборы дан-
ных из разных областей и имеющие разный смысл для сравнения алгоритмов,
можно найти на следующих сайтах [30, 31, 32].
Цели и задачи. Целью работы является исследование задач кластеризации
графа и анализ алгоритмов их решения. Достижение поставленной цели реали-
зуется путем решения следующих задач.
1. Провести обзор литературы и изучить задачи кластеризации графа.
2. Исследовать существующие постановки задач кластеризации графа и ал-
горитмы их решения.
3. Провести вычислительные эксперименты.
Структура диссертации. Объём диссертационной работы 30 страниц, на кото-
рых размещены 13 рисунков и 1 таблица. При написании работы использовалось
39 источников.
ЗАКЛЮЧЕНИЕ
Основная цель диссертации – представить базовую идею традиционных, обыч-
но используемых алгоритмов кластеризации, проанализировать преимущества
и недостатки каждого из них. Представить полный список всех существующих
алгоритмов кластеризации из–за разнообразия подходов, информации, пересече-
ния областей исследований достаточно сложно. Проделанный анализ позволяет
легко выбрать подходящую группу алгоритмов исходя из технической задачи.
В диссертационной работе получены следующие основные результаты.
– Сделан обзор существующих подходов к решению задач кластеризации
графа.
– Исследованы шесть постановок задач кластеризации.
– Исследованы шесть алгоритмов кластеризации графа и приведены приме-
ры их работы.
– Для спектрального алгоритма и алгоритма Гирвана–Ньюмена проведены
вычислительные эксперименты, с использованием библиотек Python.
Работа докладывалась на научном семинаре кафедры Высшей и прикладной ма-
тематики 2021.
СПИСОК ИСПОЛЬЗОВАНННЫХ ИСТОЧНИКОВ
1. Айвазян, С. А. Прикладная статистика : Классификация и снижение размер-
ности / С. А. Айвазян, В. М. Бухштабер, И. С. Енюков, Л. Д. Мешалкин –
Москва : Финансы и статистика, 1989. – 450 с.
2. Быкова, В. В. Комбинаторные алгоритмы: множества, графы, коды : учебное
пособие для студентов вузов, обучающихся по направлению “Математика и
компьютерные науки”/ В. В. Быкова ; Сиб. федер. ун-т, Ин-т математики и