Методы анализа сетевых структур

Магистратура 2019/2020

Статус: Курс обязательный (Интеллектуальный анализ данных)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Кафедра прикладной математики и информатики (Нижний Новгород)

Где читается: Факультет информатики, математики и компьютерных наук (Нижний Новгород)

Когда читается: 2-й курс, 2 модуль

Формат изучения: без онлайн-курса

Преподаватели: Пономаренко Александр Александрович

Прогр. обучения: Интеллектуальный анализ данных

Язык: русский

Кредиты: 6

Контактные часы: 32

Полная версия программы учебной дисциплины

Аннотация

Как отличить сеть развившуюся естественным образом от сети построенную искусственно; определить критические и наиболее важные элементы в сети; выделить сообщества в сетях; предсказать появления ребра; предсказать как сеть будет развиваться с течением времени – всё это вы узнаете в рамках данного курса.

Цель освоения дисциплины

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

Планируемые результаты обучения

Знает основные характеристики графов
Понимает Page Rank алгоритм. Понимает модель случайного блуждателя
Понимает модель. Умеет вычислять вероятность возникновения фиксированной структуры,.
Знаем модели графов со свойствами "тесного мира". Может запрограммировать.
Понимает метод спектральной кластеризации. Может запрограммировать.
Знает концепцию DHT и принцип работы Chord протокола.
Понимает модель Клайнберга.
Понимает метод вложения графов в векторное пространство graph2vec

Содержание учебной дисциплины

Основные характеристики графов
Способы задания графа. Список смежности. Матрица инцидентности. Основные характери-стики графов. Диаметр графа. Плотность графа. Коэффициент кластеризации. Распределение степеней вершин. Клики. Компоненты связанности. Мосты. Кратчайшие пути.
Google’s PageRank, HITS
Модель случайного блуждания по сети. Google’s Page Rank. HITS алгоритм.
Случайные графы.
Модель Эрдеша Реньи.
Модели графов со свойствами "тесного мира"
Модель Ватса-Строгатца. Модель Барабаши-Альберта.
Алгоритмы кластеризации в сетях
Спектральная кластеризация. Modularity. Подходы к поиску перекрывающихся сообществ.
Модели навигационных тесных миров
DHT и Chord протокол. Модель Клайнберга. Задача поиска ближайшего соседа. Диаграмма Вороного. Граф Делоне. Voronet, Raynet, SAT, GNAT. Метризованный тесный мир.
Методы вложения графов в векторные пространства.
Алгоритм Graph2vec

Элементы контроля

Самостоятельная работа по теме "случайные графы"
Лабораторная работа "Реализовать алгоритм спектральной кластеризации"
Лабораторная работа "Реализовать алгоритм Page Rank"
Лабораторная работа "Реализовать одну из моделей Тесного мира"

Промежуточная аттестация

Промежуточная аттестация (2 модуль)
0.25 * Лабораторная работа "Реализовать алгоритм Page Rank" + 0.25 * Лабораторная работа "Реализовать алгоритм спектральной кластеризации" + 0.25 * Лабораторная работа "Реализовать одну из моделей Тесного мира" + 0.25 * Самостоятельная работа по теме "случайные графы"

Программа дисциплины