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
- Introduction to network science
- Power laws and scale-free networks
- Models of network formation
- Structure, nodes and links analysis
- Network communities
- Evolving networks and link prediction
- Epidemics on networks
- Diffusion of information
- Influence propagation
Seminars/Labs
Module 3
Lectures
- [17.01.2020] Introduction to network science. [Lecture 1] [ Video 1-2]
Introduction to the complex network theory. Network properties and metrics.
- [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.
- [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
- [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.
- [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.
- [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.
- [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.
- [06.03.2020] Network structure. [Lecture 8] [ Video 7-8]
Cohesive subgroups. Graph cliques. k-cores decomposition. Network communities. Edge Betweenness. Newman-Girvin algorithm.
- [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.
- [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
- [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
- [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.
- [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.
- [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.
- [16.05.2020] Machine learning on graphs. Node classification [Lecture 15] [Video]
Node labeling. Label propagation. Iterative classification. Semi-supervised learning. Regularization on graphs
- [23.05.2020] Link prediction [Lecture 16][Video]
Link prediction problem. Proximity measures. Scoring algorithms.
Prediction by supervised learning. Performance evaluation.
- [30.05.2020] Spatial
segregation [Lecture 17] [ Video]
Schelling's segregation model. Spatial segregation. Agent based modelling. Segregation in networks
- [??.06.2020] 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:
- 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
Lecture 11:
-
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 12:
- 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 13:
-
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 14:
- Mark S. Granovetter.
Threshold Models of Collective Behavior. American Journal of Sociology Vol. 83, No. 6, pp. 1420-1443, 1978.
-
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.
-
M. Richardson, P. Domingos. Mining Knowledge-Sharing Sites for Viral
Marketing. In Proc. KDD, 2002.
-
M. Richardson, P. Domingos. Mining the Network Value of Customers. In Proc. KDD, 2001.
-
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:
- 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
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