Social Network Analysis. MAGoLEGO course.

Spring 2015. Module 4

Department of Data Analysis and Artificial Intelligence, School of Computer Science.

Instructors: Prof. Leonid Zhukov, Dr. Ilya Makarov
Teaching assistant: Andrey Shestakov

Course wiki page: Magolego SNA 2015
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. Social media and information flow in networks
8. Social influence and decision making

Lectures

1. [03.04.2015] Introduction to network science. [Lecture 1] [Video]
   Introduction to network science. Examples.
2. [10.04.2015] 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. [17.04.2015] 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. [24.04.2015] 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. [15.05.2015] 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. [22.05.2015] Network structure and visualization [Lecture 6] [Video]
   
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. [29.05.2015] Social media and information flow in networks [Lecture 7] [Video]
   Epidemic models on networks. SI, SIS, SIR models. Rumor spreading. Propagation trees.
8. [05.06.2015] Diffusion of innovation [Lecture 8]
   Diffusion of innovation. Linear threshold model. Influence maximization.
9. [26.06.2015] Exam
   

Labs & Homeworks

Available at Magolego SNA 2015

Reading material

Lecture 1:
• 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:
• 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:
• 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 14. Models of network formation. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
• Chapter 12. Random graphs. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
• 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 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 5:
• 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.
• Chapter 11. Matrix algorithms and graph partitioning. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

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:
• 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".
• Chapter 7. Diffusion through Networks. Matthew O. Jackson. "Social and Economic Networks".

Textbooks

Books:

• Stanley Wasserman and Katherine Faust. "Social Network Analysis. Methods and Applications." Cambridge University Press, 1994
• David Easley and John Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World." Cambridge University Press 2010.
• Mark Newman."Networks: An Introduction". Oxford University Press, 2010.
• Eric Kolaczyk, Gabor Csardi. Statistical Analysis of Network Data with R. Springer, 2014.

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

Software

• Computations: R with RStudio
• R libraries:
  • Graph algorithms and visualizaton: iGraph
• Visualization:
  • Open Graph Vizulization platform Gephi
  • yEd Graph Editor yEd

SNA 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

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