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

Кумарбекова, Мунара Кумарбековна Кафедра высшей и прикладной математики
Бесплатно
В избранное
Работа доступна по лицензии Creative Commons:«Attribution» 4.0

Введение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1 Постановка задачи кластеризации графа . . . . . . . . . . . . . . . . . . 5
1.1 Основные определения и обозначения . . . . . . . . . . . . . . . . . 6
1.2 Общая постановка задачи кластеризации графа . . . . . . . . . . . . 8
1.3 Выводы по первой главе . . . . . . . . . . . . . . . . . . . . . . . . . 8
2 Описание алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.1 Задачи кластеризации графа, использующие метрики . . . . . . . . . 9
2.1.1 Пример решения задач GC, GC2 , GC≤3 . . . . . . . . . . . . . 10
2.2 Задачи иерархической кластеризации графа . . . . . . . . . . . . . . 15
2.3 Задача спектральной кластеризации графа . . . . . . . . . . . . . . . 18
2.4 Задача кластеризации графа, основанные на модулярности . . . . . . 21
2.5 Выводы по второй главе . . . . . . . . . . . . . . . . . . . . . . . . . 22
3 Вычислительные эксперименты . . . . . . . . . . . . . . . . . . . . . . . 24
3.1 Способы машинного представления графов . . . . . . . . . . . . . . 24
3.2 Вычислительные эксперименты . . . . . . . . . . . . . . . . . . . . . 25
3.3 Выводы по третьей главе . . . . . . . . . . . . . . . . . . . . . . . . . 26
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
Список использованных источников . . . . . . . . . . . . . . . . . . . . . . . 28

Актуальность работы. Изучение графов является актуальной задачей, по-
скольку на практике графы часто возникают при упрощении сложных систем. К
примеру в виде графа отображают:
– взаимосвязи различных сайтов в интернете,
– социальные сети (сети контактов),
– генные сети в молекулярной биологии,
– порты, аэропорты, города (в качестве узлов графа) и соединяющие пути (в
качестве ребер).
При работе с графами часто бывает полезно обнаружить в нем какую–нибудь
структуру, например, группы вершин, внутри которых связей много, а между
группами – мало. На практике сталкиваемся с большими графами, и для опре-
деления групп вершин, необходима помощь компьютера. Поэтому и создаются
огромное количество алгоритмов, обладающих всевозможными свойствами.
Обзор литературы. В связи с растущим интересом исследователей к задачам
кластеризации графа за последние годы было написано немало статей, освещаю-
щих разные аспекты данной темы. Граф – конечный набор объектов произволь-
ной природы, называемых вершинами, и связей между некоторыми вершинами,
называемых ребрами. В работе [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. Быкова, В. В. Комбинаторные алгоритмы: множества, графы, коды : учебное
пособие для студентов вузов, обучающихся по направлению “Математика и
компьютерные науки”/ В. В. Быкова ; Сиб. федер. ун-т, Ин-т математики и

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

Заказать новую

Лучшие эксперты сервиса ждут твоего задания

от 5 000 ₽

Не подошла эта работа?
Закажи новую работу, сделанную по твоим требованиям

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

    Хочешь уникальную работу?

    Больше 3 000 экспертов уже готовы начать работу над твоим проектом!

    Катерина М. кандидат наук, доцент
    4.9 (522 отзыва)
    Кандидат технических наук. Специализируюсь на выполнении работ по метрологии и стандартизации
    Кандидат технических наук. Специализируюсь на выполнении работ по метрологии и стандартизации
    #Кандидатские #Магистерские
    836 Выполненных работ
    Глеб С. преподаватель, кандидат наук, доцент
    5 (158 отзывов)
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной с... Читать все
    Стаж педагогической деятельности в вузах Москвы 15 лет, автор свыше 140 публикаций (РИНЦ, ВАК). Большой опыт в подготовке дипломных проектов и диссертаций по научной специальности 12.00.14 административное право, административный процесс.
    #Кандидатские #Магистерские
    216 Выполненных работ
    Андрей С. Тверской государственный университет 2011, математический...
    4.7 (82 отзыва)
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на... Читать все
    Учился на мат.факе ТвГУ. Любовь к математике там привили на столько, что я, похоже, никогда не перестану этим заниматься! Сейчас работаю в IT и пытаюсь найти время на продолжение диссертационной работы... Всегда готов помочь! ;)
    #Кандидатские #Магистерские
    164 Выполненных работы
    Евгения Р.
    5 (188 отзывов)
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и со... Читать все
    Мой опыт в написании работ - 9 лет. Я специализируюсь на написании курсовых работ, ВКР и магистерских диссертаций, также пишу научные статьи, провожу исследования и создаю красивые презентации. Сопровождаю работы до сдачи, на связи 24/7 ?
    #Кандидатские #Магистерские
    359 Выполненных работ
    Екатерина С. кандидат наук, доцент
    4.6 (522 отзыва)
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    Практически всегда онлайн, доработки делаю бесплатно. Дипломные работы и Магистерские диссертации сопровождаю до защиты.
    #Кандидатские #Магистерские
    1077 Выполненных работ
    Катерина В. преподаватель, кандидат наук
    4.6 (30 отзывов)
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации... Читать все
    Преподаватель одного из лучших ВУЗов страны, научный работник, редактор научного журнала, общественный деятель. Пишу все виды работ - от эссе до докторской диссертации. Опыт работы 7 лет. Всегда на связи и готова прийти на помощь. Вместе удовлетворим самого требовательного научного руководителя. Возможно полное сопровождение: от статуса студента до получения научной степени.
    #Кандидатские #Магистерские
    47 Выполненных работ
    Рима С.
    5 (18 отзывов)
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный универси... Читать все
    Берусь за решение юридических задач, за написание серьезных научных статей, магистерских диссертаций и дипломных работ. Окончила Кемеровский государственный университет, являюсь бакалавром, магистром юриспруденции (с отличием)
    #Кандидатские #Магистерские
    38 Выполненных работ
    Оксана М. Восточноукраинский национальный университет, студент 4 - ...
    4.9 (37 отзывов)
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политоло... Читать все
    Возможно выполнение работ по правоведению и политологии. Имею высшее образование менеджера ВЭД и правоведа, защитила кандидатскую и докторскую диссертации по политологии.
    #Кандидатские #Магистерские
    68 Выполненных работ
    Александр О. Спб государственный университет 1972, мат - мех, преподав...
    4.9 (66 отзывов)
    Читаю лекции и веду занятия со студентами по матанализу, линейной алгебре и теории вероятностей. Защитил кандидатскую диссертацию по качественной теории дифференциальн... Читать все
    Читаю лекции и веду занятия со студентами по матанализу, линейной алгебре и теории вероятностей. Защитил кандидатскую диссертацию по качественной теории дифференциальных уравнений. Умею быстро и четко выполнять сложные вычислительные работ
    #Кандидатские #Магистерские
    117 Выполненных работ

    Другие учебные работы по предмету

    Кооперативные игры на гиперграфах
    📅 2019год
    🏢 Санкт-Петербургский государственный университет