Большие графы и модели сложных сетей — различия между версиями

Версия 22:41, 4 февраля 2022

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

Курс будет проходить дистанционно. Первое занятие будет объявлено позднее.

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

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

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

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

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

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

• Типичные свойства сложных сетей. Примеры больших графов из практики. Количество ребер, гигантская компонента, диаметр. Распределение степеней вершин. Различные меры центральности и 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.

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

• Blum A. Random Graphs – CS 598 Topics in Algorithms (UIUC), 2015.
• Dorogovtsev S. Lectures on Complex Networks. – Oxford University Press, 2010.
• Алон Н. и Спенсер Дж. Вероятностный метод. – М.: БИНОМ. Лаборатория знаний, 2007.
• Харари Ф. Теория графов. – М.: Мир, 1973.

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

• Туториал по Gephi
• Библиотека networkx для Python
• Библиотека igraph
• konect.cc/statistics/diameff90 Статистики некоторых графов
• hoaxy.osome.iu.edu Визуализатор распространения информации в Twitter