Введение в теорию графов и сетевой анализ

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

Лучший по критерию «Новизна полученных знаний»

Статус: Курс по выбору (Коммуникации, основанные на данных)

Направление: 42.04.01. Реклама и связи с общественностью

Кто читает: Школа коммуникаций

Где читается: Факультет креативных индустрий

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

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

Преподаватели: Смирнов Максим Сергеевич

Прогр. обучения: Коммуникации, основанные на данных

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

Кредиты: 5

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

Полная версия программы учебной дисциплины

Аннотация

Курс направлен на ознакомление студентов с основами теории графов и сетевого анализа. В рамках курса студенты получат практические навыки работы с библиотекой Python NetworkX для анализа и визуализации социальных графов. Полученные компетенции могут использоваться специалистами по рекламе и связям с общественностью для мониторинга информационного поля и планирования коммуникационных кампаний. Курс изучается в формате blended с использованием онлайн-курсов.

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

Цель курса - обучение студентов основам теории графов и базовым навыкам сетевого анализа социальных медиа с использованием библиотеки Python NetworkX.

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

Знает основные понятия теории графов.
Знает вида и свойства циклов. Умеет решать задачи поиска цикла.
Различает классы графов. Умеет решать задачи на нахождение граней графов.
Корректно применяет алгоритмы раскраски графов.
Знает базовые теоретические понятия сетевого анализа, умеет загружать графы в библиотеку NetworkX на Python.
Применяет метрики связи для анализа социальных графов, визуализирует графы в NetworkX.
Анализирует метрики центральности в социальных графах.
Строит модели, предсказывающие социальные связи.

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

Основные свойства графов.
Примеры графов. Практическое использование. Задача о семи кёнигсбергских мостах. Валентность вершины. Граф-путь. Связность графов. Ориентированные графы. Взвешенные графы. Двудольные графы.
Циклы.
Компоненты связности. Направленные ациклические графы. Сильно связные компоненты. Эйлеров цикл. Гамильтонов цикл.
Классы графов.
Деревья. Двудольные графы. Планарные графы. Формула Эйлера и её применение.
Параметры графов.
Раскраска графов. Клики графов. Теорема Монтеля. Числа Рамсея.
Основы сетевого анализа и работы с библиотекой NetworkX.
Базовые понятия теории социальных сетей. Основы сетевого анализа. Загрузка графов в библиотеку NetworkX.
Метрики исследования связи в сетевом анализе.
Коэффициент кластеризации. Метрики расстояния. Связанная компонента. Визуализация социальной сети в NetworkX.
Метрики степени влияния узла и анализ централизации.
Метрики центральности. Hubs и Authorities.
Модели эволюции сети.
Модель предпочтительного присоединения. Модели малого мира.Предсказание связей.

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

Письменное домашнее задание: задачи по теории графов
Групповой проект по сетевому анализу

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

Промежуточная аттестация (3 модуль)
0.5 * Групповой проект по сетевому анализу + 0.5 * Письменное домашнее задание: задачи по теории графов

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