• A
  • A
  • A
  • АБВ
  • АБВ
  • АБВ
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

Модели сетевых структур

2019/2020
Учебный год
RUS
Обучение ведется на русском языке
5
Кредиты

Преподаватель

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

Аннотация

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

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

  • Целями освоения дисциплины «модели сетевых структур» являются ознакомление студентов с основными методами анализа сетевых структур и их применением
Результаты освоения дисциплины

Результаты освоения дисциплины

  • Владеть основными понятиями сетевых структур
  • Понимать феномен фазового перехода при росте размерности
  • Использовать алгоритмы генерации случайных графов
  • Реализовывать алгоритмы кластеризации на сетях
  • Вычислять сравнительные характеристики мер центральности
  • Реализовывать алгоритмы информационного поиска
Содержание учебной дисциплины

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

  • Тема 1. Графы и сети
    Способы задания графа. Список смежности. Матрица инцендентности. Основные характеристики графов. Диметр графа. Плотность графа. Коэффициент кластеризации. Распре-деление степеней вершин. Клики. Компоненты связанности. Мосты. Кратчайшие пути
  • Тема 2. Случайные графы. Модель Эрдеша-Реньи
    Модель Эреша-Реньи. Основные характеристики модели. Явление фазового перехода. Доказательство фазового перехода в задаче о связности
  • Тема 3. Случайные Графы. Модели Ватса-Строгатца и Барабаши-Альберт
    Случайные графы. Тесные миры. Модель Ватса-Строгальда. Степенное распределение вершин. Модель Барабаши-Альберт
  • Тема 4. Поиск сообществ в сетях
    Алгоритм минимального разреза. Спектральные методы. Алгоритм минимального остовного дерева. Алгоритм Жирвана-Ньюмана. Лувен алгоритм
  • Тема 5. Меры центральности в сети
    Меры центральности узлов в сети. Closeness and betweennes centrality. Спектральная центральность. Модель случайного блуждания по сети. Google’s Page Rank. HITS алгоритм
  • Тема 6. Применение сетевых структур для информационного поиска
    Одноранговые (p2p) сети. Распределенные хэш таблицы. Chord Protocol. Тесный мир Клайнберга. Доказательство сложности работы алгоритма поиска в моделе Клайнберга
Элементы контроля

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

  • неблокирующий Домашнее задание №1
  • неблокирующий Домашнее задание №2
  • неблокирующий Доклад
  • неблокирующий Экзамен
Промежуточная аттестация

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

  • Промежуточная аттестация (2 модуль)
    0.2 * Доклад + 0.15 * Домашнее задание №1 + 0.15 * Домашнее задание №2 + 0.5 * Экзамен
Список литературы

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

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

  • Kolaczyk E. D., Csárdi G. Statistical analysis of network data with R. – New York : Springer, 2014. – 207 pp.

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

  • Графы и алгоритмы. Структуры данных. Модели вычислений, учебник, 319 с., Алексеев, В. Е., Таланов, В. А., 2012