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

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск
(→‎Содержание курса)
 
(не показаны 44 промежуточных версий 1 участника)
Строка 1: Строка 1:
 +
[[Категория:Спецкурсы кафедры МК (архив)]]
 +
 
{{DISPLAYTITLE:Большие графы и модели сложных сетей}}
 
{{DISPLAYTITLE:Большие графы и модели сложных сетей}}
−
'''Записаться на спецкурс''': [https://forms.yandex.ru/u/6208e2646df381393fb1d4a0/ здесь].
 
−
 
−
----
 
−
 
 
Спецкурс для студентов магистратуры. Лектор – [[Участник:KonovodovV|Коноводов В.А.]]
 
Спецкурс для студентов магистратуры. Лектор – [[Участник:KonovodovV|Коноводов В.А.]]
  
−
Курс будет проходить дистанционно.
+
Занятия в весеннем семестре 2022г. завершены.
−
 
+
−
'''Zoom:''' [https://clck.ru/bce5L link].
+
−
 
+
−
Первое занятие - '''17.02''' в '''8:45'''. Предварительно спецкурс будет проводиться по четвергам, в 8:45.
+
  
 
Курс посвящен современным математическим моделям сложных сетей, состоящих из множества взаимодействующих объектов. У курса две цели. Первая – продемонстрировать, какими свойствами обладают графы, возникающие на практике в различных прикладных областях, а также показать, каким образом проводить анализ больших сетей. Это могут быть социальные, биологические, транспортные, коммуникационные сети, или весь Интернет. Вторая цель – рассмотреть существующие модели случайных графов и их свойства, и показать, какие из них наиболее близки к реальным сетям.
 
Курс посвящен современным математическим моделям сложных сетей, состоящих из множества взаимодействующих объектов. У курса две цели. Первая – продемонстрировать, какими свойствами обладают графы, возникающие на практике в различных прикладных областях, а также показать, каким образом проводить анализ больших сетей. Это могут быть социальные, биологические, транспортные, коммуникационные сети, или весь Интернет. Вторая цель – рассмотреть существующие модели случайных графов и их свойства, и показать, какие из них наиболее близки к реальным сетям.
Строка 18: Строка 12:
 
По курсу предполагается 2 домашних задания, включающие, в частности, работу с реальными графами и изучение практических аспектов теории сложных сетей.  
 
По курсу предполагается 2 домашних задания, включающие, в частности, работу с реальными графами и изучение практических аспектов теории сложных сетей.  
  
−
Итоговая оценка по курсу формируется из баллов, полученных за домашние задания и баллов за экзамен.
+
[[Media: Large_graphs_and_model_nets.pdf|Объявление о спецкурсе (pdf)]] (февраль)
  
−
== Содержание курса ==
+
Запись первой лекции можно найти [https://disk.yandex.ru/i/QQhKrMxo8j2KVg здесь].
−
* '''Лекция 1.'''  Виды сложных сетей и примеры реальных графов. Разреженность, малый диаметр, гигантская компонента. Закон распределения степеней вершин. [https://disk.yandex.ru/i/cML3_hc7TiuYFA презентация], [https://disk.yandex.ru/i/wW2j76r_pwNUDg запись]
+
−
* '''Лекция 2.''' Устойчивость и уязвимость гигантской компоненты. Кластерные коэффициенты и ассортативность. Библиотеки для работы с графами. [https://disk.yandex.ru/i/pEf1A9aIK_ZokA запись]
+
  
−
== Предварительная программа курса  ==
+
== Домашние задания ==
−
* '''Типичные свойства сложных сетей.''' Примеры больших графов из практики. Количество ребер, гигантская компонента, диаметр. Распределение степеней вершин. Различные меры центральности и PageRank. Вторые степени вершин, кластерные коэффициенты. Количество ребер между вершинами заданных степеней. Число копий фиксированного графа. Ассортативность.
+
=== Первое домашнее задание ===
 +
* [https://disk.yandex.ru/i/I4minvVrXsT5-g Условие задач].
 +
* [https://disk.yandex.ru/i/J4x7WfdAYsmgPQ Данные к задаче 7].
 +
* [https://yadi.sk/i/UAatpzCFuzuZc Пример результата в задаче 9].
 +
* Срок сдачи – 2 апреля 23:59.
  
−
* '''Подсчет характеристик графов программными средствами.''' Библиотека networkx для работы с графами в Python. Средства и алгоритмы визуализации графа. Силовые алгоритмы. Преодоление вычислительных сложностей. Платформа Gephi. Алгоритмы для вычисления PageRank и его модификаций. Метод PowerIteration и неприводимые матрицы. Алгоритм HITS.
+
Решение нужно присылать на почту лектора, указанную в презентации, одним письмом. Решения задач 1-6 принимаются в виде одного pdf-файла (скан/фото решения, можно набрать в TeX'e). Решения задач 7-9 принимаются в любом виде (предпочтительнее ссылка на github, и т.п.), в решении обязательно должен быть приложен код программы, который позволит воспроизвести результат, а также сам результат (графики, визуализация и др.). Язык программирования и средства визуализации никак не ограничиваются.
  
−
* '''Модель Эрдеша-Реньи.''' Определение случайного графа. Распределение степеней вершин в модели. Теорема о гигантской компоненте. Диаметр в случайных графах. Число малых подграфов.
+
=== Второе домашнее задание ===
 +
* [https://disk.yandex.ru/i/jiYh-J1oSr-K5A Условие задач].
 +
* [https://disk.yandex.ru/d/HBscsvuYEWkmhg Данные к задаче 8].
 +
* Срок сдачи – 22 апреля 23:59.
 +
* '''Внимание!''' 11.04 исправлены ошибочные индексы в условии задачи 2.
  
−
* '''Модель Боллобаша-Риордана.''' Идея предпочтительного присоединения. Модель Боллобаша-Риордана. Статическое и динамическое определение модели. Степенной закон распределения. Диаметр, устойчивость и уязвимость. Генерация случайных графов в модели. Вторые степени вершин.
+
Решение нужно присылать на почту лектора, указанную в презентации, одним письмом. Решения задач 1-6 и теоретическая часть задачи 9 принимаются в виде одного pdf-файла (скан/фото решения, можно набрать в TeX'e). Решения задач 7,8 и практическая часть задачи 9 принимаются в любом виде (предпочтительнее ссылка на github, и т.п.), в решении обязательно должен быть приложен код программы, который позволит воспроизвести результат, а также сам результат (графики, визуализация и др.). Язык программирования и средства визуализации никак не ограничиваются.
  
−
* '''Модель Бакли-Остгуса.''' Определение модели и генерация графов в ней. Теоремы о характеристиках графов в модели Бакли-Остгуса. Проверка соответствия модели и хост-графа Интернета.  
+
== Экзамен ==
 +
Итоговая оценка по курсу формируется из баллов, полученных за домашние задания и баллов за экзамен. Максимальное число баллов за экзамен – 50.
  
−
* '''Другие модели случайных графов.''' Модель Чаейс—Боргса. Модели на основе копирования. Модель Купера-Фриза. Модели, учитывающие возраст. Динамические модели.  
+
Критерии оценок:
 +
* Оценка '''отлично''': не менее 40 баллов
 +
* Оценка '''хорошо''': не менее 29 и не более 39 баллов
 +
* Оценка '''удовлетворительно''': не менее 18 и не более 28 баллов
 +
* Для получения '''зачёта''' по курсу достаточно набрать баллов на оценку "удовлетворительно".
  
−
* '''Поиск сообществ.''' Базовые определения сообществ. Кластеризация данных. Методы оценивания алгоритмов. Алгоритм Кернигана-Лина. Модулярность. Иерархическая кластеризация. Алгоритм Гирвана-Ньюмана.
+
== Содержание курса ==
 +
* '''Лекция 1.''' Виды сложных сетей и примеры реальных графов. Разреженность, малый диаметр, гигантская компонента. Закон распределения степеней вершин.
 +
* '''Лекция 2.''' Устойчивость и уязвимость гигантской компоненты. Кластерные коэффициенты и ассортативность. Библиотеки для работы с графами.
 +
* '''Лекция 3.''' Пример работы с networkx. Платформа Gephi. Силовые алгоритмы визуализации графов.
 +
* '''Лекция 4.''' Модель Эрдёша-Реньи. Простейшие свойства графов в модели. Число треугольников и связность.
 +
* '''Лекция 5.''' Доказательство теорем о связности случайного графа Эрдёша-Реньи. Предпочтительное присоединение и модель Боллобаша-Риордана, статическое и динамическое определение.
 +
* '''Лекция 6.''' Диаметр, устойчивость и уязвимость гигантской компоненты в графах Боллобаша-Риордана. Степенной закон распределения степеней вершин и его доказательство в простейшем случае.
 +
* '''Лекция 7.''' Модель Бакли-Остгуса. Соответствие модели хост-графу интернета. Число рёбер между вершинами заданных степеней. Число копий заданного графа и кластерные коэффициенты в графах Боллобаша-Риордана и Бакли-Остгуса.
 +
* '''Лекция 8.''' Различные модели на основе предпочтительного присоединения и PA-класс. Модель копирования. Модель Купера-Фриза.
 +
* '''Лекция 9.''' Линковый факторы на графах. PageRank и HITS. Алгоритм PowerIteration и его сходимость.
 +
* '''Лекция 10.''' Виды центральностей. Поиск сообществ в графах. Модулярность. Алгоритмы кластеризации.
  
 
== Литература ==
 
== Литература ==
Строка 45: Строка 60:
 
* Райгородский А. М. Модели случайных графов. – М. МЦНМО, 2011, – 136 с.
 
* Райгородский А. М. Модели случайных графов. – М. МЦНМО, 2011, – 136 с.
 
* Remco van der Hofstad. Random Graphs and Complex Networks. Vol 1,2 – 2016.
 
* Remco van der Hofstad. Random Graphs and Complex Networks. Vol 1,2 – 2016.
 +
* A.Noack. Modularity clustering is force-directed layout. - [https://arxiv.org/abs/0807.4052 ссылка]
 +
* A. Langville, C. D. Meyer. A Survey of Eigenvector Methods for Web Information Retrieval. – [https://www.semanticscholar.org/paper/A-Survey-of-Eigenvector-Methods-for-Web-Information-Langville-Meyer/99e31ca1a3f72f9f4f8bb5928d38444b0c00aac1 ссылка]
  
 
===Дополнительная===
 
===Дополнительная===
Строка 51: Строка 68:
 
* Алон Н. и Спенсер Дж. Вероятностный метод. – М.: БИНОМ. Лаборатория знаний, 2007.
 
* Алон Н. и Спенсер Дж. Вероятностный метод. – М.: БИНОМ. Лаборатория знаний, 2007.
 
* Харари Ф. Теория графов. – М.: Мир, 1973.
 
* Харари Ф. Теория графов. – М.: Мир, 1973.
 +
* L.Ostroumova, E.Samosvat. Global clustering coefficient in scale-free networks – [https://arxiv.org/abs/1410.1997 ссылка]
 +
* L.Ostroumova. Global clustering coefficient in scale-free weighted and unweighted networks – [https://arxiv.org/abs/1507.00925 ссылка]
 +
* M. Jacomy, M. Bastian. ForceAtlas2, A Graph Layout Algorithm for Handy Network Visualization. - [https://api.semanticscholar.org/CorpusID:16613603 ссылка]
 +
* B. Bollobás, O. Riordan, J. Spencer, G. Tusnády. The Degree Sequence of a Scale-Free Random Graph Process. – Random Structures Algorithms. 2001. V.18, №3, P.279–290.
 +
* Grechnikov E. A., Gusev G. G., Ostroumova L. A., Pritykin Yu. L., Raigorodskii A. M., Serdyukov P., Vinogradov D. V., Zhukovskiy M. E. Empirical Validation of the Buckley–Osthus Model for the Web Host Graph. 2012. – [https://api.semanticscholar.org/CorpusID:6326984 ссылка]
 +
* Рябченко А. А., Самосват Е. А. О числе подграфов в случайном графе Барабаши–Альберт, Изв. РАН. Сер. матем., 76:3 (2012), 183–202 – [http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=im&paperid=6036&option_lang=rus ссылка]
 +
* Тильга С. Д., О распределении малых подграфов в случайном графе Бакли–Остгуса, Изв. РАН. Сер. матем., 81:2 (2017), 161–214 – [http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=im&paperid=8460&option_lang=rus ссылка]
 +
* S. Dereich, P. Mörters. Random networks with sublinear preferential attachment: degree evolutions. Electron. J. Probab. 14 (2009), no. 43, 1222–1267.
 +
* S. Bhamidi. Universal techniques to analyze preferential attachment trees: Global and Local analysis. 2007.  [https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.5134&rep=rep1&type=pdf ссылка]
 +
* G. Ergün, G. J. Rodgers. Growing random networks with fitness. Physica A-statistical Mechanics and Its Applications, 2002, v.303, p. 261-272. [https://arxiv.org/pdf/cond-mat/0103423.pdf ссылка]
 +
* P. L. Krapivsky, S. Redner. Organization of Growing Random Networks. 2001. – [https://arxiv.org/abs/cond-mat/0011094 ссылка]
 +
* S. Fortunato. Community detection in graphs. 2010. – [https://arxiv.org/abs/0906.0612 ссылка]
  
 
== Полезные ссылки ==
 
== Полезные ссылки ==
 +
* [https://gephi.org Gephi]. Открытая платформа по визуализации графов.
 
* [https://gephi.org/tutorials/gephi-tutorial-quick_start.pdf Туториал по Gephi]
 
* [https://gephi.org/tutorials/gephi-tutorial-quick_start.pdf Туториал по Gephi]
 
* [https://networkx.org/ Библиотека networkx] для Python
 
* [https://networkx.org/ Библиотека networkx] для Python
Строка 58: Строка 88:
 
* [http://konect.cc/statistics/diameff90/ konect.cc/statistics/diameff90] Статистики некоторых графов  
 
* [http://konect.cc/statistics/diameff90/ konect.cc/statistics/diameff90] Статистики некоторых графов  
 
* [https://hoaxy.osome.iu.edu/ hoaxy.osome.iu.edu] Визуализатор распространения информации в Twitter
 
* [https://hoaxy.osome.iu.edu/ hoaxy.osome.iu.edu] Визуализатор распространения информации в Twitter
−
 
−
[[Категория:Спецкурсы кафедры МК]]
 

Текущая версия на 23:05, 7 октября 2024


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

Занятия в весеннем семестре 2022г. завершены.

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

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

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

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

Запись первой лекции можно найти здесь.

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

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

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

Второе домашнее задание

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

Экзамен

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

Критерии оценок:

  • Оценка отлично: не менее 40 баллов
  • Оценка хорошо: не менее 29 и не более 39 баллов
  • Оценка удовлетворительно: не менее 18 и не более 28 баллов
  • Для получения зачёта по курсу достаточно набрать баллов на оценку "удовлетворительно".

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

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

Литература

Основная

  • Райгородский А. М. Модели интернета. – ИД Интеллект, 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. - ссылка
  • A. Langville, C. D. Meyer. A Survey of Eigenvector Methods for Web Information Retrieval. – ссылка

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

  • 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. - ссылка
  • B. Bollobás, O. Riordan, J. Spencer, G. Tusnády. The Degree Sequence of a Scale-Free Random Graph Process. – Random Structures Algorithms. 2001. V.18, №3, P.279–290.
  • Grechnikov E. A., Gusev G. G., Ostroumova L. A., Pritykin Yu. L., Raigorodskii A. M., Serdyukov P., Vinogradov D. V., Zhukovskiy M. E. Empirical Validation of the Buckley–Osthus Model for the Web Host Graph. 2012. – ссылка
  • Рябченко А. А., Самосват Е. А. О числе подграфов в случайном графе Барабаши–Альберт, Изв. РАН. Сер. матем., 76:3 (2012), 183–202 – ссылка
  • Тильга С. Д., О распределении малых подграфов в случайном графе Бакли–Остгуса, Изв. РАН. Сер. матем., 81:2 (2017), 161–214 – ссылка
  • S. Dereich, P. Mörters. Random networks with sublinear preferential attachment: degree evolutions. Electron. J. Probab. 14 (2009), no. 43, 1222–1267.
  • S. Bhamidi. Universal techniques to analyze preferential attachment trees: Global and Local analysis. 2007. ссылка
  • G. Ergün, G. J. Rodgers. Growing random networks with fitness. Physica A-statistical Mechanics and Its Applications, 2002, v.303, p. 261-272. ссылка
  • P. L. Krapivsky, S. Redner. Organization of Growing Random Networks. 2001. – ссылка
  • S. Fortunato. Community detection in graphs. 2010. – ссылка

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

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