• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Master 2019/2020

Structural Analysis and Visualization of Networks

Area of studies: Applied Mathematics and Informatics
When: 1 year, 3, 4 module
Mode of studies: Full time
Instructors: Ilya Makarov
Master’s programme: Финансовые технологии и анализ данных
Language: English
ECTS credits: 5

Course Syllabus

Abstract

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

Learning Objectives

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

Expected Learning Outcomes

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

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

Assessment Elements

  • non-blocking Исследовательский проект
  • non-blocking Проект
  • non-blocking Контрольная работа
  • non-blocking Экзамен
    "Экзамен проводится в письменной форме (тест) с использованием синхронного прокторинга. Экзамен проводится на платформе 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

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

Bibliography

Recommended Core Bibliography

  • - Мастицкий С.Э., Шитиков В.К. — Статистический анализ и визуализация данных с помощью R - Издательство "ДМК Пресс" - 2015 - ISBN: 978-5-97060-301-7 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/73072
  • 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

Recommended Additional Bibliography

  • - Роберт И., Кабаков — R в действии. Анализ и визуализация данных в программе R - Издательство "ДМК Пресс" - 2014 - ISBN: 978-5-97060-077-1 - Текст электронный // ЭБС Лань - URL: https://e.lanbook.com/book/58703
  • 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
  • Структурный анализ самоорганизующихся систем: Монография / Алдонин Г.М. - Краснояр.:СФУ, 2017. - 344 с.: ISBN 978-5-7638-3471-0