• 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 2016.

Instructor: Prof. Leonid Zhukov, Ilya Makarov
Teaching assistant:

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

Lectures

1. [19.01.2016] Introduction to network science. [Lecture 1]
   Introduction to the complex network theory. Network properties and metrics.
2. [19.01.2016] Power laws. [Lecture 2]
   Power law distribution. Scale-free networks.Pareto distribution, noramlization, moments. Zipf law. Rank-frequency plot.
3. [30.01.2016] 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. [06.02.2016] Small world and dynamic 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. [13.02.2016] 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. [20.02.2016] Link analysis. [Lecture 6 ] [Video]
   Directed graphs. PageRank, Perron-Frobenius theorem and algorithm convergence. Power iterations. Hubs and Authorites. HITS algorithm.
7. [27.02.2016] 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. [05.03.2016] Network structure. [Lecture 8] [Video]
   Cohesive subgroups. Graph cliques. k-cores decomposition. Network communities. Edge Betweenness. Newman-Girvin algorithm.
9. [12.03.2016] Graph partitioning algorithms. [Lecture 9]
   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. [19.03.2016] Community detection. [Lecture 10] [Video]
    Community detection algorithms. Overlapping communities. Clique percolation method. Heuristic methods. Fast community unfolding. Random walk based methods. Walktrap.
11. [24.03.2015] Midterm
    

Module 4

Lectures

1. [9.04.2016] 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. [16.04.2016] Epidemics [Lecture 12] [Video]
   Epidemic models: SI, SIS, SIR. Limiting cases. Basic reproduction number. Branching Galton-Watson process. Probability of epidemics.
3. [23.04.2016] Epidemics on networks [Lecture 13] [Video] .
   Spread of epidemics on network. SI, SIS, SIR models. Epidemic threshold. Simulations of infection propagation.
4. [30.04.2016] Diffusion of innovation and influence maximization [Lecture 14] [Video]
   Diffusion of innovation. Independent cascade model. Linear threshold model. Influence maximization. Submodular functions. Finding most influential nodes in networks.
5. [14.05.2016] Label propagation on graph [Lecture 15] [Video]
   Node labeling. Label propagation. Iterative classification. Semi-supervised learning. Regularization on graphs
6. [21.05.2016] Link prediction [Lecture 16] [Video]
   Link prediction problem. Proximity measures. Scoring algorithms. Prediction by supervised learning. Performance evaluation.
7. [28.05.2016] Social learning [Lecture 17] [Video]
   Social learning in networks. DeGroot model. Reaching consensus. Influence vector. Social influence networks
8. [07.06.2016] Spatial segregation [Lecture 18]
   Schelling's segregation model. Spatial segregation. Agent based modelling. Segregation in networks
9. [???.06.2016] Экзамен / Exam

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:
• M. Fiedler. Algebraic connectivity of graphs, Czech. Math. J, 23, pp 298-305, 1973
• A. Pothen, H. Simon and K. Liou. Partitioning sparse matrices with eigenvectors of graphs, SIAM Journal of Matrix Analysis, 11, pp 430-452, 1990
• Bruce Hendrickson and Robert Leland. A Multilevel Algorithm for Partitioning Graphs, Sandia National Laboratories, 199
• Jianbo Shi and Jitendra Malik. Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, N 8, pp 888-905, 2000
• M.E.J. Newman. Finding community structure in networks using eigenvectors of matrices, ArXiv:physics/06050873v3, July 23, 2006.
• M.E.J. Newman, M. Girvan. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113, 2004.
• B. Good, Y.-A. de Montjoye, A. Clauset. Performance of modularity maximization in practical contexts, Physical Review E 81, 046106, 2010
• Chapter 11. Matrix algorithms and graph partitioning. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 10:
• 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.
• U.N. Raghavan, R. Albert, S. Kumara, Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E 76 (3), 036106, 2007.
• 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.
• Daniel A. Spielman, Shang-Hua Teng. A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning. SIAM Journal on computing, Vol. 42, p. 1-26, 2013
• R. Andersen, F. Chung, K. Lang. Local graph partitioning using pagerank vectors. In Proc. FOCS, 2006.
• J. Leskovec, K.J. Lang, A. Dasgupta, and M.W. Mahoney. Statistical properties of community structure in large social and information networks. In WWW 08: Procs. of the 17th Int. Conf. on World Wide Web, pages 695-704, 2008.

Lecture 11:
• Lovasz, L. Random walks on graphs: a survey. In Combinatorics, Paul Erdos is eighty. pp. 353 – 397. Budapest: Janos Bolyai Math. Soc., 1993
• Chung, Fan R.K. Spectral graph theory. Chapter 1. Providence, RI: American Math. Soc., 1997
• Daniel A. Spielman. Spectral Graph theory. Combinatorial Scientific Computing. Chapman and Hall/CRC Press. 2011
• Chapter 6. Mathematics of networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 12:
• H.W. Hethcote. The Mathematics of Infections Diseases. SIAM Review, Vol. 42, No. 4, pp. 599-653, 2000
• Chapter 17. Epidemics on networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.

Lecture 13:
• 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
• Chapter 17. Epidemics on networks. Mark Newman. "Networks: An Introduction". Oxford University Press, 2010.
• Chapter 21. Epidemics. D. Easley and J. Kleinberg. "Networks, Crowds, and Markets: Reasoning About a Highly Connected World".

Lecture 14:
• 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)
• 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.
• D. Kempe, J. Kleinberg, E. Tardos. Influential Nodes in a Diffusion Model for Social Networks. Lecture Notes in Computer Science, Eds C. Luis, I.Giuseppe et.al, 2005
• S. Morris. Contagion. Review of Economic Studies 67, 57-78, 2000.
• L.Backstrom, D. Huttenlocher, J. Kleinbrg, X. Lan, Group Formation in Large Social Networks: Membership, Growth and Evolution, In Proc. KDD 2006.
• 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".

Lecture 15:
• S. A. Macskassy, F. Provost. Classification in Networked Data: A Toolkit and a Univariate Case Study. Journal of Machine Learning Research 8, 935-983, 2007
• Bengio Yoshua, Delalleau Olivier, Roux Nicolas Le. Label Propagation and Quadratic Criterion. Chapter in Semi-Supervised Learning, Eds. O. Chapelle, B. Scholkopf, and A. Zien, MIT Press 2006
• Smriti Bhagat, Graham Cormode, S. Muthukrishnan. Node classification in social networks. Chapter in Social Network Data Analytics, Eds. C. Aggrawal, 2011, pp 115-148
D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Scholkopf. Learning with local and global consistency. In NIPS, volume 16, 2004.
• X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In ICML, 2003.
• M. Belkin, P. Niyogi, V. Sindhwani. Manifold regularization: A geometric framework for learning from labeled and unlabeled examples. J. Mach. Learn. Res., 7, 2399-2434, 2006

Lecture 16:
• D. Liben-Nowell and J. Kleinberg. The link prediction problem for social networks. Journal of the American Society for Information Science and Technology, 58(7):1019–1031, 2007
• R. Lichtenwalter, J.Lussier, and N. Chawla. New perspectives and methods in link prediction. KDD 10: Proceedings of the 16th ACM SIGKDD, 2010
• M. Al Hasan, V. Chaoji, S. Salem, M. Zaki, Link prediction using supervised learning. Proceedings of SDM workshop on link analysis, 2006
• M. Rattigan, D. Jensen. The case for anomalous link discovery. ACM SIGKDD Explorations Newsletter. v 7, n 2, pp 41-47, 2005
• Y. Yang, R. Lichtenwalter, N. Chawla, Evaluating Link Prediction Methods, Knowledge and Information Systems, V 45, n 3, pp75-782, 2015
• M. Al. Hasan, M. Zaki. Link prediction in social networks. In Social Networks Data Analytics, Eds C. Aggarwal, 2011.

Lecture 17:
• M.H. DeGroot. Reaching a Consensus. Journal of the American Statistical Association, 1974, Vol 69, No 345
• Roger L. Berger. A Necessary and Sufficient Condition for Reaching a Consensus Using DeGroot's Method. Journal of the American Statistical Association, Vol. 76, No 374, 1981, pp 415-418
• Noah Friedkin, and Eugene C. Johnsen, Social Influence Networks and Opinion Change Advances in Group Processes 16:1-29, 1999
• B. Golub and M. Jackson Naive Learning in Social Networks and the Wisdom of Crowds, Amer. Econ. J. Microeconomics, 2:1, pp 112-149, 2010
• Chapter 8. Learning and Networks. Matthew O. Jackson. "Social and Economic Networks".

Lecture 18:
• Thomas C. Schelling Dynamic Models of Segregation , Journal of Mathematical Sociology, Vol. 1, pp 143-186, 1971.
• Arnaud Banos Network effects in Schellin's model of segregation: new evidences from agent-based simulations. Environment and Planning B: Planning and Design Vol.39, no. 2, pp. 393-405, 2012.
• Giorgio Gagiolo, Marco Valente, Nicolaas Vriend Segregation in netwroks. Journal of Econ. Behav. & Organization, Vol. 64, pp 316-336, 2007.

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

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
• Python libraries:
  • Numerical algorithms: Numpy, SciPy
  • Graph algorithms and visualizaton: NetworkX
• Visualization:
  • Open Graph Vizulization platform Gephi
  • yEd Graph Editor yEd
  • Graph Visualization Software GraphViz

Similar courses

• 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