Большие графы и модели сложных сетей

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск

Записаться на спецкурс: здесь.

Спецкурс для студентов магистратуры. Лектор – Коноводов В.А.

Курс будет проходить дистанционно.

Zoom: link.

Первое занятие - 17.02 в 8:45. Предварительно спецкурс будет проводиться по четвергам, в 8:45.

Курс посвящен современным математическим моделям сложных сетей, состоящих из множества взаимодействующих объектов. У курса две цели. Первая – продемонстрировать, какими свойствами обладают графы, возникающие на практике в различных прикладных областях, а также показать, каким образом проводить анализ больших сетей. Это могут быть социальные, биологические, транспортные, коммуникационные сети, или весь Интернет. Вторая цель – рассмотреть существующие модели случайных графов и их свойства, и показать, какие из них наиболее близки к реальным сетям.

Для освоения курса достаточно иметь начальные знания по теории вероятностей и теории графов. Предполагается, что слушатель знаком с базовыми алгоритмами обработки данных и основами комбинаторики.

По курсу предполагается 2 домашних задания, включающие, в частности, работу с реальными графами и изучение практических аспектов теории сложных сетей.

Итоговая оценка по курсу формируется из баллов, полученных за домашние задания и баллов за экзамен.

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

  • Лекция 1. Виды сложных сетей и примеры реальных графов. Разреженность, малый диаметр, гигантская компонента. Закон распределения степеней вершин. презентация, запись
  • Лекция 2. Устойчивость и уязвимость гигантской компоненты. Кластерные коэффициенты и ассортативность. Библиотеки для работы с графами. презентация, запись
  • Лекция 3. Пример работы с networkx. Платформа Gephi. Силовые алгоритмы визуализации графов. презентация, запись, код, граф из примера.
  • Лекция 4. Модель Эрдёша-Реньи. Простейшие свойства графов в модели. Число треугольников и связность. презентация, запись, доска с доказательствами

Предварительная программа курса

  • Типичные свойства сложных сетей. Примеры больших графов из практики. Количество ребер, гигантская компонента, диаметр. Распределение степеней вершин. Различные меры центральности и PageRank. Вторые степени вершин, кластерные коэффициенты. Количество ребер между вершинами заданных степеней. Число копий фиксированного графа. Ассортативность.
  • Подсчет характеристик графов программными средствами. Библиотека networkx для работы с графами в Python. Средства и алгоритмы визуализации графа. Силовые алгоритмы. Преодоление вычислительных сложностей. Платформа Gephi. Алгоритмы для вычисления PageRank и его модификаций. Метод PowerIteration и неприводимые матрицы. Алгоритм HITS.
  • Модель Эрдеша-Реньи. Определение случайного графа. Распределение степеней вершин в модели. Теорема о гигантской компоненте. Диаметр в случайных графах. Число малых подграфов.
  • Модель Боллобаша-Риордана. Идея предпочтительного присоединения. Модель Боллобаша-Риордана. Статическое и динамическое определение модели. Степенной закон распределения. Диаметр, устойчивость и уязвимость. Генерация случайных графов в модели. Вторые степени вершин.
  • Модель Бакли-Остгуса. Определение модели и генерация графов в ней. Теоремы о характеристиках графов в модели Бакли-Остгуса. Проверка соответствия модели и хост-графа Интернета.
  • Другие модели случайных графов. Модель Чаейс—Боргса. Модели на основе копирования. Модель Купера-Фриза. Модели, учитывающие возраст. Динамические модели.
  • Поиск сообществ. Базовые определения сообществ. Кластеризация данных. Методы оценивания алгоритмов. Алгоритм Кернигана-Лина. Модулярность. Иерархическая кластеризация. Алгоритм Гирвана-Ньюмана.

Литература

Основная

  • Райгородский А. М. Модели интернета. – ИД Интеллект, 2019, – 64 с.
  • Менцер Ф., Фортунато С., Дэвис К. А. Наука о сетях. Вводный курс. – ДМК-Пресс, 2021, – 338 с.
  • Райгородский А. М. Модели случайных графов. – М. МЦНМО, 2011, – 136 с.
  • Remco van der Hofstad. Random Graphs and Complex Networks. Vol 1,2 – 2016.
  • A.Noack. Modularity clustering is force-directed layout. - ссылка

Дополнительная

  • Blum A. Random Graphs – CS 598 Topics in Algorithms (UIUC), 2015.
  • Dorogovtsev S. Lectures on Complex Networks. – Oxford University Press, 2010.
  • Алон Н. и Спенсер Дж. Вероятностный метод. – М.: БИНОМ. Лаборатория знаний, 2007.
  • Харари Ф. Теория графов. – М.: Мир, 1973.
  • L.Ostroumova, E.Samosvat. Global clustering coefficient in scale-free networks – ссылка
  • L.Ostroumova. Global clustering coefficient in scale-free weighted and unweighted networks – ссылка
  • M. Jacomy, M. Bastian. ForceAtlas2, A Graph Layout Algorithm for Handy Network Visualization. - ссылка

Полезные ссылки

Источник — «https://mk.cs.msu.ru/index.php?title=Большие_графы_и_модели_сложных_сетей&oldid=8954»