Программа лекций и презентации по курсу «Анализ социальных сетей»

ВНИМАНИЕ! Адаптированные презентации предназначены для учащихся МИИГАиК.

• Лекция 1. Основные понятия и характеристики (презентация)
  1. Понятие сети и цели сетевого анализа.
  2. Основные термины и понятие транзитивности.
  3. Понятия коэффициента кластеризации и промежуточности.
  4. Идея сетевого моделирования.
• Лекция 2. Меры центральности (презентация, адаптированная презентация)
  1. Меры центральности и степень связанности.
  2. Центральность в собственных векторах.
  3. Центральность по Кацу и PageRank.
  4. Hyperlink Induced Topic Search и мера близости.
• Лекция 3. Сетевые математические модели (презентация)
  1. Идея моделирования и роль вероятностных распределений.
  2. Степенное распределение, его свойства и вычисление ключевых параметров.
  3. Модель Эрдёша-Реньи и фазовый переход.
  4. Модель Уоттса-Строгаца и блочная модель.
• Лекция 4. Структурные характеристики сетей (презентация)
  1. Качественная и количественная ассортативность сетей, сетевая модулярность.
  2. Понятие структурного подобия и способы его оценки.
  3. Выделение сообществ и иерархическая кластеризация.
  4. Использование информационной энтропии для оценки кластеризации и алгоритм Infomap.
• Лекция 5. Модели построения сетей и перколяция (презентация)
  1. Модель Прайса, модель Барабаши-Альберти и модель копирования.
  2. Построение транспортной сети и обоснование конфигурации «звезда».
  3. Понятия перколяции и гигантского перкаляционного кластера.
  4. Устойчивость к атакам и каскадные отказы.
• Лекция 6. Конфигурационная модель (презентация)
  1. Порядок формирования конфигурационной модели.
  2. Порядок вычисления доли кратных рёбер.
  3. Фазовый переход, перколяция и атака в конфигурационной модели.

Презентации к практическим занятиям

1. Представление графов.
2. Поиск кратчайших путей.
3. Просмотр графов.
4. Первые шаги в Python.
5. Основы объектно-ориентированного программирования.
6. Вычисление центральности в собственных векторах.
7. Генерация графа в модели Эрдёша-Реньи.

Задания для лабораторных работ

1. Требуется написать скрипт на языке Python с реализацией алгоритма Дейкстры для заданного графа. Граф задаётся матрицей смежности или списком смежных вершин. Алгоритм должен находить кратчайшие пути от произвольной начальной вершины до всех остальных. Для представления графов разрешается использовать сторонние библиотеки, но не разрешается использовать реализацию алгоритма Дейкстры в составе сторонних библиотек.
2. С использованием библиотеки NetworkX требуется написать скрипт для вычисления меры центральности в собственных векторах для некоторого графа. Преподавателем будет предоставлена некоторая характеристика мер центральности вершин несложного графа, и требуется подобрать (вручную, не нужно автоматизировать) исходный граф, в которой меры центральности удовлетворяют заданным характеристикам.
3. С использованием библиотеки NetworkX требуется написать скрипт для генерации графа в модели Эрдёша-Реньи с заданными характеристиками. Преподавателем будут даны значения количества вершин и вероятность появления случайного ребра. Требуется вычислить в программе среднюю степень вершины и сравнить её со значением средней степени вершины, полученной по формуле из материала лекций.

Как установить Python

Загрузите установочный файл Python:

• Для Microsoft Windows
• Для MacOS

Установите PyCharm:

• Программа установки

Вопросы для устного зачёта

1. Понятие сети и цели сетевого анализа, основные термины и транзитивность.
2. Понятия коэффициента кластеризации и промежуточности.
3. Понятия меры центральности и степени связанности, центральность в собственных векторах.
4. Центральность по Кацу и алгоритм PageRank.
5. Hyperlink Induced Topic Search и мера близости.
6. Идея моделирования и роль вероятностных распределений, степенное распределение, его свойства и вычисление ключевых параметров.
7. Модель Эрдёша-Реньи и фазовый переход.
8. Модель Уоттса-Строгаца и блочная модель.
9. Качественная и количественная ассортативность сетей, сетевая модулярность, понятие структурного подобия и способы его оценки.
10. Выделение сообществ, иерархическая кластеризация, использование информационной энтропии для оценки кластеризации и алгоритм Infomap.
11. Модель Прайса, модель Барабаши-Альберти и модель копирования.
12. Построение транспортной сети и обоснование конфигурации «звезда».
13. Понятия перколяции и гигантского перкаляционного кластера, устойчивость к атакам и каскадные отказы.
14. Конфигурационная модель и её характеристики.

См. также

• Курс на образовательной платформе университета