Network Structure Analysis

2026/2027

Academic Year

RUS

Instruction in Russian

3

ECTS credits

Delivered at:

Department of Applied Mathematics and Informatics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Compulsory course

When:

2 year, 2 module

Instructor

Ponomarenko, Alexander

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

Аннотация

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

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

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

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

• Знаем модели графов со свойствами "тесного мира". Может запрограммировать.
• Знает концепцию DHT и принцип работы Chord протокола.
• Понимает метод вложения графов в векторное пространство graph2vec
• Понимает метод спектральной кластеризации. Может запрограммировать.
• Понимает модель Клайнберга.
• Студенты научатся различать типы сетей и выбирать адекватные модели случайных графов для описания реальных систем
• Студенты освоят основные понятия теории графов и научатся вычислять ключевые метрики сетевой структуры: степени, расстояния, кластеризацию и центральности
• Студенты будут способны анализировать структурные свойства сетей и интерпретировать их в контексте прикладных задач
• Студенты поймут принципы формирования масштабно-инвариантных и маломирных сетей и их значение в социальных, биологических и технических системах
• Анализирует логистические системы (транспортные сети, цепочки поставок, распределение трафика) и формализует их в виде ориентированного графа с вершинами (склады, потребители) и рёбрами (маршруты с ограничениями)
• Формулирует задачу 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
• Network science, Barabasi, A.-L., 2019
• Small Worlds : the dynamics of networks between order and randomness, 262 p., Watts, D. J., 2004
• Supply Chain Optimization, edited by Joseph Geunes, Panos M. Pardalos, 413 p., , 2005
• Методы и модели исследования операций : целочисленное программирование, Кофман, А., 1977

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

• Linked : the new science of networks, 280 p., Barabasi, A.-L., 2002
• Networks : An Introduction, 772 p., Newman, M. E. J., 2012
• Networks: optimisation and evolution, Whittle, P., 2012
• Newman, M., Watts, D. J., and Barabási, A. The Structure and Dynamics of Networks. – Princeton University Press, 2006. – 592 pp.
• Six degrees : the science of a connected age, Watts, D., 2003
• Вероятностные методы в комбинаторике, Эрдеш, П., 1976
• Модели случайных графов - Райгородский А. М. - Московский центр непрерывного математического образования - 978-5-4439-2204-1 - 2021 - русский - https://e.lanbook.com/book/267542 - ЛАНЬ - 267542

Презентации

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

Авторы

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