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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(Содержание курса)
Строка 19: Строка 19:
  
 
Итоговая оценка по курсу формируется из баллов, полученных за домашние задания и баллов за экзамен.
 
Итоговая оценка по курсу формируется из баллов, полученных за домашние задания и баллов за экзамен.
 +
 +
[[Media: Large_graphs_and_model_nets.pdf|Объявление о спецкурсе (pdf)]] (февраль)
  
 
== Домашние задания ==
 
== Домашние задания ==
Строка 35: Строка 37:
 
* '''Лекция 4.''' Модель Эрдёша-Реньи. Простейшие свойства графов в модели. Число треугольников и связность. [https://disk.yandex.ru/i/xYhUNyfa4TT8yA презентация], [https://disk.yandex.ru/i/v9aJmFPqUWk6bg запись], [https://disk.yandex.ru/i/JoE6dOwm_-dapg доска с доказательствами].
 
* '''Лекция 4.''' Модель Эрдёша-Реньи. Простейшие свойства графов в модели. Число треугольников и связность. [https://disk.yandex.ru/i/xYhUNyfa4TT8yA презентация], [https://disk.yandex.ru/i/v9aJmFPqUWk6bg запись], [https://disk.yandex.ru/i/JoE6dOwm_-dapg доска с доказательствами].
 
* '''Лекция 5.''' Доказательство теорем о связности случайного графа Эрдёша-Реньи. Предпочтительное присоединение и модель Боллобаша-Риордана, статическое и динамическое определение. [https://disk.yandex.ru/i/hvjp7pJtkTkYFw презентация], [https://disk.yandex.ru/i/cMo90sVMlOGyjw запись], [https://disk.yandex.ru/i/LlrzH5Ak4wfN6A доска с доказательствами].
 
* '''Лекция 5.''' Доказательство теорем о связности случайного графа Эрдёша-Реньи. Предпочтительное присоединение и модель Боллобаша-Риордана, статическое и динамическое определение. [https://disk.yandex.ru/i/hvjp7pJtkTkYFw презентация], [https://disk.yandex.ru/i/cMo90sVMlOGyjw запись], [https://disk.yandex.ru/i/LlrzH5Ak4wfN6A доска с доказательствами].
 
== Предварительная программа курса  ==
 
* '''Типичные свойства сложных сетей.''' Примеры больших графов из практики. Количество ребер, гигантская компонента, диаметр. Распределение степеней вершин. Различные меры центральности и PageRank. Вторые степени вершин, кластерные коэффициенты. Количество ребер между вершинами заданных степеней. Число копий фиксированного графа. Ассортативность.
 
 
* '''Подсчет характеристик графов программными средствами.''' Библиотека networkx для работы с графами в Python. Средства и алгоритмы визуализации графа. Силовые алгоритмы. Преодоление вычислительных сложностей. Платформа Gephi. Алгоритмы для вычисления PageRank и его модификаций. Метод PowerIteration и неприводимые матрицы. Алгоритм HITS.
 
 
* '''Модель Эрдеша-Реньи.''' Определение случайного графа. Распределение степеней вершин в модели. Теорема о гигантской компоненте. Диаметр в случайных графах. Число малых подграфов.
 
 
* '''Модель Боллобаша-Риордана.''' Идея предпочтительного присоединения. Модель Боллобаша-Риордана. Статическое и динамическое определение модели. Степенной закон распределения. Диаметр, устойчивость и уязвимость. Генерация случайных графов в модели. Вторые степени вершин.
 
 
* '''Модель Бакли-Остгуса.''' Определение модели и генерация графов в ней. Теоремы о характеристиках графов в модели Бакли-Остгуса. Проверка соответствия модели и хост-графа Интернета.
 
 
* '''Другие модели случайных графов.''' Модель Чаейс—Боргса. Модели на основе копирования. Модель Купера-Фриза. Модели, учитывающие возраст. Динамические модели.
 
 
* '''Поиск сообществ.''' Базовые определения сообществ. Кластеризация данных. Методы оценивания алгоритмов. Алгоритм Кернигана-Лина. Модулярность. Иерархическая кластеризация. Алгоритм Гирвана-Ньюмана.
 
  
 
== Литература ==
 
== Литература ==

Версия 20:25, 19 марта 2022

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


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

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

Zoom: link.

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

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

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

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

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

Объявление о спецкурсе (pdf) (февраль)

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

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

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

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

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

Литература

Основная

  • Райгородский А. М. Модели интернета. – ИД Интеллект, 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. - ссылка

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