Магистратура
2026/2027




Методы анализа сетевых структур
ID 1188952
Статус:
Курс обязательный (Интеллектуальный анализ данных)
Когда читается:
2-й курс, 2 модуль
Охват аудитории:
для всех кампусов НИУ ВШЭ
Преподаватели:
Пономаренко Александр Александрович
Язык:
русский
Кредиты:
3
Контактные часы:
28
Программа дисциплины
Аннотация
Как отличить сеть развившуюся естественным образом от сети построенную искусственно; определить критические и наиболее важные элементы в сети; выделить сообщества в сетях; предсказать появления ребра; предсказать как сеть будет развиваться с течением времени – всё это вы узнаете в рамках данного курса.
Цель освоения дисциплины
- Владеть методами кластеризации
- Знать и разбираться в различных моделях случайных графов
- Владеть методами поиска наиболее важных элементов в сети
- Понимать принципы работы графовых нейронных сетей
Планируемые результаты обучения
- Знаем модели графов со свойствами "тесного мира". Может запрограммировать.
- Знает концепцию DHT и принцип работы Chord протокола.
- Понимает метод спектральной кластеризации. Может запрограммировать.
- Понимает модель Клайнберга.
- Студенты научатся различать типы сетей и выбирать адекватные модели случайных графов для описания реальных систем
- Студенты освоят основные понятия теории графов и научатся вычислять ключевые метрики сетевой структуры: степени, расстояния, кластеризацию и центральности
- Студенты будут способны анализировать структурные свойства сетей и интерпретировать их в контексте прикладных задач
- Студенты поймут принципы формирования масштабно-инвариантных и маломирных сетей и их значение в социальных, биологических и технических системах
- Анализирует логистические системы (транспортные сети, цепочки поставок, распределение трафика) и формализует их в виде ориентированного графа с вершинами (склады, потребители) и рёбрами (маршруты с ограничениями)
- Формулирует задачу Multi-Commodity Flow (MCF) для заданного набора товаропотоков, включая целевую функцию минимизации затрат и систему ограничений (баланс потока, пропускная способность)
- Сравнивает и выбирает подходящую формулировку задачи (потоковую на рёбрах или путевую) в зависимости от размерности и структуры исходных данных, аргументируя выбор с точки зрения вычислительной эффективности
- Преобразует нелинейную функцию стоимости (зависящую от количества транспортных средств) в линеаризованную модель целочисленного линейного программирования (MILP) путём введения дополнительных переменных
- Применяет методы декомпозиции (генерация столбцов, релаксация Лагранжа) и эвристические алгоритмы для поиска приближённых решений крупномасштабных задач MCF в условиях комбинаторного взрыва
- Оценивает эффективность различных практических подходов (агрегация данных, использование солверов Gurobi/OR-Tools) и обосновывает выбор инструментов для решения реальных логистических задач с учётом компромисса между точностью и скоростью вычислений.
Содержание учебной дисциплины
- Базовые характеристики и классические модели случайных графов
- Построение оптимальных логистических сетей
- Модели графов со свойствами "тесного мира"
- Модели навигационных тесных миров
- Графовые нейроные сети
- Алгоритмы кластеризации в сетях
Промежуточная аттестация
- 2026/2027 2nd module0.5 * Навигационные графы + 0.5 * Модели случайных графов
Список литературы
Рекомендуемая основная литература
- Ming-Yang Kao. Encyclopedia of Algorithms. Springer, New York, NY, 2016
- Графы и алгоритмы - Алексеев В.Е., Таланов В.А. - Национальный Открытый Университет "ИНТУИТ" - 5-9556-0066-3 - 2016 - русский - https://e.lanbook.com/book/100593 - ЛАНЬ - 100593
- Наливайко Л.В., Шунскайте Д.С. - Комбинаторика, теория вероятностей и математическая статистика - НИЦ ИНФРА-М - 2024 - https://znanium.ru/catalog/document?id=445227 - 445227 - ZNANIUM