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 Makarov
Course page at cs.hse: Magolego Social Network Analysis

Course Outline

1. Introduction to network science
2. Descriptive network analysis
3. Mathematical models of networks
4. Node centrality and ranking on networks
5. Network communities
6. Network structure and visualization
7. Epidemics and information spreading in networks
8. Diffusion of innovation
9. Strategic network formation
10. Spatial models of segregation

Lectures

1. [07.04.2017] Introduction to network science. [Lecture 1] [Video]
   Introduction to network science. Examples.
2. [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.
3. [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
4. [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.
5. [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.
6. [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.
7. [26.05.2017] Epidemics and information spreading in networks [Lecture 7] [Video]
   Epidemic models on networks. SI, SIS, SIR models. Rumor spreading. Propagation trees.
8. [02.06.2017] Diffusion of innovation [Lecture 8] [Video]
   Diffusion of innovation. Linear threshold model. Influence maximization.
9. [09.06.2017] Spatial models of segregation [Lecture 9][Video]
   Schelling's segregation model. Spatial segregation. Agent based modelling. Segregation in networks
10. [16.06.2017] Exam
    

Labs & Homeworks

Available at Magolego Social Network Analysis

Reading 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.

Lecture 2:
• 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.

Lecture 3:
• 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".

Lecture 4:
• 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

Lecture 5:
• 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.

Lecture 6:
• 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.

Lecture 7:
• 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".

Lecture 8:
• 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".

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

• "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

EdX
• "Networks, Crowds and Markets", David Easley, Jon Kleinberg, Eva Tardos, Cornell University

University courses online
• 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