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

2026/2027

Учебный год

RUS

Обучение ведется на русском языке

3

Кредиты

Кто читает:

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

Статус:

Курс обязательный

Когда читается:

2-й курс, 2 модуль

Преподаватель

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

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

Аннотация

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

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

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

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

• Знаем модели графов со свойствами "тесного мира". Может запрограммировать.
• Знает концепцию DHT и принцип работы Chord протокола.
• Понимает метод спектральной кластеризации. Может запрограммировать.
• Понимает модель Клайнберга.
• Студенты научатся различать типы сетей и выбирать адекватные модели случайных графов для описания реальных систем
• Студенты освоят основные понятия теории графов и научатся вычислять ключевые метрики сетевой структуры: степени, расстояния, кластеризацию и центральности
• Студенты будут способны анализировать структурные свойства сетей и интерпретировать их в контексте прикладных задач
• Студенты поймут принципы формирования масштабно-инвариантных и маломирных сетей и их значение в социальных, биологических и технических системах
• Анализирует логистические системы (транспортные сети, цепочки поставок, распределение трафика) и формализует их в виде ориентированного графа с вершинами (склады, потребители) и рёбрами (маршруты с ограничениями)
• Формулирует задачу Multi-Commodity Flow (MCF) для заданного набора товаропотоков, включая целевую функцию минимизации затрат и систему ограничений (баланс потока, пропускная способность)
• Сравнивает и выбирает подходящую формулировку задачи (потоковую на рёбрах или путевую) в зависимости от размерности и структуры исходных данных, аргументируя выбор с точки зрения вычислительной эффективности
• Преобразует нелинейную функцию стоимости (зависящую от количества транспортных средств) в линеаризованную модель целочисленного линейного программирования (MILP) путём введения дополнительных переменных
• Применяет методы декомпозиции (генерация столбцов, релаксация Лагранжа) и эвристические алгоритмы для поиска приближённых решений крупномасштабных задач MCF в условиях комбинаторного взрыва
• Оценивает эффективность различных практических подходов (агрегация данных, использование солверов Gurobi/OR-Tools) и обосновывает выбор инструментов для решения реальных логистических задач с учётом компромисса между точностью и скоростью вычислений.

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

• Базовые характеристики и классические модели случайных графов
• Построение оптимальных логистических сетей
• Модели графов со свойствами "тесного мира"
• Модели навигационных тесных миров
• Графовые нейроные сети
• Алгоритмы кластеризации в сетях

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

• Навигационные графы
• Модели случайных графов

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

• 2026/2027 2nd module
  0.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

Презентации

• Navigable Small Worlds - Klainberg Model
  Модель навигационного тесного мира Клайнберга с доказательством логарифмической сложностью поиска
• Кластеризация в сетях. Поиск непересекающихся сообществ.
  - Минимальный разрез - Модулярность и конфигурационная модель – Алгоритм распространения меток - Кластеризация используя математическое программирование
• Кластеризация в сетях. Поиск пересекающихся сообществ
  – Подход группировки вокруг рёбер. Линейный граф. – Коммутационное расстояние и его коррекция. – Метод LPAM – Применение матричной факторизации для поиска пересекающихся сообществ: метод BIGCLAM

Авторы

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