Structural Analysis and Visualization of Networks

Master 2020/2021

Category 'Best Course for Broadening Horizons and Diversity of Knowledge and Skills'

Category 'Best Course for New Knowledge and Skills'

Type: Elective course (Financial Technologies and Data Analysis)

Area of studies: Applied Mathematics and Informatics

Delivered by: School of Data Analysis and Artificial Intelligence

Where: Faculty of Computer Science

When: 1 year, 3, 4 module

Mode of studies: offline

Instructors: Ilya Makarov

Master’s programme: Финансовые технологии и анализ данных

Language: English

ECTS credits: 5

Contact hours: 44

Full Syllabus Ask Question

Abstract

Курс «Структурный анализ и визуализация сетей» вводит студентов в новую и активно развивающуюся междисциплинарную область наук о сетевых структурах. Начиная с исследований социальных сетей социологами, данное направление привлекло внимание физиков, ученых в области компьютерных наук, экономистов, вычислительных биологов, лингвистов и других, и стало по-настоящему междисциплинарной областью изучения. Несмотря на разнообразие процессов, которые образуют сети, а также объекты и отношения, которые служат узлами и ребрами в этих сетях, все сети обладают общими статистическими и структурными свойствами. Взаимодействие между порядком и беспорядком создает сложные сетевые структуры, которые находятся в центре внимания исследования. В ходе курса мы рассмотрим методы статистического и структурного анализа сетей, модели формирования и эволюции сети, и развития процессов в сети. Особое внимание будет уделено практическому анализу и визуализации реальных сетей с использованием доступных программных средств, и современных языков и библиотек программирования.

Learning Objectives

Целями обучения на курсе «Структурный анализ и визуализация сетей» являются ознакомление учащихся с новой быстро развивающейся областью сетевых наук и предоставление практического опыта в анализе сетевых данных реального мира.

Expected Learning Outcomes

• знать основные понятия и терминологию, используемые в науке о сетях; • понимать основополагающие принципы сетевой̆ структуры и эволюции; • уметь разрабатывать математические модели сетевых процессов; • быть способными анализировать сетевые данные реального мира.

Course Contents

Введение в науку о сетях
Введение в новую науку о сетях. Теория сложных сетей. Основные свойства и метрики сетей. Примеры сетей.
Степенной закон
Распределение степенного закона. Scale-free сети. Распределение Парето, нормализация, моменты. Закон Зипфа. График частот.
Модели формирования сетей
Модель случайного графа Эрдоса-Рени. Распределения Пуассона и Бернулли. Распределение степеней узлов. Фазовый переход, гигантский связанный компонент. Диаметр и коэффициент кластера. Модель конфигурации. Модель Барабаси-Альберта. Предпочтительное прикрепление. Уравнение в непрерывном приближении. Временная эволюция степеней узлов. Распределение степени узла. Средняя длина пути и коэффициент кластеризации. Модель малого мира. Модель Watts-Strogats. Переход от регулярного к случайному графу, изменения коэффициента кластеризации и средней длины пути.
Анализ структуры сетей, узлов и связей
Метрики центральности узлов, степенная центральность, центральность близости, betweenness центральность, eigenvector центральность. Метрики, основанные на структуре графа. PageRank, стохастическая метрика и теорема Перрона-Фробениуса. Итерации мощности. Центры и авторитеты. Алгоритм HITS. Ранговое расстояние Кендалл-Тау. Метрики структурной эквивалентности. Расстояния Евклида и Хемминга. Коэффициент корреляции. Косинусное сходства. Ассортативное смешивание и гомофилия. Модульность. Смешивание по степеням.
Сообщества в сетях
Сообщества в сетях. Плотность графа. Разделение графа. Показатели Min-cut, quotent и normalized cuts. Дивизионные и агломерационные алгоритмы. Повторяющееся деление пополам. Корреляционная матрица. Кластеризация. Edge Betweenness. Алгоритм Ньюмана- Гирвина. Спектральные методы. Алгоритм максимизации модульности (Newman). Аппроксимационные алгоритмы. Рандомизированный минимальный разрез (алгоритм Каргеса). Вероятность нахождения минимального разреза. Многоуровневая парадигма. Многоуровневый алгоритм для графов со степенным законом. Локальная кластеризация. Проводимость. Алгоритмы Nibble. Graph motiffs, k-cores, перепись диад и триад.
Распространение влияния
Социальная диффузия. Пороговая модель коллективного поведения Грановеттера. Наиболее влиятельные узлы в сети. Каскады в сетях. Базовая каскадная модель. Каскадная модель.
Диффузия и эпидемии в сетях
Физическая диффузия. Уравнение диффузии. Диффузия в сетях. Дискретный оператор Лапласа, матрица Лапласа. Решение уравнения диффузии. Случайные блуждания по графу. Эпидемические модели SI, SIS, SIR. Решение дифференциального уравнения. Ограничивающие случаи. Моделирование распространения инфекции.
Информационные каскады
Наблюдательное обучение. Информационные каскады.
Визуализация сетей
Визуальное исследование. Графические схемы: радиальные, силовые, спектральные. Матричная визуализация.
Развитие сетей и предсказание связей
Рост сети. Уменьшение диаметра. Взаимодействие связей. Задача предсказания связей. Обучение с учителем для предсказания.

Assessment Elements

Исследовательский проект
Проект
Контрольная работа
Экзамен
"Экзамен проводится в письменной форме (тест) с использованием синхронного прокторинга. Экзамен проводится на платформе Moodle (https://moodle.org/?lang=ru), прокторинг на платформе Экзамус (https://hse.student.examus.net). К экзамену необходимо подключиться за 15 минут. На платформе Экзамус доступно тестирование системы. Компьютер студента должен удовлетворять следующим требованиям: https://elearning.hse.ru/data/2020/05/07/1544135594/Технические%20требования%20к%20ПК%20студента.pdf) Для участия в экзамене студент обязан: заранее зайти на платформу прокторинга, провести тест системы, включить камеру и микрофон, подтвердить личность. Во время экзамена студентам запрещено: общаться (в социальных сетях, с людьми в комнате), списывать. Во время экзамена студентам разрешено: пользоваться собственными письменными конспектами (в тетради или на распечатанных листах). Кратковременным нарушением связи во время экзамена считается прерывание связи до 10 минут. Долговременным нарушением связи во время экзамена считается прерывание связи 10 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи. "

Interim Assessment

Interim assessment (4 module)
0.3 * Исследовательский проект + 0.15 * Контрольная работа + 0.15 * Проект + 0.4 * Экзамен

Bibliography

Recommended Core Bibliography

Jackson, M. O. (2008). Social and Economic Networks. Princeton, NJ: Princeton University Press. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=1079018
Мастицкий С.Э., Шитиков В.К. - Статистический анализ и визуализация данных с помощью R - Издательство "ДМК Пресс" - 2015 - 496с. - ISBN: 978-5-97060-301-7 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/73072

Recommended Additional Bibliography

Chwe, M. S.-Y. (2000). Communication and Coordination in Social Networks. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.AE115D69
IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS, SPECIAL ISSUE ON VISUAL ANALYTICS 1 Visual Analysis of Large Heterogeneous Social Networks by Semantic and Structural Abstraction. (n.d.). Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsbas&AN=edsbas.63955D2C
Роберт И., Кабаков - R в действии. Анализ и визуализация данных в программе R - Издательство "ДМК Пресс" - 2014 - 588с. - ISBN: 978-5-97060-077-1 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/58703
Структурный анализ самоорганизующихся систем: Монография / Алдонин Г.М. - Краснояр.:СФУ, 2017. - 344 с.: ISBN 978-5-7638-3471-0

Course Syllabus