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

2025/2026

Учебный год

RUS

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

3

Кредиты

Кто читает:

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

Статус:

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

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

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

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

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

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

Аннотация

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

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

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

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

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

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

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

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

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

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

• 2025/2026 1st module
  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

Презентации

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

Авторы

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