Network Structure Analysis

2023/2024

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, 1 module

Instructor

Ponomarenko, Alexander

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

Аннотация

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

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

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

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

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

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

• Основные характеристики графов
• Google’s PageRank, HITS
• Случайные графы.
• Модели графов со свойствами "тесного мира"
• Алгоритмы кластеризации в сетях
• Модели навигационных тесных миров
• Методы вложения графов в векторные пространства.

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

• Лабораторная работа по анализу свойств случайных графов
  Взять 3 моделий случайных графов: 1) Модель Эрдёша — Реньи (n,p) 2) Модель Watts-Strogatz 3) Модель Barabási–Albert Исследовать как зависят характеристики графов от параметров моделей. Например, n, p, k Характеристики графов: коэф. кластеризации, диаметр, плотность, распределение степеней вершин, чем больше тем лучше. Зависимости нужно аппроксимировать аналитической функцией.
• Лабораторная работа – "Навигационные тесные миры"
  Для 2х моделей случайных графов со свойствами навигации исследовать, как зависят характеристики графов от параметров моделей. Например, n, p, q, k, размерности пространства. Модели: 1) Навигационный тесный мир Klainberg 2) NSW (Ponomarenko, Malkov) Характеристики графов: коэф. кластеризации, диаметр, плотность, распределение степеней вершин, чем больше тем лучше. Зависимости нужно аппроксимировать аналитической функцией.

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

• 2023/2024 учебный год 1 модуль
  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

Авторы

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