• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта
Магистратура 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 * Лабораторная работа – "Навигационные тесные миры"
Список литературы

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

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

  • 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

Авторы

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