Презентации и программа лекций

Учебный курс «Анализ социальных сетей»

 1. Понятие сети и цели сетевого анализа.
 1. Основные термины и понятие транзитивности.
 1. Понятия коэффициента кластеризации и промежуточности.
 1. Идея сетевого моделирования.

 1. Меры центральности и степень связанности.
 1. Центральность в~собственных векторах.
 1. Центральность по~Кацу и PageRank.
 1. Hyperlink Induced Topic Search и мера близости.

 1. Идея моделирования и роль вероятностных распределений.
 1. Степенное распределение, его свойства и вычисление ключевых параметров.
 1. Модель Эрдёша-Реньи и фазовый переход.
 1. Модель Уоттса-Строгаца и блочная модель.

Лекция 4

Структурные характеристики сетей

 1. Качественная и количественная ассортативность сетей, сетевая модулярность.
 1. Понятие структурного подобия и способы его оценки.
 1. Выделение сообществ и иерархическая кластеризация.
 1. Использование информационной энтропии для~оценки кластеризации и алгоритм Infomap.

📌 Презентация

 1. Модель Прайса, модель Барабаши-Альберти и модель копирования.
 1. Построение транспортной сети и обоснование конфигурации «звезда».
 1. Понятия перколяции и гигантского перкаляционного кластера.
 1. Устойчивость к~атакам и каскадные отказы.

 1. Порядок формирования конфигурационной модели.
 1. Порядок вычисления доли кратных рёбер.
 1. Фазовый переход, перколяция и атака в~конфигурационной модели.

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

Алгоритм Дейкстры

Требуется написать скрипт на языке Python с реализацией алгоритма Дейкстры для заданного графа. Граф задаётся матрицей смежности или списком смежных вершин. Алгоритм должен находить кратчайшие пути от произвольной начальной вершины до всех остальных. Для представления графов разрешается использовать сторонние библиотеки, но не разрешается использовать реализацию алгоритма Дейкстры в составе сторонних библиотек.

Центральность узлов в собственных векторах

С использованием библиотеки NetworkX требуется написать скрипт для вычисления меры центральности в собственных векторах для некоторого графа. Преподавателем будет предоставлена некоторая характеристика мер центральности вершин несложного графа, и требуется подобрать (вручную, не нужно автоматизировать) исходный граф, в которой меры центральности удовлетворяют заданным характеристикам.

Модель Эрдёша-Реньи

С использованием библиотеки NetworkX требуется написать скрипт для генерации графа в модели Эрдёша-Реньи с заданными характеристиками. Преподавателем будут даны значения количества вершин и вероятность появления случайного ребра. Требуется вычислить в программе среднюю степень вершины и сравнить её со значением средней степени вершины, полученной по формуле из материала лекций.

Требования к математической подготовке

Для изучения курса требуются следующие математические навыки:

1. Основы линейной алгебры: понятия вектора, матрицы, векторного пространства.
2. Собственные числа и собственные вектора матриц.
3. Операции над матрицами, вычисление определителя матрицы, вычисление обратной матрицы.
4. Понятие системы линейных уравнений и способы решения систем линейных уравнений.
5. Основы теории вероятностей: нормальное распределение и его параметры.