Большие графы и модели сложных сетей

Материал из Кафедра математической кибернетики
Перейти к: навигация, поиск

Важная информация про экзаменационный тест 28.04:

  • Тест будет открыт с 9:00 до 9:50, после 9:50 завершить тест будет невозможно. Время на выполнение теста – 40 минут.
  • При прохождении теста система показывает таймер с оставшимся временем, при переключениии между вкладками браузера/окнами и т.п. возможно некорректное отображение оставшегося времени.
  • В тесте 10 заданий, все задания имеют разную стоимость (от 2 до 10 баллов), в задании баллы не указаны.
  • За неправильные ответы отрицательные баллы не ставятся.
  • Нельзя пропускать вопросы и возвращаться к ним позднее.
  • Подробнее о том, как записаться на тест, написано ниже в разделе Экзамен.
  • Результаты теста появятся в общей таблице результатов до 11:00.

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

Занятия в весеннем семестре 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 баллов
  • Для получения зачёта по курсу достаточно набрать баллов на оценку "удовлетворительно".

В случае набора баллов за домашние задания на оценку, с которой слушатель согласен, экзамен можно не сдавать. Если эта оценка "хорошо" или "удовлетворительно", необходимо сообщить о своем согласии лектору на почту.

Первый экзамен (для шестого курса и желающих) состоится 28.04 в 9:00. Варианты других дат проведения экзамена для первого курса магистратуры и иных слушателей будут объявлены позднее.

Для сдачи экзамена необходимо подать заявку на курс https://lomonosov-msu.ru/rus/event/7408/, зарегистрировавшись на сайте при отсутствии учетной записи.

Для записи на экзамен 28 апреля необходимо заполнить форму по ссылке https://lomonosov-msu.ru/rus/event/request/dashboard/7408 (отправить форму, перейдя в "Запись на экзамен 28 апреля" по ссылке "Заполнить" и нажав "отправить"). Форму можно заполнить в любое время до начала экзамена. Отменить запись невозможно.

Экзамен будет проходить в форме электронного теста, ссылка на тест будет доступна в разделе "Мои заявки". Экзаменационный тест состоит из 10-15 вопросов, время на выполнение – 40 минут. Ответ на каждый вопрос – либо выбор одного из вариантов, либо в виде числа, либо в виде текста. Код писать не нужно, работать со специальными данными не нужно. Тест будет открыт для зарегистрированных (по форме выше) участников с 09:00 до 09:40. В 09:50 все результаты будут собраны. Результаты будут размещены в общей таблице в течение часа после окончания теста.

Для всех зарегистрированных участников на странице доступен пробный тест по курсу. Вопросы теста по своей форме похожи на вопросы экзамена.

Содержание лекции 10 не будет включено в экзамен.

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

  • Лекция 1. Виды сложных сетей и примеры реальных графов. Разреженность, малый диаметр, гигантская компонента. Закон распределения степеней вершин. презентация, запись
  • Лекция 2. Устойчивость и уязвимость гигантской компоненты. Кластерные коэффициенты и ассортативность. Библиотеки для работы с графами. презентация, запись
  • Лекция 3. Пример работы с networkx. Платформа Gephi. Силовые алгоритмы визуализации графов. презентация, запись, код, граф из примера.
  • Лекция 4. Модель Эрдёша-Реньи. Простейшие свойства графов в модели. Число треугольников и связность. презентация, запись, доска с доказательствами.
  • Лекция 5. Доказательство теорем о связности случайного графа Эрдёша-Реньи. Предпочтительное присоединение и модель Боллобаша-Риордана, статическое и динамическое определение. презентация, запись, доска с доказательствами.
  • Лекция 6. Диаметр, устойчивость и уязвимость гигантской компоненты в графах Боллобаша-Риордана. Степенной закон распределения степеней вершин и его доказательство в простейшем случае. презентация, запись, доска с доказательствами.
  • Лекция 7. Модель Бакли-Остгуса. Соответствие модели хост-графу интернета. Число рёбер между вершинами заданных степеней. Число копий заданного графа и кластерные коэффициенты в графах Боллобаша-Риордана и Бакли-Остгуса. презентация, запись.
  • Лекция 8. Различные модели на основе предпочтительного присоединения и PA-класс. Модель копирования. Модель Купера-Фриза. презентация, код, запись, ч1, запись, ч2
  • Лекция 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=9165»