Network Science

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

Winter - Spring 2020.

Instructors: Prof. Leonid Zhukov, Ilya Makarov

Course Outline

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

Seminars/Labs

Youtube channel with lectures

Module 3

Lectures

  1. [17.01.2020] Introduction to network science. [Lecture 1] [ Video 1-2]
    Introduction to the complex network theory. Network properties and metrics.
  2. [24.01.2020] Power law and scale-free networks. [Lecture 2] [ Video 1-2]
    Power law distribution. Scale-free networks.Pareto distribution, normalization, moments. Zipf law. Rank-frequency plot.
  3. [31.01.2020] Random graphs. [Lecture 3][ Video 3-4]
    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. [07.02.2020] Small world and dynamic growth models. [Lecture 4] [ Video 3-4]
    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. [14.02.2020] Centrality measures. [Lecture 5] [Video 5-6]
    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. [21.02.2020] Link analysis. [Lecture 6 ] [Video 5-6]
    Directed graphs. PageRank, Perron-Frobenius theorem and algorithm convergence. Power iterations. Hubs and Authorites. HITS algorithm.
  7. [28.02.2020] Structural properties of networks. [Lecture 7] [ Video 7-8]
    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. [06.03.2020] Network structure. [Lecture 8] [ Video 7-8]
    Cohesive subgroups. Graph cliques. k-cores decomposition. Network communities. Edge Betweenness. Newman-Girvin algorithm.
  9. [13.03.2020] Epidemics [Lecture 9] [ Video 9]
    Compartamental epidemic models: SI, SIS, SIR. Limiting cases. Basic reproduction number. Branching Galton-Watson process. Probability of epidemics.
  10. [20.03.2020] Epidemics on networks [Lecture 10] [ Video 10]
    Spread of epidemics on network. SI, SIS, SIR network models. Epidemic threshold. Simulations of infection propagation on networks

Module 4

Lectures

  1. [11.04.2020] Graph partitioning algorithms. [Lecture 11] [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
  2. [18.04.2020] Diffusion on networks [Lecture 12] [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.
  3. [25.04.2020] Community detection. [Lecture 13] [Video]
    Community detection algorithms. Overlapping communities. Clique percolation method. Heuristic methods. Fast community unfolding. Random walk based methods. Walktrap.
  4. [07.05.2020] Cascades in networks and influence maximization [Lecture 14] [Video]
    Cascades in netwroks. Difusion of innovatinon. Independent cascade model. Linear threshold model. Influence maximization. Submodular functions. Finding most influential nodes in networks.
  5. [16.05.2020] Machine learning on graphs. Node classification [Lecture 15] [Video]
    Node labeling. Label propagation. Iterative classification. Semi-supervised learning. Regularization on graphs
  6. [23.05.2020] Link prediction [Lecture 16][Video]
    Link prediction problem. Proximity measures. Scoring algorithms. Prediction by supervised learning. Performance evaluation.
  7. [30.05.2020] Spatial segregation [Lecture 17] [ Video]
    Schelling's segregation model. Spatial segregation. Agent based modelling. Segregation in networks
  8. [??.06.2020] Exam

Reading material

Textbooks

Books

Reviews

Paper collections

Software