Structural Analysis and Visualization of Networks

Department of Data Analysis and Artificial Intelligence, School of Computer Science
National Research University Higher School of Economics

Winter-Spring 2015.

Instructor: Prof. Leonid Zhukov
Teaching assistant: Andrey Shestakov

Course Outline

  1. Introduction to network science
  2. Power laws
  3. Models of network formation
  4. Structure, nodes and links analysis
  5. Network communities
  6. Evolving networks and link prediction
  7. Diffusion and random walks
  8. Epidemics on networks
  9. Diffusion of information
  10. Influence propagation

Module 3


  1. [15.01.2015] Introduction to network science. [Lecture 1] [Video]
    Introduction to the complex network theory. Network properties and metrics.
  2. [20.01.2015] Power laws. [Lecture 2] [Video]
    Power law distribution. Scale-free networks.Pareto distribution, noramlization, moments. Zipf law. Rank-frequency plot.
  3. [27.01.2015] Random graphs. [Lecture 3] [Video]
    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.2015] Small world and dynamical growth models. [Lecture 4] [Video]
    Barabasi-Albert model. Preferential attachement. 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. Clustering coefficient and ave path lenght.
  5. [10.02.2015] Centrality measures. [Lecture 5] [Video]
    Node centrality metrics, degree centrality, closeness centrality, betweenness centrality, eigenvector centrality. Katz status index and Bonacich centrality, alpha centrality Spearman rho and Kendall-Tau ranking distance.
  6. [17.02.2015] Link analysis. [Lecture 6 ] [Video]
    Directed graphs. PageRank, Perron-Frobenius theorem and algorithm convergence. Power iterations. Hubs and Authorites. HITS algorithm.
  7. [24.02.2015] Structural equivalence. [Lecture 7] [Video]
    Structural and regular equivalence. Similarity metrics. Correlation coefficient and cosine similarity. Assortative mixing and homophily. Modularity. Assortativity coefficient. Mixing by node degree. Assortative and disassortative networks.
  8. [03.03.2015] Network communitites. [Lecture 8] [Video]
    Cohesive subgroups. Graph cliques, k-plexes, k-cores. Network communities. Vertex similarity matrix. Similarity based clustering. Agglomerative clustering. Graph partitioning. Repeated bisection. Edge Betweenness. Newman-Girvin algorithm.
  9. [10.03.2015] Graph partitioning algorithms. [Lecture 9] [Video]
    Graph density. Graph pertitioning. Min cut, ratio cut, normalized and quotient cuts metrics. Spectral graph partitioning (normalized cut). Direct (spectral) modularity maximization. Multilevel recursive partitioning
  10. [17.03.2015] Community detection. [Lecture 10] [Video]
    Community detection algorithms. Overlapping communities. Clique percolation method. Heuristic methods. Label propagation. Fast community unfolding. Random walk based methods. Walktrap. Nibble.
  11. [24.03.2015] Student midterm exam presentations. [Video]


   iPython notebooks:
  1. Introduction to iPython enviroment and NetworkX. Lab 1
  2. Power laws. Lab 2
  3. Random graphs. Lab 3
  4. Small world models. Lab 4
  5. Node centralities. Lab 5
  6. PageRank and HITS. Lab 6
  7. Structural similarity. Lab 7
  8. Dense Subgroups in Networks, Communities and Motif counting. Lab 8
  9. Community detection algorithms. Lab 9
  10. Community detection algorithms, part 2. Lab 10


  1. [20.01.2015, due: 28.01.2015]. Power laws. Homework 1
  2. [10.02.2015, due: 18.02.2015]. Network models. Homework 2
  3. [27.02.2015, due: 09.03.2015]. Centralities and assortativitiy coefficients. Homework 3
  4. [11.03.2015, due: 19.03.2015]. Community Detection Algorithms. Homework 4
  5. [17.03.2015, due: 24.03.2015]. FB or VK personal graph analysis. Midterm exam presentation.

Module 4


  1. [31.03.2015] Diffusion on networks [Lecture 11] [Video]
    Random walks on graph. Stationary distribution. Physical diffusion. Diffusion equation. Diffusion on networks. Discrete Laplace operator, Laplace matrix. Solution of the diffusion equation. Normalized Laplacian.
  2. [07.04.2015] Epidemics [Lecture 12] [Video]
    Epidemic models: SI, SIS, SIR. Limiting cases. Basic reproduction number. Branching Galton-Watson process. Probability of epidemics.
  3. [14.04.2015] Epidemics on networks [Lecture 13] [Video] .
    Spread of epidemics on network. SI, SIS, SIR models. Epidemic threshold. Simulations of infection propagation.
  4. [21.04.2015] Social contagion and spread of information [Lecture 14] [Video]
    Information diffusion. Rumor spreading models. Homogenous and mean field models. Examples. Cascades and information propagation trees.
  5. [28.04.2015] Diffusion of innovation and influence maximization [Lecture 15] [Video]
    Diffusion of innovation. Independent cascade model. Linear threshold model. Influence maximization. Submodular functions. Finding most influential nodes in networks.
  6. [12.05.2015] Social learning [Lecture 16] [Video]
    Social learning in networks. DeGroot model. Reaching consensus. Influence vector. Social influence networks
  7. [19.05.2015] Label propagation on graph [Lecture 17] [Video1] [Video2]
    Node labeling. Label propagation. Iterative classification. Semi-supervised learning. Regularization on graphs
  8. [26.05.2015] Link prediction [Lecture 18] [Video]
    Link prediction problem. Proximity measures. Scoring algorithms. Prediction by supervised learning. Performance evaluation.
  9. [02.06.2015] Spatial segregation [Lecture 19] [Video]
    Schelling's segregation model. Spatial segregation. Agent based modelling. Segregation in networks
  10. [09.06.2015] Strategic network formation [Lecture 20]
    Economic models of networks. Course summary.
  11. [25.06.2015] Экзамен / Exam


   iPython notebooks:
  1. Random walk modeling. Lab 1
  2. Epidemics Lab 2
  3. Epidemics on networks. Lab 3
  4. Threshold models. Lab 4
  5. Social learning. Lab 5
  6. Node label and link prediction. Lab 6
  7. Segregation models. Lab 7


  1. Information and influence propagation in networks. Course Project 1
  2. Link prediction. Course Project 2

Reading material






Similar courses