• Home
• Lectures
• Reading material
• Textbooks
• Software

Network Science

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

Winter - Spring 2022.

Instructors: Prof. Leonid Zhukov, Ilya Makarov

Course topics

1. Statistical properties and modeling of networks
2. Network structure and dynamics
3. Processes on networks
4. Predictions on networks (ML)
5. Network embeddings (DL)
6. Graph neural networks (DL)

Seminars/Labs

• Github Network Science course

Youtube channel with lectures 2021

Module 3

Lectures

1. [10.01.2022] Introduction to network science. [Lecture 1]
   Introduction to the complex network theory. Network properties and metrics.
2. [17.01.2022] Power law and scale-free networks. [Lecture 2]
   Power law distribution. Scale-free networks.Pareto distribution, normalization, moments. Zipf law. Rank-frequency plot.
3. [24.01.2022] Random graphs. [Lecture 3]
   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. [31.01.2022] Network models [Lecture 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. [07.02.2022] Node centrality and ranking on networks. [Lecture 5]
   Node centrality metrics, degree centrality, closeness centrality, betweenness centrality, eigenvector centrality. Katz status index. Directed graphs. PageRank, Perron-Frobenius theorem and algorithm convergence. Power iterations. Hubs and Authorites. HITS algorithm.
6. [14.02.2022] Structural properties of networks. [Lecture 6 ]
   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. Cohesive subgroups. Graph cliques. k-cores decomposition.
7. [21.02.2022] Graph partitioning. [Lecture 7]
   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
8. [28.02.2022] Network communities. [Lecture 8]
   Network communities. Edge Betweenness. Newman-Girvin algorithm. Community detection algorithms. Overlapping communities. Clique percolation method. Heuristic methods. Fast community unfolding. Random walk based methods. Walktrap.
9. [14.03.2022] Mathematical modeling of epidemics [Lecture 9]
   Compartamental epidemic models: SI, SIS, SIR. Limiting cases. Basic reproduction number.
10. [21.03.2022] Epidemics on networks [Lecture 10]
    Spread of epidemics on network. SI, SIS, SIR network models. Epidemic threshold. Simulations of infection propagation on networks

Module 4

Lectures

1. [04.04.2022] Cascades in networks and influence maximization [Lecture 11]
   Cascades in netwroks. Difusion of innovatinon. Independent cascade model. Linear threshold model. Influence maximization. Submodular functions. Finding most influential nodes in networks.
2. [11.04.2020] Machine learning on graphs. Node classification [Lecture 12]
   Node labeling. Label propagation. Iterative classification. Semi-supervised learning. Regularization on graphs
3. [18.04.2020] Link prediction [Lecture 13]
   Link prediction problem. Proximity measures. Scoring algorithms. Prediction by supervised learning. Performance evaluation.

Additional reading material

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

Lecture 2:
• 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
• M. Mitzenmacher. A brief history of generative models for power law and lognormal distributions. Internet Mathematics, vol 1, No. 2, pp. 226-251, 2004.
• M.L. Goldstein, S.A. Morris, and G.G. Yen. Problems with fitting to the power-law distribution , Eur. Phys. J. B 41, pp 255–258, 2004.
• Chapter 18. Power Laws and Rich-Get-Richer Phenomena. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

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.
• Chapter 12. Random graphs. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 4:
• 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 20. The Small-World Phenomenon. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

Lecture 5:
• 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.
• Leo Katz A new status index derived from sociometric analysis . Psychometrika, 19, 39-43, 1953.
• Phillip Bonacich, Paulette Lloyd, Eigenvector-like measures of centrality for asymmetric relations . Social Networks 23, 191–201, 2001
• Chapter 7. Measures and metrics. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
• Chapter 5. Centrality and Prestige. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994

Lecture 6:
• 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.
• Andrei Broder et all. Graph structure in the Web. Procs of the 9th international World Wide Web conference, 2000
• Amy N. Langville and Carl D. Meyer, A Survey of Eigenvector Methods of Web Information Retrieval. 2004
• David F. Gleich. PageRank beyond the Web arXiv:1407.5107, 2014
• 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".

Lecture 7:
• S. Borgatti, M. Everett. The class of all regular equivalences: algebraic structure and computations. Social Networks, v 11, p65-68, 1989
• E. A. Leicht, P.Holme, and M. E. J. Newman. Vertex similarity in networks. Phys. Rev. E 73, 026120, 200
• G. Jeh and J. Widom. SimRank: A Measure of Structural-Context Similarity. Proceedings of the eighth ACM SIGKDD , p 538-543. ACM Press, 2002
• M. McPherson, L. Smith-Lovin, and J. Cook. Birds of a Feather: Homophily in Social Networks, Annu. Rev. Sociol, 27:415-44, 2001.
• M. Newman. Mixing patterns in networks. Phys. Rev. E, Vol. 67, p 026126, 2003
• M. D. Conover, J. Ratkiewicz, et al. Political Polarization on Twitter. Fifth International AAAI Conference on Weblogs and Social Media, 2011
• N. Christakis and J. Fowler. The spread of obesity in a large social network over 32 years. Engl J Med v 357:370-379, 2007
• Chapter 9. Structural Equivalence. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
• Chapter 12. Network Positions and Roles. S. Wasserman and K. Faust. "Social Network Analysis. Methods and Applications". Cambridge University Press, 1994
• Chapter 7. Measures and metrics. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 8:
• 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
• V. Batagelj, M. Zaversnik. An O(m) Algorithms for Cores Decomposition of Networks. 2003
• M.E.J. Newman. Modularity and community structure in networks. PNAS Vol. 103, N 23, pp 8577-8582, 2006
• Chapter 7. Matrix algorithms and graph partitioning. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 9:
• H.W. Hethcote. The Mathematics of Infections Diseases. SIAM Review, Vol. 42, No. 4, pp. 599-653, 2000
• Chapter 21. Epidemics. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

Lecture 10:
• Chapter 17. Epidemics on networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
• 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
• M. Kuperman and G. Abramson Small World Effect in an Epidemiological Model., Phys. Rev. Lett., Vol 86, No 13, pp 2909-2912, 2001
• Manitz J, Kneib T, Schlather M, Helbing D, Brockmann D. Origin Detection During Food-borne Disease Outbreaks - A Case Study of the 2011 EHEC/HUS Outbreak in Germany. PLoS Currents. 2014

Textbooks

Books

• "Network Science", Albert-Laszlo Barabasi, Cambridge University Press, 2016
• "Networks: An Introduction", Mark Newman. Oxford University Press, 2010.
• "Social and Economic Networks", Matthew O. Jackson. Princeton University Press, 2010.
• "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

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
• S. N. Dorogovtsev and J. F. F. Mendes. Evolution of Networks. Adv. Phys. Vol. 51, N 4, p 1079-1187

Paper collections

• "The Structure and Dynamics of Networks". Eds.M. Newman, A.-L. Barabasi, D. Watts. Princeton University Press, 2006.
• "Network Analysis". Eds. Ulrik Brandes, Thomas Erlebach. Lecture Notes in Computer Science. Springer, 2005
• "Social Network Data Analysis. Ed. Charu C. Aggarwal. Springer, 2011

Software

• Computations: Python and iPython, use Anaconda distribution.
• Python libraries:
  • Graph algorithms and visualizaton: NetworkX
• Visualization:
  • Open Graph Vizulization platform Gephi
  • yEd Graph Editor yEd