Social Network Analysis. MAGoLEGO course.
Spring 2017. Module 4
Department of Data Analysis and Artificial Intelligence, School of Computer Science.
Instructors: Prof. Leonid Zhukov, Dr. Ilya MakarovCourse page at cs.hse: Magolego Social Network Analysis
Course Outline
- Introduction to network science
- Descriptive network analysis
- Mathematical models of networks
- Node centrality and ranking on networks
- Network communities
- Network structure and visualization
- Epidemics and information spreading in networks
- Diffusion of innovation
- Strategic network formation
- Spatial models of segregation
Lectures
- [07.04.2017] Introduction to network science. [Lecture 1] [Video]
Introduction to network science. Examples. - [14.04.2017] Descriptive network analysis.
[Lecture 2] [Video]
Basic graph theory notations. Node degree. Node degree distribution. Power laws. Scale free networks. Connected components. Graph diameter. Average path length. Local and global clustering coefficients. Transitivity. - [21.04.2017] Mathematical models of networks. [Lecture 3][Video]
Erdos-Reni random graph model. Bernoulli distribution. Phase transition, gigantic connected component. Diameter and cluster coefficient. Barabasi-Albert model. Preferential attachement. Small world model. Watts-Strogats model. Transition from regular to random - [28.04.2017] Node centrality and ranking on networks. [Lecture 4] [Video]
Node centrality metrics, degree centrality, closeness centrality, betweenness centrality, eigenvector centrality. Katz status index and Bonacich centrality, alpha centrality PageRank,Hubs and Authorites. - [12.05.2017] Network communities
[Lecture 5] [Video]
Cohesive subgroups. Graph cliques. Network communities. Graph partitioning. Modularity. Edge Betweenness. Spectral partitioning. Modularity maximization. Heuristic methods. Label propagation. Fast community unfolding. Walktrap. - [19.05.2017] Network structure and visualization
[Lecture 6] [Video from 2016 course offerning]
k-core decomposition of networks. Diads and triads. Edge reciprocity. Frequent subgraphs. Network motifs.
Assortative mixing. Network visualization. Forde directed layouts. Adjacency matrix ordering.
- [26.05.2017] Epidemics and information spreading in networks
[Lecture 7] [Video]
Epidemic models on networks. SI, SIS, SIR models. Rumor spreading. Propagation trees. - [02.06.2017] Diffusion of innovation
[Lecture 8] [Video]
Diffusion of innovation. Linear threshold model. Influence maximization. - [09.06.2017] Spatial models of
segregation [Lecture 9][Video]
Schelling's segregation model. Spatial segregation. Agent based modelling. Segregation in networks - [16.06.2017] Exam
Labs & Homeworks
Available at Magolego Social Network AnalysisReading material
-
Lecture 1:
- Chapter1. Introduction. Albert-Laszlo Barabasi, "Network Science", Cambridge University Press, 2016
- Chapter 1. Overview. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
- 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 strength of weak ties , American Journal of Sociology, 78(6):1360-1380, 1973.
- J. Leskovec and E. Horvitz. Planetary-Scale Views on a Large Instant-Messaging Network. Proceedigs WWW 2008
- L. Backstrom, P. Boldi, M. Rosa, J. Ugander, S. Vigna. Four Degrees of Separation. WebSci '12 Procs. 4th ACM Web Science Conference, pp 33-42, 2012
- Chapters 1-2. Eric Kolaczyk, Gabor Csardi. Statistical Analysis of Network Data with R. Springer, 2014.
- Chapter2. Graph Theory. Albert-Laszlo Barabasi, "Network Science", Cambridge University Press, 2016
- Chapter 2, Graphs, Chapter 18, Power laws, D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World"
- 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
- Chapter 4. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
- Chapters 6,8. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
- Chapter 4. Descriptive Analysis of Network Graph Characteristics. Eric Kolaczyk, Gabor Csardi. Statistical Analysis of Network Data with R. Springer, 2014.
- Chapter3. Random Networks. Chapter5. The Barabasi-Albert model. Albert-Laszlo Barabasi, "Network Science", Cambridge University Press, 2016
- 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.
- 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 18, Power Laws, Chapter 20, The Small-world Phenomenon, D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
- 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.
- Sergey Brin, Larry Page. The Anatomy of a Large-Scale Hypertextual Web Search Engine, ,1998.
- John M. Kleinberg. Authoritative Sources in a Hyperlinked Environment. Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, 1998.
- Amy N. Langville and Carl D. Meyer, A Survey of Eigenvector Methods of Web Information Retrieval. 2004
- 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
- Chapter 9. Communities. Albert-Laszlo Barabasi, "Network Science", Cambridge University Press, 2016
- Mark Granovetter. The strength of weak ties , American Journal of Sociology, 78(6):1360-1380, 1973.
- S. E. Schaeffer. Graph clustering. Comp. Sci. Rev., Vol. 1, p 27-64, 2007
- S. Fortunato. Community detection in graphs . Physics Reports, Vol. 486, pp. 75-174, 2010
- M.E.J. Newman. Modularity and community structure in networks. PNAS Vol. 103, N 23, pp 8577-8582, 2006
- M.E.J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 2004.
- G. Palla, I. Derenyi, I. Farkas, T. Vicsek, Uncovering the overlapping community structure of complex networks in nature and society, Nature 435, 814-818, 2005.
- P. Pons and M. Latapy. Computing communities in large networks using random walks, Journal of Graph Algorithms and Applications, 10, 191-218, 2006.
- V.D. Blondel, J.-L. Guillaume, R. Lambiotte, E. Lefebvre. Fast unfolding of communities in large networks, J. Stat. Mech. P10008, 2008.
- 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
- H. Gibson, J. Faith, P. Vickers. A survey of two-dimensional graph layout techniques for information visualization. Information Visualization,12, 324-357, 2012.
- Chapter 10. Spreading phenomena. Albert-Laszlo Barabasi, "Network Science", Cambridge University Press, 2016
- 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
- Y. Moreno, M. Nekovee, A. Pacheco. Dynamics of rumor spreading in complex networks. Phys. Rev. E 69, 066130, 2004
- M. Nekovee, Y. Moreno, G. Biaconi, M. Marsili. Theory of rumor spreading in complex social networks. Physica A 374, pp 457-470, 2007
- 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 21.Epidemics. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
- Mark S. Granovetter. Threshold Models of Collective Behavior. American Journal of Sociology Vol. 83, No. 6, pp. 1420-1443, 1978.
- 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.
- M. Richardson, P. Domingos. Mining Knowledge-Sharing Sites for Viral Marketing. In Proc. KDD, 2002.
- 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)
- S. Morris. Contagion. Review of Economic Studies 67, 57-78, 2000.
- Chapter 19. Cascading Behavior in Neworks. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".
- 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.
Lecture 2:
Lecture 3:
Lecture 4:
Lecture 5:
Lecture 6:
Lecture 7:
Lecture 8:
Lecture 9:
Textbooks
- "Network Science", Albert-Laszlo Barabasi, Cambridge University Press, 2016
- "Networks, Crowds, and Markets: Reasoning About a Highly Connected World", David Easley and John Kleinberg. Cambridge University Press 2010.
- "Social Network Analysis. Methods and Applications",Stanley Wasserman and Katherine Faust, Cambridge University Press, 1994
- "Statistical Analysis of Network Data with R", Eric Kolaczyk, Gabor Csardi, Springer, 2014.
Software
- Computations: R with RStudio
-
R libraries:
- Graph algorithms and visualizaton: iGraph
-
Visualization:
- Open Graph Vizulization platform Gephi
SNA courses online
-
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
- "Networks, Crowds and Markets", David Easley, Jon Kleinberg, Eva Tardos, Cornell University
- 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
EdX
University courses online