Магистратура 2018/2019

Моделирование сетей и анализ больших данных

Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»

Статус: Курс обязательный (Математические методы моделирования и компьютерные технологии)

Направление: 01.04.02. Прикладная математика и информатика

Кто читает: Департамент прикладной математики

Где читается: Московский институт электроники и математики им. А.Н. Тихонова

Когда читается: 1-й курс, 3, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Вальба Ольга Владимировна

Прогр. обучения: Математические методы моделирования и компьютерные технологии

Язык: русский

Кредиты: 6

Контактные часы: 88

Программа дисциплины

Аннотация

Целью освоения дисциплины являетсязнакомство с основными понятиями и методами анализа сетей; практические навыки анализа и моделирования сетей. Изучение данной дисциплины базируется на следующих дисциплинах: -Математический анализ; -Линейная алгебра и геометрия; -Теория вероятностей и математическая статистика; -Дискретная математика. Основные положения дисциплины могут быть использованы в дальнейшем при подготовке выпускной квалификационной работы.

Цель освоения дисциплины

• знакомство с основными понятиями и методами анализа сетей
• практические навыки анализа и моделирования сетей

Планируемые результаты обучения

• знать: основные понятия теории сложных сетей, -принципы построения моделей случайных сетей
• уметь: интерпретировать свойства реальных сетей и выбирать подходящую модель для их описания
• владеть: навыками применения методов дисциплины при исследовании конкретных систем

Содержание учебной дисциплины

• Основные понятия, определения и методы анализа сложных сетей.
  Введение в теорию сложных сетей. Определения и примеры сложных сетей. Основные понятия в теории сетей. Свойства и метрики анализа сетей. Топологические свойства сетей. Распределение степеней связности, коэффициент кластеризации, ассортативность, диаметр, кратчайшие пути. Представление сети в компьютерном эксперименте. Понятие к-ядра графа, диады и триады в графах, мотивы
• Случайные сети и компьютерное моделирование сложных систем
  Модель Эрдеша-Реньи (Erdos-Renyi). Распределение Бернулли и Пуассона. Функция распределения степеней. Фазовые переходы, возникновение связанной компоненты. Диаметр и коэффициент кластеризации. Конфигурационная модель. Модель Барабаши-Альберта (Barabasi-Albert). Предпочтительное присоединение. Уравнение в непрерывном приближении. Временная эволюция степеней узлов. Распределение степеней узлов. Средняя длина пути и коэффициент кластеризации. Модели "малого мира". Модель Watts-Strogats. Однопараметрическая модель. Переход от регулярного графа к случайному. Изменения коэффициента кластеризации и средней длины пути. Модели экспоненциальных случайных графов и их физический смысл. Методы Монте-Карло моделирования экспоненциальных-случайных графов. Фазовые переходы и нарушение симметрии.
• Спектральные свойства сетей.
  Матрица смежности. Матрица Лапласа. Процесс физической диффузии. Уравнение диффузии. Диффузия на сетях. Дискретный оператор Лапласа и матрица Лапласа, решение уравнения диффузии на графе. Случайные блуждания на графе. Спектр сети. Максимальное собственное значение матрицы смежности. Алгебраическая связность. Полукруговой закон.
• Поиск сообществ в сети.
  Понятие сообщества в сети. Плотность связей. Метрики. Разделение графа на части. Разрезы в графе. Минимальный разрез, нормированные разрез. Задача нахождения минимально разреза в графе. Агломеративные и разделяющие алгоритмы. Корреляционная матрица. Кластеризация. Понятие промежуточности ребер. Алгортмы Гирвина-Ньюмана. Спектральные методы. Оптимизация модулярности. Классификация алгоритмов нахождения сообществ.
• Модели распространения эпидемий в сетях.
  Модели SI, SIR, SIS. Решения дифференциальных уравнений. Предельные случаи.
• Большие данные и анализ сложных сетей.
  Большие данные социальных сетей. Алгоритмы ранжирования. Векторное представление вершин в сети для задач машинного обучения. Задача кластеризации, классификации и предсказания связей в сложных сетях. Применение методов машинного обучения.

Элементы контроля

• Работа студентов на семинарских занятиях
• Контрольная работа
• Экзамен

Промежуточная аттестация

• Промежуточная аттестация (4 модуль)
  0.15 * Контрольная работа + 0.35 * Работа студентов на семинарских занятиях + 0.5 * Экзамен

Список литературы

Рекомендуемая основная литература

• Newman, M. (2010). Networks: An Introduction. Oxford University Press, 2010
• Newman, M., Watts, D. J., and Barabási, A. The Structure and Dynamics of Networks. – Princeton University Press, 2006. – 592 pp.

Рекомендуемая дополнительная литература

• Diestel R. Graph Theory. – Springer, 2017. – 428 pp.