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

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

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

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

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

Zoom: link.

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

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

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

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

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

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

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

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

• Условие задач.
• Данные к задаче 7.
• Пример результата в задаче 9.
• Срок сдачи – 2 апреля 23:59.

Решение нужно присылать на почту лектора, указанную в презентации, одним письмом. Решения задач 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. - ссылка

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

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