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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Первое д/з по спецкурсу)
Строка 21: Строка 21:
  
 
== Домашние задания ==
 
== Домашние задания ==
* '''ДЗ 1.''' Появится здесь 12-13 марта.  
+
=== Первое домашнее задание ===
 +
* [https://disk.yandex.ru/i/I4minvVrXsT5-g Условие задач].
 +
* [https://disk.yandex.ru/i/J4x7WfdAYsmgPQ Данные к задаче 7].
 +
* [https://yadi.sk/i/UAatpzCFuzuZc Пример результата в задаче 9].
 +
* Срок сдачи – 2 апреля 23:59.
 +
 
 +
Решение нужно присылать на почту лектора, указанную в презентации, одним письмом. Решения задач 1-6 принимаются в виде одного pdf-файла (скан/фото решения, можно набрать в TeX'e). Решения задач 7-9 принимаются в любом виде (предпочтительнее ссылка на github, и т.п.), в решении обязательно должен быть приложен код программы, который позволит воспроизвести результат, а также сам результат (графики, визуализация и др.). Язык программирования и средства визуализации никак не ограничиваются.
  
 
== Содержание курса ==
 
== Содержание курса ==

Версия 23:17, 11 марта 2022

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


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

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

Zoom: link.

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

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

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

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

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

Домашние задания

Первое домашнее задание

Решение нужно присылать на почту лектора, указанную в презентации, одним письмом. Решения задач 1-6 принимаются в виде одного pdf-файла (скан/фото решения, можно набрать в TeX'e). Решения задач 7-9 принимаются в любом виде (предпочтительнее ссылка на github, и т.п.), в решении обязательно должен быть приложен код программы, который позволит воспроизвести результат, а также сам результат (графики, визуализация и др.). Язык программирования и средства визуализации никак не ограничиваются.

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

  • Лекция 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. - ссылка

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