2019/2020

Social Network Analysis

Type: Mago-Lego

Delivered by: School of Data Analysis and Artificial Intelligence

When: 4 module

Instructors: Ilia Karpov, Leonid E Zhukov

Language: English

ECTS credits: 3

Contact hours: 32

Course Syllabus

Abstract

The course presents mathematical methods and computational tools for Social Network Analysis (SNA). SNA was pioneered by sociologist, but recently became an interdisciplinary endeavor with contributions from mathematicians, computer scientists, physicists, economists etc., who brought in many new tools and techniques for network analysis. In this course we will start with basic statistical descriptions of networks, analyze network structure, roles and positions of nodes in networks, connectivity patterns and methods for community detection. In the second part of the course we will discuss processes on networks and practical methods of network visualization. We conclude the course with examples from social media mining and Facebook, Vkontakte and Twitter analysis.

Learning Objectives

• Providing students with essential knowledge of network analysis applicable to real world data, with examples from today’s most popular social networks.

Expected Learning Outcomes

• Students know basic notation and terminology used in network science.
• Students understand basic principles behind network analysis algorithms.
• Students develop practical skills of network analysis in R programming language.
• Students visualize, summarize and compare networks.
• Students analyze real work networks.

Course Contents

• Introduction to network science
  Introduction to network science. Examples.
• Descriptive network analysis
  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.
• Mathematical models of networks
  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.
• Node centralitiy and ranking on network
  Node centrality metrics, degree centrality, closeness centrality, betweenness centrality, eigenvector centrality. Katz status index and Bonacich centrality, alpha centrality PageRank,Hubs and Authorites.
• Network communities
  Cohesive subgroups. Graph cliques. Network communities. Graph partitioning. Modularity. Edge Betweenness. Spectral partitioning. Modularity maximization. Heuristic methods. Label propagation. Fast community unfolding. Walktrap.
• Epidemics and information spreading in networks
  Epidemic models on networks. SI, SIS, SIR models. Rumor spreading. Propagation trees.
• Diffusion of innovation
  Diffusion of innovation. Linear threshold model. Influence maximization.
• Spatial models of segregation
  Schelling's segregation model. Spatial segregation. Agent based modelling. Segregation in networks.

Assessment Elements

• Homework 1
• Homework 2
• Homework 3
• Homework 4
• Exam
  Экзамен проводится письменно путем отправки тестов на электронную почту студентов за 15 минут до начала экзамена.

Interim Assessment

• Interim assessment (4 module)
  0.4 * Exam + 0.15 * Homework 1 + 0.15 * Homework 2 + 0.15 * Homework 3 + 0.15 * Homework 4

Bibliography

Recommended Core Bibliography

• Easley, D. et al. Networks, crowds, and markets. – Cambridge : Cambridge university press, 2010. – 744 pp.
• Kolaczyk E. D., Csárdi G. Statistical analysis of network data with R. – New York : Springer, 2014. – 207 pp.

Recommended Additional Bibliography

• Barabási A. L., Frangos J. Linked: the new science of networks science of networks. – Basic Books, 2002. – 211 pp.
• Zuur, A., Ieno, E. N., Meesters E. A Beginner's Guide to R. – Springer Science & Business Media, 2009. – 240 pp.