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

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

Тематический План Курса / 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, coordination games, beleif propagation
10. Процессы в сетях: пороговые модели поведения и информационные каскады / Network processess: influence propagation, threshold models, information cascades
11. Процессы в сетях: коллективные явления / Network processess: collective behavior

Модуль 3 / Module 3

Лекции / Lectures

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

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

1. [23.01.2012] 1) Найти значение медианы для степенного распределения. 2) Вычислить среднеквадратичное отклонение (ошибку) в методе максимального правдоподобия. 3) Пострoить распределение степеней узлов в фрагменте internet routing system. (http://www.routeviews.org/) Показать, что это распределение носит степенной характер. Построить cCDF, оценить значение показателя степени по наклону кривой. Вычислить показатель степени используя метод максимального правдоподобия. Сравнить полученные результаты.
2. [30.01.2012] 1) Показатать что в пределе больших n при фиксированном средней степени узла <к>, биномиальное распределение степеней узлов случайного графа превращается в расределение Пуассона. 2) Найти среднее (мат. ожидание) и дисперсию для распределения Пуассона. 3) Написать процедуру для генерации случайных графов в моделях Erdos-Renyi G(n,m) и G(n,p). Построить распределение степеней узлов, найти среднюю степень узла <к> и дисперсию. Провести эксперименты и определить момент возникновения гигантской связанной компоненты. Установить какие изменения происходят с графом при p = ln n/n. Визуализировать графы для различных фазовых состояни. Для визуализации графа в Матлабе (нахождение координат узлов) можно использовать программу GraphViz. Интерфейс к Матлабу доступен здесь или здесь Вызов функции производится командой draw_dot(A), где А матрица смежности графа. Для изображение графа также удобно пользоваться командой gplot.
3. [06.02.2012] 1) Найти скорость роста степени узлов от времени и функцию распределения степеней узлов в модели B-A при равновероятном присоединении. 2) Показать что коэффициент кластеризации для регулярного графа из модели W-S равен C = 3(k-2)/4(k-1), где k- степень узлов в графе 3) Написать процедуру моделирующую процесс предпочтительного присоединения (модель B-A). Провести эксперименты. Визуализировать типчный граф. Численно найти и изобразить функцию распределния степеней узлов.
4. [13.02.2012] 1) Имплементировать нормализованные метрики центральности узлов: степенная (degree centrality), близостная (closeness centrality), промежуточная (betweenness centrality). Для имплиментации удобно воспользоваться библиотекой MatlabBGL 2) Используя полученные функиции рассчитать и графически сравнить значение метрик узов для сетей a) karate club b) political books c) political blogs
5. [20.02.2012] 1) Имплементировать алгоритмы PageRank и Hits (Hubs & Authorities) 2) Рассчитать и сравнить значения Degree Centrality, PageRank и Hits для сетей а) web1 б) web2
6. [27.02.2012] 1) Вычислить корреляционную матрицу структурной эквивалентности узлов в сетях karate_club и dolphins и визулизировать ее командой pcolor. Воспользоваться reverse Cuthill-McKee сортировкой для визуального выделения сильно скоррелированных участков. 2) Вычислить ассортативное смешивание по степеням узлов (корреляцию между степенями соседних узлов) для сетей Princeton, Georgetown, internet_autonomous, political_blogs. Сравнить и объяснить полученные результаты.
7. [12.02.2012] 1) Имплементировать один из двух алгоритмов для нахождения сообществ: Edge betweenness или Spectral modularity. При рассчетах использовать библиотеку MatlabBGL. Найти сообщества в сетях a) karate_club b) dolphins 2) Визуализировать указанные сети и обознчить цветом узлы принадлежащие разным сообществам. Для визуализации использовать Матлаб интерфейс к программе GraphViz.

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

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

• "Networks: An Introduction". Mark Newman. Oxford University Press, 2010.
• "Social and Economic Networks". Matthew O. Jackson. Princeton University Press, 2010.
• "Networks, Crowds, and Markets: Reasoning About a Highly Connected World". David Easley and John Kleinberg, Cambridge University Press 2010.

• Scale Free Networks, Scientific American, A.L Barabasi
• The physics of networks, Physics Today, Mark Newman

• Statistical mechanics of complex networks, R. Albert and A-L. Barabasi
• The Structure and Function of Complex Networks, M. E. J. Newman
• Complex networks: Structure and dynamics, S. Boccaletti et al.
• Evolution of Networks, S. N. Dorogovtsev and J. F. F. Mendes

• Power laws, Pareto distributions and Zipf’s law, M. E. J. Newman
• On random graphs I, P. Erdos and A. Renyi
• On the evolution of random graphs, P. Erdos and A. Renyi
• Collective dynamics of ‘small-world’ networks. Duncan J. Watts and Steven H. Strogatz
• Emergence of Scaling in Random Networks, AL Barabasi and R. Albert
• Centrality in Social Networks. Conceptual Clarification, Linton C. Freeman
• Power and Centrality: A Family of Measures, Phillip Bonacich
• The PageRank Citation Ranknig: Bringing Order to the Web, S. Brin, L. Page
• Authoritative Sources in a Hyperlinked Environment, John M. Kleinberg
• Finding and evaluating community structure in networks, M.E.J. Newman, M. Girvan
• Modularity and community strcuture in networks, M.E.J. Newman
• Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm, D.R. Karger
• Multilevel algorithms for partitioning power-law graphs, A. Abou-rjeili, G. Karypis

• The Mathematics of Infections Diseases, H.W. Hethcote
• Contagion Stephen Morris
• Maximizing the Spread of Influence through a Social Network, D. Kempe, J. Kleinberg, E. Tardos
• Influential Nodes in a Diffusion Model for Social Networks, D. Kempe, J. Kleinberg, E. Tardos
• Reaching a Consensus M.H. DeGroot
• A Necessary and Sufficient Condition for Reaching a Consensus Using DeGroot's Method Roger L. Berger
• A Theory of Fads, Fashion, Custom, and Cultural Change as Information Cascades S. Bikhchandani, D Hirshleifer and I.Welch
• Learning from the Behavior of Others: Conformity, Fads, and Informational Cascades S. Bikhchandani, D Hirshleifer and I.Welch
• Information Cascades in the Laboratory L. Anderson and C. Halt
• Following the Herd Pierre Lemieux
• Dynamic Models of Segregation Thomas C. Schelling
• Threshold Models of Collective Behavior Mark S. Granovetter
• The Economics of Social Networks Matthew O. Jackson
• A Strategic Model of Social and Economic Networks Matthew O. Jackson

• Networks and Epidemics models Matt. J. Keeling and Ken.T.D. Eames
• Network effects in Schellin's model of segregation: new evidences from agent-based simulations Arnaud Banos
• Segregation in netwroks Giorgio Gagiolo, Marco Valente, Nicolaas Vriend