Магистратура 2022/2023

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

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

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

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

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

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

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

Охват аудитории: для всех кампусов НИУ ВШЭ

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

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

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

Кредиты: 6

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

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

Аннотация

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

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

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

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

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

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

• Основные характеристики графов
• Google’s PageRank, HITS
• Случайные графы.
• Модели графов со свойствами "тесного мира"
• Алгоритмы кластеризации в сетях
• Модели навигационных тесных миров
• Методы вложения графов в векторные пространства.

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

• Лабораторная работа-1
  Учащиеся пишут программный код задач. Решение отправляется онлайн в систему тестирования. Задача засчитывается после того, как программа успешно проходит все тесты.
• Лабораторная работа-2
• Лабораторная работа-3
• Лабораторная работа-4

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

• 2022/2023 учебный год 1 модуль
  0.25 * Лабораторная работа-3 + 0.25 * Лабораторная работа-2 + 0.25 * Лабораторная работа-4 + 0.25 * Лабораторная работа-1

Список литературы

Рекомендуемая основная литература

• Ming-Yang Kao. Encyclopedia of Algorithms. Springer, New York, NY, 2016

Рекомендуемая дополнительная литература

• Panos M. Pardalos, Ding-Zhu Du, Ronald L. Graham. Handbook of Combinatorial Optimization. Springer Science+Business Media, New York, 2013.
• Комбинаторика и теория вероятностей, учебное пособие, 99 с., Райгородский, А. М., 2013

Авторы

• Пономаренко Александр Александрович
• Калягин Валерий Александрович