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

2019/2020

Учебный год

RUS

Обучение ведется на русском языке

5

Кредиты

Кто читает:

Кафедра прикладной математики и информатики (Нижний Новгород) (Факультет информатики, математики и компьютерных наук (Нижний Новгород))

Статус:

Курс обязательный

Когда читается:

4-й курс, 1, 2 модуль

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

Калягин Валерий Александрович

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

Аннотация

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

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

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

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

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

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

• Тема 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