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

Кумарбекова, Мунара Кумарбековна Кафедра высшей и прикладной математики
Бесплатно
В избранное
Работа доступна по лицензии 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 экспертов уже готовы начать работу над твоим проектом!

    Анна К. ТГПУ им.ЛН.Толстого 2010, ФИСиГН, выпускник
    4.6 (30 отзывов)
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помог... Читать все
    Я научный сотрудник федерального музея. Подрабатываю написанием студенческих работ уже 7 лет. 3 года назад начала писать диссертации. Работала на фирмы, а так же помогала студентам, вышедшим на меня по рекомендации.
    #Кандидатские #Магистерские
    37 Выполненных работ
    Дарья П. кандидат наук, доцент
    4.9 (20 отзывов)
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных... Читать все
    Профессиональный журналист, филолог со стажем более 10 лет. Имею профильную диссертацию по специализации "Радиовещание". Подробно и серьезно разрабатываю темы научных исследований, связанных с журналистикой, филологией и литературой
    #Кандидатские #Магистерские
    33 Выполненных работы
    Юлия К. ЮУрГУ (НИУ), г. Челябинск 2017, Институт естественных и т...
    5 (49 отзывов)
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - ин... Читать все
    Образование: ЮУрГУ (НИУ), Лингвистический центр, 2016 г. - диплом переводчика с английского языка (дополнительное образование); ЮУрГУ (НИУ), г. Челябинск, 2017 г. - институт естественных и точных наук, защита диплома бакалавра по направлению элементоорганической химии; СПХФУ (СПХФА), 2020 г. - кафедра химической технологии, регулирование обращения лекарственных средств на фармацевтическом рынке, защита магистерской диссертации. При выполнении заказов на связи, отвечаю на все вопросы. Индивидуальный подход к каждому. Напишите - и мы договоримся!
    #Кандидатские #Магистерские
    55 Выполненных работ
    Антон П. преподаватель, доцент
    4.8 (1033 отзыва)
    Занимаюсь написанием студенческих работ (дипломные работы, маг. диссертации). Участник международных конференций (экономика/менеджмент/юриспруденция). Постоянно публик... Читать все
    Занимаюсь написанием студенческих работ (дипломные работы, маг. диссертации). Участник международных конференций (экономика/менеджмент/юриспруденция). Постоянно публикуюсь, имею высокий индекс цитирования. Спикер.
    #Кандидатские #Магистерские
    1386 Выполненных работ
    Евгений А. доктор, профессор
    5 (154 отзыва)
    Более 40 лет занимаюсь преподавательской деятельностью. Специалист в области философии, логики и социальной работы. Кандидатская диссертация - по логике, докторская - ... Читать все
    Более 40 лет занимаюсь преподавательской деятельностью. Специалист в области философии, логики и социальной работы. Кандидатская диссертация - по логике, докторская - по социальной работе.
    #Кандидатские #Магистерские
    260 Выполненных работ
    Вирсавия А. медицинский 1981, стоматологический, преподаватель, канди...
    4.5 (9 отзывов)
    руководитель успешно защищенных диссертаций, автор около 150 работ, в активе - оппонирование, рецензирование, написание и подготовка диссертационных работ; интересы - ... Читать все
    руководитель успешно защищенных диссертаций, автор около 150 работ, в активе - оппонирование, рецензирование, написание и подготовка диссертационных работ; интересы - медицина, биология, антропология, биогидродинамика
    #Кандидатские #Магистерские
    12 Выполненных работ
    Александра С.
    5 (91 отзыв)
    Красный диплом референта-аналитика информационных ресурсов, 8 лет преподавания. Опыт написания работ вплоть до докторских диссертаций. Отдельно специализируюсь на повы... Читать все
    Красный диплом референта-аналитика информационных ресурсов, 8 лет преподавания. Опыт написания работ вплоть до докторских диссертаций. Отдельно специализируюсь на повышении уникальности текста и оформлении библиографических ссылок по ГОСТу.
    #Кандидатские #Магистерские
    132 Выполненных работы
    Анна С. СФ ПГУ им. М.В. Ломоносова 2004, филологический, преподав...
    4.8 (9 отзывов)
    Преподаю англ язык более 10 лет, есть опыт работы в университете, школе и студии англ языка. Защитила кандидатскую диссертацию в 2009 году. Имею большой опыт написания... Читать все
    Преподаю англ язык более 10 лет, есть опыт работы в университете, школе и студии англ языка. Защитила кандидатскую диссертацию в 2009 году. Имею большой опыт написания и проверки (в качестве преподавателя) контрольных и курсовых работ.
    #Кандидатские #Магистерские
    16 Выполненных работ
    Александр Р. ВоГТУ 2003, Экономический, преподаватель, кандидат наук
    4.5 (80 отзывов)
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфин... Читать все
    Специальность "Государственное и муниципальное управление" Кандидатскую диссертацию защитил в 2006 г. Дополнительное образование: Оценка стоимости (бизнеса) и госфинансы (Казначейство). Работаю в финансовой сфере более 10 лет. Банки,риски
    #Кандидатские #Магистерские
    123 Выполненных работы

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

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