Теория Социальных Сетей. Social Networks: Theory and Applications.

Зима-Весна 2013 / Winter-Spring 2013.

Тематический План Курса / Course Outline

  1. Обзор курса, введение, примеры комплексных сетей / Introduction and examples of complex networks
  2. Анализ сетей: метрики и структурные свойства / Network analysis: structure and metrics
  3. Анализ сетей: статистические свойства и законы распределения / Network analysis: statistcal properties and distributions
  4. Формирование сетей: случайные сети / Network formation: random networks
  5. Формирование сетей: модели роста / Network formation: growth models
  6. Формирование сетей: модели малого мира / Network formation: small world models
  7. Формирование сетей: стратегические модели / Network formation: strategic models
  8. Сетевые сообщества / Network communities
  9. Процессы в сетях: диффузия и распространение информации/ Network processess: diffusion and information propagation
  10. Процессы в сетях: эпедимии / Network processess: epidemics
  11. Процессы в сетях: пороговые модели поведения и информационные каскады / Network processess: influence propagation, threshold models, information cascades
  12. Процессы в сетях: коллективные явления / Network processess: collective behavior

Модуль 3 / Module 3

Лекции / Lectures

  1. [31.01.2012] Комплексные сети / Complex networks. [Lecture1]
    Введение в теорию комплексных систем. Основные понятия в теории сетей. Свойства и метрики анализа сетей.
  2. [31.01.2012] Степенные законы распределения / Power laws. [Lecture2]
    Степенное распределение. Масштабно-инвариантные сети (scale-free networks). Распределение Парето, нормализация, моменты,
  3. [07.02.2012] Случайные графы / Random graphs. [Lecture3]
    Модель Erdos-Renyi. Распределение Бернулли и Пуассона. Функция распределния степеней. Фазовые переходы, возникновение связанной компоненты. Диаметр и кластерный коэффициент. Конфигурационная модель
  4. [07.02.2012] Динамические модели роста сетей / Dynamical growth models. [Lecture4]
    Модель Barabasi-Albert. Предпочтительное присоединение. Уравнение в непрерывном приближении. Временная эволюция степеней узлов. Распределение степеней узлов. Средняя длина пути и кластерный коэффициент. Модели "малого мира". Модель Watts-Strogats. Однопараметрическая модель. Переход от регулярного графа к случайному. Измения кластерного коэффициента и средней длины пути.
  5. [14.02.2012] Метрики центральности узлов / Centrality metrics. [Lecture5 ]
    Понятия центральности и престижа. Модельные графы. Degree centrality, closeness centrality, betweenness centrality, статус/rank prestige (eigenvector centrality). Центральность сети (сentralization).
  6. [21.02.2012] Анализ связей / Links analysis [Lecture6]
    Алгоритм PageRank. Стохастические матрицы. Теорема Perrona-Frobenius. Степенные итерации. Нахождение собственного вектора. Hubs и Authorities. Алгоритм HITS.
  7. [28.02.2012] Структурная эквивалентность / Structural equivalence. [Lecture7]
    8. Метрики структурной эквивалентности узлов. Эвклидово расстояние. Расстояни Хэмминга. (Eucleadean and Hamming distance). Корреляционный коэффициент. Сходство по косинусу (cosine similarity). Ассортативнoe смешивание (homophily). Модулярность (modularity). Ассортативный коэффициент (Assortativity coefficient). Смешивание по степеням узлов (Mixing by degree).
  8. [07.03.2012] Сетевые сообщества / Network communitites [Lecture8 ]
    Понятие сетевых сообществ (network communities). Плотность связей. Метрики. Разделение графа на части (graph partitioning). Разрезы (cuts) в графе. Min-cut, quotent and normalized cuts метрики. Divisive and agglomerative algorithms. Repeated bisection. Корреляционная матрица. Clustering. Классификация алгоритмов нахождения сообществ.
  9. [14.03.2012] Алгоритмы нахождения сетевых сообществ / Network community detection algorithms. [Lecture9]
    Edge Betweenness. Newman-Girvin algorithm. Spectral methods. Modularity maximization algorithm (Newman)
  10. [21.03.2012] Алгоритмы разбиения графов / Graph partitioning algorithms [Lecture10]
    Approximation algorithms. Randomized min-cut (Karges's algorithm). Probability of finding min-cut. Multilevel paradigm. Multilevel algorithm for power law graphs
  11. [27.03.2012] Зачет

Домашние задания / Homeworks

  1. [31.01.2013, due: 14.02.2013] Пострoить распределение степеней узлов в фрагменте internet routing system. (http://www.routeviews.org/). Сеть представлена в виде разряженной матрицы в формате Матлаб .mat файла. Показать, что распределение носит степенной характер. Оценить по возможности значение показателя степени по наклону кривой. Построить кумулятивную функцию распределения, найти значение показателя степени по наклону кривой. Вычислить показатель степени используя метод максимального правдоподобия. Сравнить полученные результаты.
  2. [07.02.2012, due: 21.02.2013] a) Написать процедуру генерации случайных графов в моделях Erdos-Renyi G(n,m) и G(n,p). Построить распределение степеней узлов, найти среднюю степень узла <к> и дисперсию. Провести эксперименты и определить момент возникновения гигантской связанной компоненты.Визуализировать графы для различных фазовых состояни. Для визуализации графа в Матлабе (нахождение координат узлов) можно использовать программу GraphViz. Интерфейс к Матлабу доступен здесь или здесь Вызов функции производится командой draw_dot(A), где А матрица смежности графа. Для изображение графа также удобно пользоваться командой gplot. b) Найти скорость роста степени узлов от времени и функцию распределения степеней узлов в модели B-A при равновероятном присоединении (теоретически, П(к)=const) c) Написать процедуру моделирующую процесс предпочтительного присоединения (модель B-A). Провести эксперименты. Визуализировать типчный граф. Численно найти и изобразить функцию распределния степеней узлов. Найти показатель степени используя метод максимального правдоподобия. Сравнить с теоретическим результатом
  3. [21.02.2013, due: 14.03.2013] 1) Имплементировать нормализованные метрики центральности узлов: степенная (degree centrality), близостная (closeness centrality), промежуточная (betweenness centrality). Для имплиментации удобно воспользоваться библиотекой MatlabBGL Используя полученные функиции рассчитать и графически сравнить значение метрик узов для сетей a) karate club b) political books c) political blogs 2) Имплементировать алгоритмы PageRank и Hits (Hubs & Authorities) Рассчитать и сравнить значения Degree Centrality, PageRank и Hits для сетей а) web1 б) web2 Какие из веб страниц имеют наибольшие значения Degreee Centrality, PageRank и Hubs-Authorities score?
  4. [07.03.2013, due: 21.03.2013] 1) Вычислить корреляционную матрицу (Pearson correlation) структурной эквивалентности узлов в сетях karate_club и dolphins и визулизировать ее командой pcolor. 2) Вычислить величину ассортативного смешивания по степеням узлов (assortativity coefficient) в сетях Princeton, Georgetown, internet_autonomous, political_blogs. Сравнить и объяснить полученные результаты.
  5. [14.03.2013, due 22.03.2013] 1) Имплементировать один из двух алгоритмов для нахождения сообществ: Edge betweenness или Spectral modularity. При рассчетах использовать библиотеку MatlabBGL. Найти сообщества в сетях a) karate_club b) dolphins 2) Визуализировать указанные сети и обозaнчить цветом узлы принадлежащие разным сообществам. Для визуализации использовать Матлаб интерфейс к программе GraphViz.

Модуль 4 / Module 4

Лекции / Lectures

  1. [19.04.2013] Диффузия в сетях / Diffusion on networks [Lecture1]
    Процесс физической диффузии. Уравнение диффузии. Диффузия на сетях. Дискретный оператор Лапласа, Матрица Лапласа, решение уравнения диффузии на графе. Случайные блуждания на графе.
  2. [26.04.2013] Распространение эпидемий / Epidemics [Lecture2]
    Модели SI, SIR, SIS. Решения диф. уравнений. Предельные случаи.
  3. [10.05.2013] Эпидемии в сетях / Epidemics on networks [Lecture3]
    Модели SI, SIR, SIS на сетях. Решения диф. уравнений. Предельные случаи. Моделирование распростронения.
  4. [17.05.2013] Пороговые модели распространения и максимизация влияния /Threshold models and Influence maximization [Lecture4]
    Пороговые модели принятия решений. Granovetter's Threshold model of Collective behavior. Определение наиболее влиятельных узлов
  5. [24.05.2013] Достижение консенсуса / Reaching consenus [Lecture5]
    Обучение в сети. Модель De Groot. Условия достижимости консенсуса.
  6. [31.05.2013] Информaционные каскады / Information cascades [Lecture6]
    Observational learning. Модели каскадов. Условия возникновения.
  7. [07.06.2013] Модели пространственная сегрегация / Spatial segregation model [Lecture7]
    Schelling's segregation model.
  8. [07.06.2013] Стратегические модели формирования сетей / Strategic models of network formation[Lecture8]
    Функия полезности. Эффективность и стабильность. Модель связей. Модель со-авторов.
  9. [07.06.2013] Модели коллективных действий / Collective actionс [Optional material] [Lecture9]
  10. [27.06.2012] Экзамен / Exam

Проекты / Projects

  1. Моделирование распространение эпидемии в сетях (Due: 30.05.2013). Имплементировать SIS/SIR модели распространения эпидемии в сетях. Исследовать поведение моделей на следующих сетях: 1) регулярная двумерная решетка 2) двумерная модель малого мира 3) случайный граф 4) модель предпочительного присоединения BA 5) данная сеть. Для каждой модели/сети построить усредненную зависимость распространения инфекции (% зараженных узлов) от времени при фиксированном выборе параметров модели.

    ПОЯСНЕНИЯ:
    В этом проекте требуется использовать два подхода:
    1. Моделирование т.е когда с помощью случайных блужданий моделируется распространение эпидемии по сети (переход соседей в "зараженнное" сосояние) и подсчитывается количество(доля) вершин в каждом статусе с течением времени (шагов цикла)
    2. Решение дифф. уравнений (на сети) используя матрицы смежности и уравнения выведенные на лекции. Для решение в Матлабе можно использовать функцию ode45. Решение дает вероятности нахождение каждого из узлов в одном из состояний как функцию времени Для сравнения с результатами (1) можно вычислить усредненные по всем узлам вероятности

    Итоговый вывод в работе должен содержать:
    1) итоговое сравнение распространения эпидемии на разных типах сетей (например порог эпидемии и скорость ее распространения)
    2) сравнение решений методом решения ДУ и моделированием

  2. Модель сегрегации Шeллинга на сетях (Due: 21.06.2012). Имплементировать модель Шеллинга на графе.Исследовать поведение модели на следующих сетях: 1) регулярная двумерная решетка с 8 ближайшими соседями 2) двумерная модель малого мира 3) случайный граф 4) модель предпочительного присоединения BA 5) random geometric graph, (для его визуализации в Матлабе удобно использовать функцию gplot()) Исследовать поведение модели в зависимости от порога толерантности агентов и типа графа определить области значений толерантности приводящие к значительной сегрегации.

    ПОЯСНЕНИЯ:
    Результаты работы должны демонстрировать зависимость индекса смешивание общества (или других метрик однородности) достигаемого в равновесии в зависимости от порога толерантности агентов для разных типов сетей

Литература по курсу / References

Книги / Books Вводные статьи / Introductiory Articles Обзоры / Reviews Научные статьи / Papers

Програмное обеспечение / Software

Похожие курсы / Similar courses