Содержание курса

1. Базовые понятия теории графов и классические модели случайных графов

• Основные свойства графов
• Классические модели случайных графов
• Сравнение различных моделей

2. Математические модели оптимальных логистических сетей

• Построение оптимальных логистических сетей
• Потоковая и путевая формулировки

3. P2P Сети, Алгоритмы, DHT, Chord, Kademlia

• Одноранговые сети
• Распределенные хеш-таблицы (DHT)
• Алгоритмы Chord и Kademlia

4. Навигационные графы со свойством тесного мира и графы для приближенного поиска ближайшего соседа

• Навигационные свойства сетей малого мира
• Поиск ближайших соседей на основе графов
• Применение в системах рекомендаций

5. Модель навигационного тестого мира Клейнберга

• Модель Клейнберга
• Доказательство логарифмеческой оценки

6. Кластеризация в сетях - часть 1. Поиск непересекающихся сообществ

• Минимальный разрез
• Модулярность и конфигурационная модель – Алгоритм распространения меток
• Кластеризация используя математическое программирование

7. Кластеризация в сетях - часть 2. Поиск пересекающихся сообществ

• Подход группировки вокруг рёбер (разделение рёбер). Линейный граф.
• Коммутационное расстояние и его коррекция.
• Метод LPAM (Link Partitiong Around Medoids)
• Применение матричной факторизации для поиска пересекающихся сообществ: метод BIGCLAM

8. Векторные вложения графов

• Методы векторного вложения вложения регулярных графов: Node2Vec, Graph2Vec, AnonymusWalk
• Способы векторного вложения графов знаний: TransE, RotatE, PairRE
• Применение в задачах машинного обучения

9. Графовые нейроные сети

• Простая свёрточная нейронная сеть (GNN)
• GraphSAGE (SAmple and aggreGatE)
• Graph Attention Networks (GAT)
• Обобщающий фреймворк Message Passing Neural Networks (MPNN)

---

Курсовая работа: Конкурс по построению оптимальной логистической сети

В рамках курсовой работы на платформе Яндекс.Контест проводится конкурс по построению оптимальной логистической сети с нелинейной стоимостью рёбер и учётом перегруза

Описание задачи

Смотри описание в файле MCF Extensions

Требования:

• Участники должны предложить алгоритм построения логистической сети
• Алгоритм должен учитывать нелинейную стоимость рёбер
• Алгоритм должен учитывать эффект перегруза и штрафы за перегруз
• Предоставить анализ эффективности предложенного решения

Критерии оценки:

• Выполнение всех ограничений
• Стоимость решения

Материалы лежат в директории optimal-logistic-network-contest/

optimal-logistic-network-contest/validator.py – проверка решения

---

Вопросы к экзамену

Вопросы к экзамену перечислены в файле Exam-Questions.md

---

Благодарности

Илья Антонов создал validator.py. Дмитрий Шустров настроил и создал соревнование в Яндекс.Контесте