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

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

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

1. Введение в теорию социальных сетей / Introduction and examples of complex networks
2. Степенные законы распределения / Power laws
3. Модели формирования и роста сетей / Network formation
4. Анализ структуры связей и роли узлов / Network structure and link analysis
5. Сетевые сообщества / Network communities
6. Диффузия и распространение эпидемий / Diffusion and epidimecs on networks
7. Модели распространение влияния / Influence propagation
8. Модели достижения консенсуса / Reaching consensus
9. Информационные каскады / Information cascades
10. Модель пространственной сегрегации / Spatial segregation models

Модуль 3 / Module 3

Лекции / Lectures

1. [13.01.2014] Комплексные сети / Complex networks. [Lecture 1] [Audio ]
   Введение в теорию комплексных систем. Основные понятия в теории сетей. Свойства и метрики анализа сетей.
   Introduction to the complex network theory. Network properties and metrics.
2. [20.01.2014] Степенные законы распределения / Power laws. [Lecture 2] [Video]
   Степенное распределение. Масштабно-инвариантные сети (scale-free networks). Распределение Парето, нормализация, моменты. Закон Ципфа.Граф ранк-частота.
   Power law distribution. Scale-free networks.Pareto distribution, noramlization, moments. Zipf law. Rank-frequency plot.
3. [27.01.2014] Случайные графы / Random graphs. [Lecture 3] [Video]
   Модель Erdos-Renyi. Распределение Бернулли и Пуассона. Функция распределния степеней. Фазовые переходы, возникновение связанной компоненты. Диаметр и кластерный коэффициент. Конфигурационная модель
   Erdos-Reni random graph model. Poisson and Bernulli distributions. Distribution of node degrees. Phase transition, gigantic connected component. Diameter and cluster coefficient. Configuration model
4. [03.02.2014] Малый мир и динамические модели роста / Small world and dynamical growth models. [Lecture 4] [Video]
   Модель Barabasi-Albert. Предпочтительное присоединение. Уравнение в непрерывном приближении. Временная эволюция степеней узлов. Распределение степеней узлов. Средняя длина пути и кластерный коэффициент. Модели "малого мира". Модель Watts-Strogats. Однопараметрическая модель. Переход от регулярного графа к случайному. Измения кластерного коэффициента и средней длины пути.
   Barabasi-Albert model. Preferential attachement. Equation in continues approximation. Time evolition of node degrees. Node degree distribution. Average path length and clustering coefficient. Small world model. Watts-Strogats model. Transition from ragular to random. changes in clustering coefficient and ave path lenght.
5. [10.02.2014] Метрики центральности узлов и анализ связей /Nodes and Links analysis. [Lecture 5 ]
   Понятия центральности и престижа. Модельные графы. Degree centrality, closeness centrality, betweenness centrality, статус/rank prestige (eigenvector centrality). Центральность сети (сentralization). Алгоритм PageRank. Стохастические матрицы. Теорема Perrona-Frobenius. Степенные итерации. Нахождение собственного вектора. Hubs и Authorities. Алгоритм HITS. Сравнение ранжировок. Расстояние Kendall-Tau.
   Node centrality metrics, degree centrality, closeness centrality, betweenness centrality, eigenvector centrality. Graph strucure based metrics. PageRank, stochastic metric and Perron=Frobenius theorem. Power iterations. Hubs and Authorites. HITS algorithm. Kendall-Tau ranking distance.
6. [17.02.2014] Структурная эквивалентность / Structural equivalence. [Lecture 6]
   
Метрики структурной эквивалентности узлов. Эвклидово расстояние. Расстояни Хэмминга. Корреляционный коэффициент. Сходство по косинусу. Ассортативнoe смешивание. Модулярность. Ассортативный коэффициент. Смешивание по степеням узлов.
Structural equivalency metrics. Eucleadean and Hamming distance. Correlation coefficient. Cosine similarity.Assortative mixing and homophily. Modularity. Mixing by degree.
7. [24.02.2014] Сетевые сообщества / Network communitites [Lecture 7] [Video]
   Понятие сетевых сообществ Плотность связей. Метрики. Разделение графа на части. Разрезы в графе. Минимальный разрез, нормированные разрез.Агломеративные и разделяющие алгоритмы. Корреляционная матрица. Кластеризация. Понятие промежуточности ребер. Алгортмы Ньюмана Гирвина. Спектральные методы. Оптиизация модулярности. Классификация алгоритмов нахождения сообществ.
   Network communities. Graph density. Graph pertitioning. Min-cut, quotent and normalized cuts metrics. Divisive and agglomerative algorithms. Repeated bisection. Correlation matrix. Clustering. Edge Betweenness. Newman-Girvin algorithm. Spectral methods. Modularity maximization algorithm (Newman)
8. [03.03.2014] Алгоритмы разбиения графов / Graph partitioning algorithms [Lecture 8] [Video]
   Приблииженные алгорирмы. Задача нахождения минимально разреза в графе. Алгорим randomized min-cut. Многоуровневый подход. Нахождение сообществ многоурвневым методом. Локальная кластеризация. Понятие проводимости, алгоритм Nibble
   Approximation algorithms. Randomized min-cut (Karges's algorithm). Probability of finding min-cut. Multilevel paradigm. Multilevel algorithm for power law graphs. Local clustering. Conductance. Nibble Algorithms.
9. [10.03.2014] Сетевые структуры / Network structures [Lecture 9] [Video]
   Понятие к-ядра графа, диады и триады в графах, мотивы.
   Graph motiffs, k-cores, diad and triad census
10. [17.03.2014] Специальные типы сетей / Special classes of networks [Lecture 10] [ Video]
    Двудольные графы и сети аффилированости. Сети с положительными и отрицательными связями
    Bi-partite graphs and affiliation networks. Networks with signed edges
11. [24.03.2014] Зачет
    

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

1. [27.01.2014, due: 03.02.2014]
   1. Построить кумулятивную функцию распределения (rank-frequency plot) для частот с которыми встречаются слова в корпусе английского языка wordcounts. Проверить выполнение закона Ципфа. Найти показатель степенной функции alpha и среднее квадратичное отклонение sigma. Указать минимальную, максимальную, среднюю частоту и медиану.
   2. Построить распредение и кумулятивную функцию распределения степеней узлов в следующих сетях (входящих и выходящих степеней узлов) в следующих сетях:
   а) Фрагмент сети интернет раутинга network
   b) Фрагмент веб графа web graph
   c) Фрагмент Facebook facebook
   3. Являеются ли полученные рапсределения степенными? Найти минимальное, максимальное и среднее значение степени узлов k (k_in, k_out). Вычислить alpha и sigma используя метод ML максимального правдоподобия и найти оптимальные значения x_min используя тест Колмогорова-Смирнова.
2. [03.02.2014, due: 17.02.2014]
   1. Написать процедуру генерации случайных графов в модели Erdos-Renyi G(n,p).
   2. Написать процедуру моделирующую процесс предпочтительного присоединения (модель B-A).
   3. Используя полученные генераторы провести следующие исследования:
   а) найти и изобразить распределение степеней узлов, мин, мах, медиану, среднюю степень.
   в) Визуализировать полученные сети
   с) Для BA модели найти степенной показатель alpha и величину sigma, для ER модели вычислить среднее и ср. ква отклонение.
   d) В полученных графах найти и изобразить на графике кластерный коэффициент и среднюю длину пути как функицю от числа узлов графа N (p > p_c для ER)
   4. В модели ER провести численные эксперименты и найти момент возникновения гигантской связанной компоненты (critical value of p). Найти и графически изобразить зависимость среднего размера самой большой компоненты графа от параметра p
3. [17.02.2014, due: 03.03.2014]
   1. Имплементировать нормализованные метрики центральности узлов: степенная (degree centrality), близостная (closeness centrality), промежуточная (betweenness centrality). Используя полученные функиции рассчитать и графически сравнить значение метрик узов для сетей 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? 3. Отранжировать узлы по метрикам и сравнить ранжированные списки узлов расстоянием Kendall tau. Сравнение произвести для топ 10,100,1000 узлов.
4. [03.03.2014, due: 21.03.2014]
   1. Имплементировать любые два из трех алгоритмов для нахождения сообществ: Edge betweenness, Spectral modularity, Nibble (random walk). Используя написанные алгоритмы, найти сообщества в сетях a) karate_club b) dolphins c) political_blogs
   2. Сравнить найденные сообщества используя три метрики: модулярность, плотность, conductance.
   3. Визуализировать указанные сети и обозaнчить цветом узлы принадлежащие разным сообществам.

Материал к лекциям / Reading material

Lecture 1:
• Albert-Laszlo Barabasi and Eric Bonabeau. Scale Free Networks. Scientific American, p 50-59, 2003
• Mark Newman. The physics of networks. Physics Today,2008
• Stanley Milgram. The Small-World Problem. Psychology Today, Vol 1, No 1, pp 61-67, 1967
• J. Travers and S. Milgram. An Experimental Study of the Small World Problem. Sociometry, vol 32, No 4, pp 425-433, 1969
• Mark Granovetter. The strengtth of weak ties , American Journal of Sociology, 78(6):1360-1380, 1973.

Lecture 2:
• M. E. J. Newman. Power laws, Pareto distributions and Zipf’s law. Contemporary Physics 46(5), 323-351, 2005
• A. Clauset, C.R. Shalizi, M.E.J. Newman. Power-law distributions in empirical data. SIAM Review 51(4), 661-703, 2009
• M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
• M.L. Goldstein, S.A. Morris, and G.G. Yen. Problems with fitting to the power-law distribution, Eur. Phys. J. B 41, pp 255–258, 2004.
• Chapter 18. Power Laws and Rich-Get-Richer Phenomena. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

Lecture 3:
• P. Erdos and A. Renyi. On random graphs I. Publ. Math. Debrecen, 1959.
• P. Erdos and A. Renyi. On the evolution of random graphs. Magyar Tud. Akad. Mat. Kutato Int. Koezl., 1960.
• Chapter 12. Random graphs. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 4:
• Duncan J. Watts and Steven H. Strogatz. Collective dynamics of ‘small-world’ networks. . Nature 393:440-42, 1998.
• AL Barabasi and R. Albert. Emergence of Scaling in Random Networks. Science, 286, 1999.
• Chapter 14. Models of network formation. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
• Chapter 20. The Small-World Phenomenon. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

Lecture 5:
• Linton C. Freeman. Centrality in Social Networks. Conceptual Clarification. Social Networks, Vol 1, pp 215-239, 1978
• Phillip Bonacich. Power and Centrality: A Family of Measures. American journal of sociology, Vol.92, pp 1170-1182, 1987.
• S. Brin, L. Page. The PageRank Citation Ranknig: Bringing Order to the Web.
• John M. Kleinberg. Authoritative Sources in a Hyperlinked Environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.
• Chapter 7. Measures and metrics. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
• Chapter 14. Link Analysis and Web Search. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
• Chapter 5. Centrality and Prestige. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994

Lecture 6:
• M. Newman. Mixing patterns in networks. Phys. Rev. E, Vol. 67, p 026126, 2003
• Chapter 9. Structural Equivalence. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
• Chapter 12. Network Positions and Roles. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
• Chapter 7. Measures and metrics. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 7:
• M.E.J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 2004.
• M.E.J. Newman. Modularity and community structure in networks. PNAS Vol. 103, N 23, pp 8577-8582, 2006
• S. E. Schaeffer. Graph clustering. Comp. Sci. Rev., Vol. 1, p 27-64, 2007
• Chapter 7. Matrix algorithms and graph partitioning. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 8:
• D.R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. Proceedings SODA '93, p. 21-30, 1993
• A. Abou-rjeili, G. Karypis. Multilevel algorithms for partitioning power-law graphs. In Proceedings IPDPS '06, p 10, 2006
• G.Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. on Sci. Comp., Vol. 20, p 359-392, 1998.
• Daniel A. Spielman, Shang-Hua Teng. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal on computing, Vol. 42, p. 1-26, 2013
• R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. In Proc. FOCS, 2006.

Lecture 9:
• S. Fortunato. Community detection in graphs . Physics Reports, Vol. 486, pp. 75-174, 2010
• V. Batagelj, M. Zaversnik. An O(m) Algorithms for Cores Decomposition of Networks. 2003
• L. da F. Costa, F. A. Rodrigues, et. al. Characterization of complex networks: A survey of measurements.Advances in Physics, Vol. 56, pp. 167-242, 2007
• R. Milo, S. Shen-Orr, S. Itzkovitz et al. Network motifs: simple building blocks of complex networks. Science 298 (5594): 824–827, 2002
• Chapter 7. Coheseve Subgroups. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994

Lecture 10:
• D. Cartwright, F. Harary. Structural balance: A generalization of Heider's theory. Psychological review, 63 (5): 277-293 1956.
• Leonid Zhukov. Spectral Clustering of Large Advertiser Datasets. Technical report Overture R&D, 2003.
• Chapter 5. Positive and Negative Relationships. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
• Chapter 6. Structural Balance and Transitivity. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
• Chapter 8. Affiliation and Overlappipng Subgroups. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994

Модуль 4 / Module 4

Лекции / Lectures

1. [31.03.2014] Диффузия в сетях / Diffusion on networks [Lecture 1] [Video]
   Процесс физической диффузии. Уравнение диффузии. Диффузия на сетях. Дискретный оператор Лапласа, Матрица Лапласа, решение уравнения диффузии на графе. Случайные блуждания на графе.
   Physical diffusion. Diffusion equation. Diffusion on netowrks. Discrete Laplace operator, Lapalce matrix. Solution of the diffusion equation. Random walks on graph.
2. [07.04.2014] Распространение эпидемий / Epidemics [Lecture 2] [Video]
   Модели SI, SIR, SIS. Решения диф. уравнений. Предельные случаи.
   Epidmic models SI, SIS, SIR. Solution of diff. equations. Limiting cases.
3. [14.04.2014] Эпидемии в сетях / Epidemics on networks [Lecture 3] [Video]
   Модели SI, SIR, SIS на сетях. Моделирование распростронения.
   Epidmic models SI, SIS, SIR. Modeling of infectino propagation
4. [21.04.2014] Пороговые модели влияния /Threshold models and Influence maximization [Lecture 4] [Video]
   Распространение вляния. Пороговые модели принятия решений.Модель Гранноветера. Определение наиболее влиятельных узлов.
   Social diffusion.Granovetter's Threshold model of Collective behavior. Most influential nodes in networks.
5. [28.04.2014] Распространение идей / Social contagion [Lecture 5] [Video]
   Распростанение идей. Модель каскадов. Размеры касакдов
   Cascades in networks. Basic cascade model. Cascade capacity.
6. [12.05.2014] Информaционные каскады / Information cascades [Lecture 6] [Video]
   Наблюдательное обучение. Информационные каскады. Условия воникновения каскадов
   Observational learning. Information cascades.
7. [19.05.2014] Достижение консенсуса / Reaching consenus [Lecture 7]
   Обучение в сети. Модель Де Грута. Условия достижимости консенсуса. Социальное влияние
   Social learning. De Groot model. Reaching consensus
8. [02.06.2014] Стратегические модели формирования сетей / Strategic models of network formation[Lecture 8]
   Функия полезности. Эффективность и стабильность. Модель связей. Модель со-авторов.
   Stratigic model. Utilities. Stability and efficiency. Distance based utility, co-author models.
9. [09.06.2014] Модели пространственная сегрегация / Spatial segregation model [Lecture 9] [Video]
   Пространственная сегрегация. Модель Шиллинга. Моделирование с помощью агентов
   Schelling's segregation model. Spatial segregation. Agent based modelling.
10. [23.06.2014] Экзамен / Exam

Проекты / Projects

1. Моделирование распространение эпидемии в сетях . Имплементировать SIS/SIR модели распространения эпидемии в сетях. Исследовать поведение моделей на следующих сетях: 1) регулярная двумерная решетка 2) двумерная модель малого мира 3) случайный граф 4) модель предпочительного присоединения BA 5) данная сеть. Для каждой модели/сети построить усредненную зависимость распространения инфекции (% зараженных узлов) от времени при фиксированном выборе параметров модели.
   
   ПОЯСНЕНИЯ:
   В этом проекте требуется использовать два подхода:
   1. Моделирование т.е когда с помощью случайных блужданий моделируется распространение эпидемии по сети (переход соседей в "зараженнное" сосояние) и подсчитывается количество(доля) вершин в каждом статусе с течением времени (шагов цикла)
   2. Решение дифф. уравнений (на сети) используя матрицы смежности и уравнения выведенные на лекции. Для решение в Матлабе можно использовать функцию ode45. Решение дает вероятности нахождение каждого из узлов в одном из состояний как функцию времени Для сравнения с результатами (1) можно вычислить усредненные по всем узлам вероятности
   
   Итоговый вывод в работе должен содержать:
   1) итоговое сравнение распространения эпидемии на разных типах сетей (порог эпидемии и скорость ее распространения)
   2) сравнение решений полученных методом ДУ и моделированием
   
   
2. Моделирование распространения влияния в сети Имплементировать a) Independent cascade model b) Linear thresholod model. Исследовать поведение моделей на тех же сетях, что и в предыдущем задании.

Материал к лекциям / Reading material

Lecture 1:
• Lovasz, L. Random walks on graphs: a survey. In Combinatorics, Paul Erdos is eighty. pp. 353 – 397. Budapest: Janos Bolyai Math. Soc., 1993
• Chung, Fan R.K. Spectral graph theory (2ed.). Providence, RI: American Math. Soc., 1997
• Chapter 6. Mathematics of networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 2:
• H.W. Hethcote. The Mathematics of Infections Diseases. SIAM Review, Vol. 42, No. 4, pp. 599-653, 2000
• Chapter 17. Epidemics on networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 3:
• Matt. J. Keeling and Ken.T.D. Eames. Networks and Epidemics models Journal R. Soc. Interface, Vol 2, pp 295-307, 2005
• G. Witten and G. Poulter Simulations of infections diseases on networks Computers in Biology and Medicine, Vol 37, No. 2, pp 195-205, 2007
• M. Kuperman and G. Abramson Small World Effect in an Epidemiological Model., Phys. Rev. Lett., Vol 86, No 13, pp 2909-2912, 2001
• Chapter 17. Epidemics on networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
• Chapter 21. Epidemics. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

Lecture 4:
• Mark S. Granovetter. Threshold Models of Collective Behavior. American Journal of Sociology Vol. 83, No. 6, pp. 1420-1443, 1978.
• H. Peyton Young. The Diffusion of Innovations in Social Networks. In L. E. Blume and S. N. Durlauf (eds.), The Economy as an Evolving Complex System III (2003)
• D. Kempe, J. Kleinberg, E. Tardos. Maximizing the Spread of Influence through a Social Network. In Proc. KDD 2003.
• D. Watts. A simple model of global cascades on random networks. Proc. Natl. Acad. Sci., vol. 99 no. 9, 5766-5771, 2002.
• Chapter 19. Cascading Behavior in Neworks. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
• Chapter 7. Diffusion through Networks. Matthew O. Jackson. "Social and Economic Networks".

Lecture 5:
• D. Kempe, J. Kleinberg, E. Tardos. Influential Nodes in a Diffusion Model for Social Networks. Lecture Notes in Computer Science, Eds C. Luis, I.Giuseppe et.al, 2005
• S. Morris. Contagion. Review of Economic Studies 67, 57-78, 2000.
• L.Backstrom, D. Huttenlocher, J. Kleinbrg, X. Lan, Group Formation in Large Social Networks: Membership, Growth and Evolution, In Proc. KDD 2006.
• J.L. Iribarren, E. Moro, Impact of Human Activity Patterns on the Dynamics of Information Diffusion, Phys. Rev. Letters, Vol 103, 038702, 2009
• J. Leskovec, L. Adamic, B. Huberman, The Dynamics of Viral Marketing, EC 2006
• Chapter 19. Cascading Behavior in Neworks. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

Lecture 6:
• A. V. Banerjee. A Simple Model of Herd Behavior. The Quarterly Journal of Economics, Vol. 107, No. 3, pp. 797-817, 1992.
• S. Bikhchandani, D Hirshleifer and I.Welch. A Theory of Fads, Fashion, Custom, and Cultural Change as Information Cascades. Journal of Political Economy. Vol. 100, pp. 992-1026, 1992.
• S. Bikhchandani, D Hirshleifer and I.Welch. Learning from the Behavior of Others: Conformity, Fads, and Informational Cascades
• L. Anderson and C. Halt. Information Cascades in the Laboratory. The American Economic Review, Vol. 87, No. 5 (Dec., 1997), pp. 847-862
• Pierre Lemieux. Following the Herd . Regulation, Winter 2003-2004
• Chapter 16. Information Cascades. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

Lecture 7:
• M.H. DeGroot. Reaching a Consensus. Journal of the American Statistical Association, 1974, Vol 69, No 345
• Roger L. Berger. A Necessary and Sufficient Condition for Reaching a Consensus Using DeGroot's Method. Journal of the American Statistical Association, Vol. 76, No 374, 1981, pp 415-418
• Noah Friedkin, and Eugene C. Johnsen, Social Influence Networks and Opinion Change Advances in Group Processes 16:1-29, 1999
• B. Golub and M. Jackson Naive Learning in Social Networks and the Wisdom of Crowds, Amer. Econ. J. Microeconomics, 2:1, pp 112-149, 2010
• Chapter 8. Learning and Networks. Matthew O. Jackson. "Social and Economic Networks".

Lectue 8:
• Matthew O. Jackson. The Economics of Social Networks. Calfornia Institute of Technology, 2005.
• Matthew O. Jackson. A Strategic Model of Social and Economic Networks. Journal of Economic Theory, Vol 71, pp 44-74, 1996.
• Chapter 6. Strategic Network Formation. Matthew O. Jackson. "Social and Economic Networks".

Lecture 9:
• Thomas C. Schelling Dynamic Models of Segregation , Journal of Mathematical Sociology, Vol. 1, pp 143-186, 1971.
• Arnaud Banos Network effects in Schellin's model of segregation: new evidences from agent-based simulations. Environment and Planning B: Planning and Design Vol.39, no. 2, pp. 393-405, 2012.
• Giorgio Gagiolo, Marco Valente, Nicolaas Vriend Segregation in netwroks. Journal of Econ. Behav. & Organization, Vol. 64, pp 316-336, 2007.

Основная литература по курсу / Textbooks

Книги / Books:

• Mark Newman."Networks: An Introduction". Oxford University Press, 2010.
• Matthew O. Jackson. "Social and Economic Networks". Princeton University Press, 2010.
• David Easley and John Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World." Cambridge University Press 2010.
• Stanley Wasserman and Katherine Faust. "Social Network Analysis. Methods and Applications." Cambridge University Press, 1994

Обзоры / Reviews:

• R. Albert and A-L. Barabasi. Statistical mechanics of complex networks. Rev. Mod. Phys, Vol. 74, p 47-97, 2002
• M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Review, Vol. 45, p 167-256, 2003
• S. Boccaletti et al. Complex networks: Structure and dynamics. Phys. Reports, Vol. 424, p 175-308, 2006
• S. N. Dorogovtsev and J. F. F. Mendes. Evolution of Networks. Adv. Phys. Vol. 51, N 4, p 1079-1187

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

• Computations: Matlab, Octave, R, Python
• Graph Visualization: Gephi, yEd
• Matlab libraries:
  • Graph algorithms: MatlabBGL
  • Graph layout: GraphViz. Matlab interface for GraphViz gvraphviz4matlab or graphviz
• Python libraries:
  • Linear algebra algorithms: Numpy, SciPy
  • Graph algorithms and visualizaton: NetworkX, iGraph
• R libraries:
  • Graph algorithms: igraph, statnet

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

• Social and Information Network Analysis, Jure Leskovec, Stanford
• The structure of Information Networks , Jon Kleinberg, Cornell University
• Networks, Jon Kleinberg, Eva Tardos, David Easley, Cornell University
• Structure and Dynamics of Networked Information, David Kempe, University of Southern California
• Networked Life , Michael Kearns, University of Pennsylvania
• Network Theory , Dragomir R. Radev, Columbia University
Coursera:
• Social and Economic Networks: Models and Analysis, Matthew O. Jackson, Stanford University
• Social Network Analysis, Lada Adamic, University of Michigan
• Networked Life , Michael Kearns, University of Pennsylvania