- Базовые понятия: cтепень вершины, путь, рдиаметр графа и коэффициенты кластеризации, меры центральностей.
- Классические модели случайных графов: модель Эрдёша-Реньи, Уаттса-Строгаца, Барабаши-Альберта – свойства и различия.
- Какие метрики используются для описания сетей: степень узла, диаметр, коэффициент кластеризации, центральности?
- Что такое распределение степеней и как оно различается в разных моделях графов?
- Задача Multi-Commodity Flow: потоковая и путевая формулировки, основные ограничения.
- Как линеаризуется нелинейная стоимость рёбер в задачах оптимизации логистических сетей?
- Что такое распределённые хеш-таблицы (DHT) и каковы их основные свойства?
- Протоколы Chord и Kademlia: архитектура, алгоритмы маршрутизации и схожесть/различие.
- Как устроены торрент-сети и какую роль в них играет DHT на основе Kademlia?
- Навигационные графы и алгоритм направленного обхода графа (greeedy walk). Диаграма Вороного и граф Делоне.
- Модель Клейнберга: навигационный тесный мир, параметр r=2, децентрализованный алгоритм поиска.
- Почему при r=2 в модели Клейнберга достигается оптимальный баланс между локальными и дальними связями?
- Навигационные тесные миры для поиска ближайших соседей: NSW и HNSW.
- Как устроена иерархическая структура в HNSW и какие параметры влияют на качество поиска?
- Какие существуют подходы к кластеризации в сетях: разрезание графа, модулярность, Label Propagation?
- Что такое модулярность и какие есть ограничения у этой меры при обнаружении сообществ?
- Объясните алгоритмы максимизации модулярности: Newman, Louvain, CNM.
- Каковы особенности поиска пересекающихся сообществ и в чем различие между node partitioning и link partitioning?
- Опишите метод LPAM для обнаружения пересекающихся сообществ. Коммутационное расстояние (commute distance).
- Опишите метод BIGCLAM: модель аффилиаций, матрица принадлежности, оптимизация.
- Векторные вложения для графов: от word2vec к node2vec, graph2vec и anonymous walk embeddings.
- Как работает алгоритм node2vec и в чем различие между BFS- и DFS-подобными обходами?
- Как устроены анонимные блуждания (anonymous walks) и в чем их преимущество?
- Графовые нейронные сети: основные архитектуры GCN, GraphSAGE, GAT.
- Как работает механизм внимания в Graph Attention Networks (GAT)?
- Опишите обобщающий фреймворк MPNN (Message Passing Neural Networks).
- Какое отношение имееет Weisfeiler-Lehman (WL) тест к графовым нейроным сетям?
- В чем различие между трансдуктивной и индуктивной постановкой эксперимента применительно к GNN?
- Применение графовых нейронных сетей в задачах рекомендательных систем и обработки социальных сетей.