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

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

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

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

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

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

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

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

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

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

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

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

Кредиты: 3

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

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

Аннотация

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

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

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

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

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

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

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

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

Лабораторная работа по анализу свойств случайных графов
Взять 3 моделий случайных графов: 1) Модель Эрдёша — Реньи (n,p) 2) Модель Watts-Strogatz 3) Модель Barabási–Albert Исследовать как зависят характеристики графов от параметров моделей. Например, n, p, k Характеристики графов: коэф. кластеризации, диаметр, плотность, распределение степеней вершин, чем больше тем лучше. Зависимости нужно аппроксимировать аналитической функцией.
Лабораторная работа – "Навигационные тесные миры"
Для 2х моделей случайных графов со свойствами навигации исследовать, как зависят характеристики графов от параметров моделей. Например, n, p, q, k, размерности пространства. Модели: 1) Навигационный тесный мир Klainberg 2) NSW (Ponomarenko, Malkov) Характеристики графов: коэф. кластеризации, диаметр, плотность, распределение степеней вершин, чем больше тем лучше. Зависимости нужно аппроксимировать аналитической функцией.

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

2023/2024 учебный год 1 модуль
0.5 * Лабораторная работа по анализу свойств случайных графов + 0.5 * Лабораторная работа – "Навигационные тесные миры"

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

Авторы

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

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