Курс: ANTS: Advanced Topics in Network Science

Общее

Свернуть всё Развернуть всё

Advanced Topics in Network Science (ANTS)

Course lecturers

Lovro Šubelj (R 2.49) & Jure Leskovec (Stanford)

Outline & objective

Networks or graphs are ubiquitous in everyday life. Examples include online social networks, the Web, wiring of a neural system, references between WikiLeaks cables, Supervizor, terrorist affiliations, plumbing systems and your brain. Many such real networks reveal characteristic patterns of connectedness that are far from regular or random. Networks have thus been a prominent tool for investigating real-world systems since the 18th century. However, while small networks can be drawn by hand and analyzed by a naked eye, real networks require specialized computer algorithms, techniques and models. This led to the emergence of a new scientific field about 20 years ago denoted network science.

The course will first introduce the language of networks and review fundamental concepts and techniques for the analysis of large real networks. In the main part of the course, the students will learn about selected advanced topics in network science with special emphasis on the practical applicability of the presented approaches. The topics will include node metrics, clusters and patterns, large-scale network structure, network sampling, comparison, modeling, mining, inference, visualization and dynamics.

The lectures will give a broad theoretical background that will suffice for a proper comprehension of the topics covered, whereas the main part of the lectures will be devoted to their practical applications found in the literature. The objective of the course is not to give a comprehensive theoretical discussion or in-depth review on any of the topics, but to present a rich set of network science tools that students could use in their own PhD work. The latter will be the main part of the coursework.

Except for a clearly identified PhD topic, there are no specific prerequisites for the course. However, the students will benefit from a solid knowledge in graph theory, probability theory, statistics and linear algebra, good programming skills in a language of their choice (e.g. C/C++, Python, Java), and familiarity with research work and scientific writing.

Literature & readings

The course notes, handouts, videos, readings and other materials will be posted periodically on this web page. The course literature will be given in English in the form of lecture handouts with references to relevant scientific papers. The students are expected to search for additional literature on their own. Chapters from the following course books will be recommended as background reading.

Barabási, A.-L., Network Science (Cambridge University Press, 2016).

Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).

Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).

de Nooy, W., Mrvar, A. & Batagelj, V., Exploratory Social Network Analysis (Cambridge University Press, 2011).

Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).

Course assignments

Course assignments will be adjusted to individual students on a case-by-case basis.
Course syllabus
Tentative course syllabus Гиперссылка
Course discussions
Course announcements Форум

From graph theory to network science

Выделено

From classical graph theory to social network analysis and modern network science. Graphology and networkology.

Lectures materials:

Networks introduction and motivation (slides)
Graph theory and network science (slides)
Graphology and networkology (slides)
Networks in modern science (slides)
Network science journals (handout)
Network science events (handout)

Book chapters:

Ch. 1: Introduction & Ch. 2: Graph theory in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Ch. 1-5: Introduction etc. & Ch. 6: Mathematics of networks in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Ch. 1: Overview & Ch. 2: Graphs in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).

Course readings:

Barabási, A.-L., The network takeover , Nat. Phys. 8(1), 14-16 (2012).
Newman, M.E.J., The physics of networks, Phys. Today 61(11), 33-38 (2008).
Barabási, A.-L. & Bonabeau, E., Scale-free networks, Sci. Am. 288(5), 50-59 (2003).
Broder, A., Kumar, R. et al., Graph structure in the Web, Comput. Netw. 33(1-6), 309-320 (2000).
Newman, M.E.J., Communities, modules and large-scale structure in networks, Nat. Phys. 8(1), 25-31 (2012).
Vespignani, A., Modelling dynamical processes in complex socio-technical systems, Nat. Phys. 8(1), 32-39 (2012).
Motter, A.E. & Yang, Y., The unfolding and control of network cascades, Phys. Today 70(1), 33-39 (2017).
Laurienti, P.J., Joyce, K.E. et al., Universal fractal scaling of self-organized networks, Physica A 390(20), 3608-3613 (2011).
Ch. 1: Uvod in Šubelj, L., Odkrivanje skupin vozlišč v velikih realnih omrežjih, PhD thesis (University of Ljubljana, 2013).
Hidalgo, C.A., Disconnected, fragmented, or united? A trans-disciplinary review of network science, Appl. Netw. Sci. 1, 6 (2016).
Sayama, H., Mapping the curricular structure and contents of network science courses, e-print arXiv:1707.09570v2, pp. 17 (2017).
Cramer, C., Porter, M.A., at al., Network Literacy: Essential Concepts and Core Ideas (Creative Commons Licence, 2015).

Large-scale structure and models

Random graphs and real networks. Degrees of separation in small-world networks, power-law distributions of scale-free networks and mixing in networks.

Lectures materials:

Random graph models (slides)
Configuration graph model (slides)
Exponential random graph model (slides)
Small-world networks and models (slides)
Scale-free networks and models (slides)
Node mixing in networks (slides)

Book chapters:

Ch. 3: Random networks, Ch. 4-5: Scale-free model etc. & Ch. 7: Correlation etc. in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Ch. 8: Large-scale structure etc. & Ch. 12-15: Network models in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Ch. 11: Random Models etc. & Ch. 17: Global properties etc. in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).
Ch. 18: Power laws etc. & Ch. 20: Small-world etc. in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).

Course readings:

Erdős, P. & Rényi, A., On random graphs I, Publ. Math. Debrecen 6, 290-297 (1959).
Newman, M.E.J., Watts, D.J. & Strogatz, S.H., Random graph models of social networks, P. Natl. Acad. Sci. USA 99, 2566-2572 (2002).
Newman, M.E.J., Strogatz, S.H. & Watts, D.J., Random graphs with arbitrary degree distributions and their applications, Phys. Rev. E 64(2), 026118 (2001).
Milo, R., Kashtan, N. et al., On the uniform generation of random graphs with prescribed degree sequences, e-print arXiv:0312028v2, pp. 4 (2004).
Carstens, C.J. & Horadam, K.J., Switching edges to randomize networks, J. Complex Netw. 5(3), 337-351 (2017).
Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079-1187 (2002).

Milgram, S., The small world problem, Psychol. Today 1(1), 60-67 (1967).
Watts, D.J. & Strogatz, S.H., Collective dynamics of 'small-world' networks, Nature 393(6684), 440-442 (1998).
Dodds, P.S., Muhamad, R. & Watts, D.J., An experimental study of search in global social networks, Science 301(5634), 827-829 (2003).
Liben-Nowell, D., Novak, J. et al., Geographic routing in social networks, P. Natl. Acad. Sci. USA 102(33), 11623-11628 (2005).
Backstrom, L., Boldi, P. et al., Four degrees of separation, In: Proceedings of WebSci '12 (Evanston, IL, USA, 2012), pp. 45-54.
Ugander, J., Karrer, B. et al., The anatomy of the Facebook social graph, e-print arXiv:1111.4503v1, pp. 17 (2011).

de Solla Price, D.J., Networks of scientific papers, Science 149, 510-515 (1965).
Barabási, A.-L. & Albert, R., Emergence of scaling in random networks, Science 286(5439), 509-512 (1999).
Clauset, A., Shalizi, C.R. & Newman, M.E.J., Power-law distributions in empirical data, SIAM Rev. 51, 661-703 (2009).
Faloutsos, M., Faloutsos, P. & Faloutsos, C., On power-law relationships of the Internet topology, Comput. Commun. Rev. 29(4), 251-262 (1999).
Golosovsky, M., Preferential attachment mechanism of complex network growth, e-print arXiv:1802.09786v1, pp. 12 (2018).
Albert, R., Jeong, H. & Barabási, A.-L., Error and attack tolerance of complex networks, Nature 406(6794), 378-382 (2000).
Albert, R., Jeong, H. & Barabási, A.-L., Diameter of the World Wide Web, Nature 401, 130-131 (1999).
Broido, A.D. & Clauset, A., Scale-free networks are rare, e-print arXiv:1801.03400v1, pp. 14 (2018).
Barabási, A.-L., Love is all you need, reply to e-print arXiv:1801.03400v1, pp. 6 (2018).

Newman, M.E.J., Mixing patterns in networks, Phys. Rev. E 67(2), 026126 (2003).
Newman, M.E.J., Assortative mixing in networks, Phys. Rev. Lett. 89(20), 208701 (2002).
Newman, M.E.J. & Park, J., Why social networks are different from other types of networks, Phys. Rev. E 68(3), 036122 (2003).
Pastor-Satorras, R., Vázquez, A. & Vespignani, A., Dynamical and correlation properties of the Internet, Phys. Rev. Lett. 87(25), 258701 (2001).
Vázquez, A., Pastor-Satorras, R. & Vespignani, A., Large-scale topological and dynamical properties of the Internet, Phys. Rev. E 65(6), 066130 (2002).
Xulvi-Brunet, R. & Sokolov, I.M., Changing correlations in networks: Assortativity and dissortativity, Acta Phys. Pol. B 36, 1431-1455 (2005).
Park, J. & Barabási, A.-L., Distribution of node characteristics in complex networks, P. Natl. Acad. Sci. USA 104(46), 17916-17920 (2007).
Foster, J.G., Foster, D.V. et al., Edge direction and the structure of networks, P. Natl. Acad. Sci. USA 107(24), 10815-10820 (2010).
Estrada, E., Combinatorial study of degree assortativity in networks, Phys. Rev. E 84(4), 047101 (2011).

Mesoscopic structure and fragments

Network community and core-periphery structure. Graph partitioning, blockmodeling and community detection. Network motifs, graphlets and node orbits.

Lectures materials:

Weak ties and network community structure (slides)
Graph partitioning and community detection (slides)
Blockmodeling and stochastic block models (slides)
Network motifs, graphlets and node orbits (slides)

Book chapters:

Ch. 9: Communities in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Ch. 7.12-13: Similarity etc. & Ch. 11: Graph partitioning in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Ch. 21: Fragments etc. & Ch. 21: Communities etc. in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).
Ch. 3: Strong and weak ties in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).

Course readings:

Granovetter, M.S., The strength of weak ties, Am. J. Sociol. 78(6), 1360-1380 (1973).
Girvan, M. & Newman, M.E.J., Community structure in social and biological networks, P. Natl. Acad. Sci. USA 99(12), 7821-7826 (2002).
Ravasz, E., Somera, A.L. et al., Hierarchical organization of modularity in metabolic networks, Science 297(5586), 1551-1555 (2002).
Newman, M.E.J. & Girvan, M., Mixing patterns and community structure in networks, Phys. Rev. E 67(2), 026126 (2003).
Fortunato, S. & Barthelemy, M., Resolution limit in community detection, P. Natl. Acad. Sci. USA 104(1), 36-41 (2007).
Palla, G., Derényi, I. et al., Uncovering the overlapping community structure of complex networks in nature and society, Nature 435(7043), 814-818 (2005).
Guimera, R., Sales-Pardo, M. & Amaral, L.A.N., Classes of complex networks defined by role-to-role connectivity profiles, Nat. Phys. 3(1), 63-69 (2007).
Lancichinetti, A., Kivela, M. et al., Characterizing the community structure of complex networks, PLoS ONE 5(8), e11976 (2010).
Ahn, Y.-Y., Bagrow, J.P. & Lehmann, S., Link communities reveal multiscale complexity in networks, Nature 466(7307), 761-764 (2010).
Onnela, J.-P., Saramäki, J. et al., Structure and tie strengths in mobile communication networks, P. Natl. Acad. Sci. USA 104(18), 7332-7336 (2007).
Hric, D., Darst, R.K. & Fortunato, S., Community detection in networks: Structural communities versus ground truth, Phys. Rev. E 90(6), 062805 (2014).
Schaub, M.T., Delvenne, J.-C. et al., The many facets of community detection in complex networks, Appl. Netw. Sci. 2, 4 (2017).

Fortunato, S., Community detection in graphs, Phys. Rep. 486(3-5), 75-174 (2010).
Fortunato, S. & Hric, D., Community detection in networks: A user guide, Phys. Rep. 659, 1-44 (2016).
Xie, J., Kelley, S. & Szymanski, B.K., Overlapping community detection in networks, ACM Comput. Surv. 45(4), 43 (2013).
Lancichinetti, A. & Fortunato, S., Community detection algorithms: A comparative analysis, Phys. Rev. E 80(5), 056117 (2009).
Raghavan, U.N., Albert, R. & Kumara, S., Near linear time algorithm to detect community structures in large-scale networks, Phys. Rev. E 76(3), 036106 (2007).
Rosvall, M. & Bergstrom, C.T., Maps of random walks on complex networks reveal community structure, P. Natl. Acad. Sci. USA 105(4), 1118-1123 (2008).
Blondel, V.D., Guillaume, J.-L. et al., Fast unfolding of communities in large networks, J. Stat. Mech., P10008 (2008).
Kumpula, J.M., Kivelä, M. et al., Sequential algorithm for fast clique percolation, Phys. Rev. E 78(2), 026109 (2008).
Šubelj, L. & Bajec, M., Ubiquitousness of link-density and link-pattern communities in real-world networks, Eur. Phys. J. B 85(1), 32 (2012).
Šubelj, L., Blagus, N. & Bajec, M., Group extraction for real-world networks, In: Proceedings of NetSci '13 (Copenhagen, Denmark, 2013), pp. 2.
Zhao, Y., Levina, E. & Zhu, J., Community extraction for social networks, P. Natl. Acad. Sci. USA 108(18), 7321-7326 (2011).
Šubelj, L., Label propagation for clustering in Doreian, P., Batagelj, V. & Ferligoj, A., Advances in Network Clustering and Blockmodeling (Wiley, 2018).

Reichardt, J. & White, D.R., Role models for complex networks, Eur. Phys. J. B 60(2), 217-224 (2007).
Holland, P.W., Laskey, K.B. & Leinhardt, S., Stochastic blockmodels: First steps, Soc. Networks 5(2), 109-137 (1983).
Airoldi, E.M., Blei, D.M. et al., Mixed membership stochastic blockmodels, J. Mach. Learn. Res. 9(9), 1981-2014 (2008)
Newman, M.E.J. & Leicht, E.A., Mixture models and exploratory analysis in networks, P. Natl. Acad. Sci. USA 104(23), 9564 (2007).
Karrer, B. & Newman, M.E.J., Stochastic blockmodels and community structure in networks, Phys. Rev. E 83(1), 016107 (2011).
Peixoto, T., Model selection and hypothesis testing for large-scale network models with overlapping groups, Phys. Rev. X 5(1), 011033 (2015).
Guimera, R., Sales-Pardo, M. & Amaral, L.A.N., Classes of complex networks defined by role-to-role connectivity profiles, Nat. Phys. 3(1), 63-69 (2007).
Clauset, A., Moore, C. & Newman, M.E.J., Hierarchical structure and the prediction of missing links in networks, Nature 453(7191), 98-101 (2008).
Guimera, R. & Sales-Pardo, M., Missing and spurious interactions and the reconstruction of complex networks, P. Natl. Acad. Sci. USA 106(52), 22073-22078 (2009).
Šubelj, L. & Bajec, M., Group detection in complex networks: An algorithm and comparison of the state of the art, Physica A 397, 144-156 (2014).
Peixoto, T.P., Bayesian stochastic blockmodeling in Doreian, P., Batagelj, V. & Ferligoj, A., Advances in Network Clustering and Blockmodeling (Wiley, 2018).

Seidman, S.B., Network structure and minimum degree, Soc. Networks 5(3), 269–287 (1983).
Borgatti, S.P. & Everett, M.G., Models of core/periphery structures, Soc. Networks 21(4), 375–395 (2000).
Holme, P., Core-periphery organization of complex networks, Phys. Rev. E 72(4), 46111 (2005).
Leskovec, J., Lang, K.J. et al., Community structure in large networks, Internet Math. 6(1), 29–123 (2009).
Batagelj, V. & Zaveršnik, M., An O(m) algorithm for cores decomposition of networks, Adv. Data Anal. Classif. 5(2), 129–145 (2011).
Csermely, P., London, A. et al., Structure and dynamics of core/periphery networks, J. Complex Netw. 1(2), 93-123 (2013).
Rombach, M., Porter, M. et al., Core-periphery structure in networks, SIAM J. Appl. Math. 74(1), 167–190 (2014).
Zhang, X., Martin, T. & Newman, M.E.J., Identification of core-periphery structure in networks, Phys. Rev. E 91(3), 32803 (2015).
Jeub, L.G.S., Balachandran, P. et al., Think locally, act locally, Phys. Rev. E 91(1), 12821 (2015).
Ma, A. & Mondragón, R.J., Rich-cores in networks, PLoS ONE 10(3), e0119678 (2015).

Milo, R., Shen-Orr, S. et al., Network motifs: Simple building blocks of complex networks, Science 298(5594), 824-827 (2002).
Milo, R., Itzkovitz, S. et al., Superfamilies of evolved and designed networks, Science 303(5663), 1538-1542 (2004).
Valverde, S. & Solé, R.V., Network motifs in computational graphs: A case study in software architecture, Phys. Rev. E 72(2), 026107 (2005).
Davies, T. & Marchione, E., Event networks and the identification of crime pattern motifs, PLoS ONE 10(11), e0143638 (2015).
Benson, A.R., Gleich, D.F. & Leskovec, J., Higher-order organization of complex networks, Science 353(6295), 163-166 (2016).
Pržulj, N., Corneil, D.G. & Jurisica, I., Modeling interactome: Scale-free or geometric?, Bioinformatics 20(18), 3508-3515 (2004).
Pržulj, N., Biological network comparison using graphlet degree distribution, Bioinformatics 23(2), e177-e183 (2007).
Yaveroğlu, Ö.N., Malod-Dognin, N. et al., Revealing the hidden language of complex networks, Sci. Rep. 4, 4547 (2014).
Hočevar, T. & Demšar, J., A combinatorial approach to graphlet counting, Bioinformatics 30(4), 559-565 (2014).
Soufiani, H.A. & Airoldi, E.M., Graphlet decomposition of a weighted network, J. Mach. Learn. Res. 22, 54-63 (2012).
Sarajlić, A., Malod-Dognin, N. et al., Predictive functional connectivity of real-world systems, e-print arXiv:1603.05470v1, pp. 17 (2016).
Peel, L., Delvenne, J.-C., & Lambiotte, R., Multiscale mixing patterns in networks, P. Natl. Acad. Sci. USA 115(16), 4057-4062 (2018).
Sanchez-Garcia, R.J., Exploiting symmetry in network analysis, e-print arXiv:1803.06915v1, pp. 7 (2018).

Node position and similarity

Measures of node position and centrality, measures of link importance and bridging, and link analysis algorithms. Node similarity and equivalence.

Lectures materials:

Measures of node centrality (slides)
Node similarity and equivalence (slides)
Measures of link bridging (slides)
Link analysis algorithms (slides)

Book chapters:

Ch. 7: Measures and metrics in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Ch. 14: Link analysis and web search in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
Ch. 14: Classical node centrality & Ch. 15: Spectral etc. in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).

Course readings:

Katz, L., A new status index derived from sociometric analysis, Psychometrika 18(1), 39-43 (1953).
Freeman, L.C., A set of measures of centrality based on betweenness, Sociometry 40(1), 35-41 (1977).
Freeman, L.C., Centrality in social networks: Conceptual clarification, Soc. Networks 1(3), 215-239 (1979).
Bonacich, P., Power and centrality: A family of measures, Am. J. Sociology 92(5), 1170-1182 (1987).
Brandes, U., A faster algorithm for betweenness centrality, J. Math. Sociol. 25(2), 163-177 (2001).
Jeong, H., Mason, S.P., et al., Lethality and centrality in protein networks, Nature 411, 41-42 (2001).
Soffer, S.N. & Vázquez, A., Network clustering coefficient without degree-correlation biases, Phys. Rev. E 71(5), 057101 (2005).
Newman, M.E.J., A measure of betweenness centrality based on random walks, Soc. Networks 27(1), 39-54 (2005).
Jensen, P., Morini, M., et al., Detecting global bridges in networks, J. Complex Netw., 1-15 (2015), under review.
Everett, M.G. & Valente, T.W., Bridging, brokerage and betweenness, Soc. Networks 44, 202-208 (2016).
Franceschet, M. & Bozzo, E., A theory on power in networks, e-print arXiv:1510.08332v2, pp. 19 (2016).
Agneessens, F., Borgatti, S.P. & Everett, M.G., Geodesic based centrality, Soc. Networks 49, 12-26 (2017).
Wu, A.-K., Tian, L. & Liu, Y.-Y., Bridges in complex networks, Phys. Rev. E 97(1), 012307 (2018).

Lorrain, F. & White, H.C., Structural equivalence of individuals in social networks, J. Math. Sociol. 1(1), 49-80 (1971).
White, D.R., & Reitz, K.P., Graph and semigroup homomorphisms on networks of relations, Soc. Networks 5(2), 193-234 (1983).
Leicht, E.A., Holme, P. & Newman, M.E.J., Vertex similarity in networks, Phys. Rev. E 73(2), 026120 (2006).
Onnela, J.-P., Saramäki, J., et al., Structure and tie strengths in mobile communication networks, P. Natl. Acad. Sci. USA 104(18), 7332-7336 (2007).
Liben‐Nowell, D. & Kleinberg, J., The link‐prediction problem for social networks, J. Am. Soc. Inf. Sci. Tec. 58(7), 1019-1031 (2007).
Zhou, T., Lü, L. & Zhang, Y.-C., Predicting missing links via local information, Eur. Phys. J. B 71(4), 623-630 (2009).

Kleinberg, J., Authoritative sources in a hyperlinked environment, J. ACM 46(5), 604-632 (1999).
Brin, S. & Page, L., The anatomy of a large-scale hypertextual Web search engine, Comput. Networks ISDN 30(1-7), 107-117 (1998).
Lempel, R. & Moran, S., SALSA: The stochastic approach for link-structure analysis, ACM Trans. Inf. Syst. 19(2), 131–160 (2001).
Haveliwala, T.H., Topic-sensitive PageRank, In: Proceedings of WWW ’02 (Honolulu, HI, USA, 2002), pp. 517-526.
Jeh, G. & Widom, J., SimRank: A measure of structural-context similarity, In: Proceedings of KDD ’02 (Edmonton, Canada, 2002), pp. 538–543.
Gyongyi, Z., Garcia-Molina, H. & Pedersen, J., Combating web spam with TrustRank, In: Proceedings of VLDB ’04 (Toronto, Canada, 2004), pp. 576-587.
Tong, H., Faloutsos, C. & Pan, J.-Y., Fast random walk with restart and its applications, In: Proceedings of ICDM ’06 (Washington, DC, USA, 2006), pp. 613-622.
Berkhin, P., A survey on PageRank computing, Internet Math. 2(1), 73-120 (2005).
Fabrikant, A., Mahdian, M. & Tomkins, A., SCRank, e-print arXiv:1802.08204v1, pp. 10 (2018).

Network formation and evolution

Generative models of network evolution and link copying models. Network optimization models and random geometric graphs.

Lectures materials:

Models of network evolution (see below)
Network optimization models (slides)

Book chapters:

Ch. 5: Barabási-Albert model in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Ch. 14: Models of network formation in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).

Course readings:

Kleinberg, J.M., Kumar, R. et al., The web as a graph, In: Proceedings of COCOON ’99 (Tokyo, Japan, 1999), pp. 1–17.
Dorogovtsev, S.N., Mendes, J.F.F. & Samukhin, A.N., Structure of growing networks with preferential linking, Phys. Rev. Lett. 85(21), 4633 (2000).
Bianconi, G. & Barabási, A.-L., Competition and multiscaling in evolving networks, Europhys. Lett. 54(4), 436-442 (2001).
Krapivsky, P.L. & Redner, S., Organization of growing random networks, Phys. Rev. E 63(6), 066123 (2001).
Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079–1187 (2002).
Vázquez, A., Growing network with local rules, Phys. Rev. E 67(5), 056104 (2003).
Krapivsky, P.L. & Redner, S., Network growth by copying, Phys. Rev. E 71(3), 036118 (2005).
Leskovec, J., Kleinberg, J. & Faloutsos, C., Graph evolution, ACM Trans. Knowl. Discov. Data 1(1), 1–41 (2007).
Hébert-Dufresne, L., Allard, A. et al., Structural preferential attachment, Phys. Rev. Lett. 107(15), 158702 (2011).
Hébert-Dufresne, L., Allard, A. et al., Structural preferential attachment, Phys. Rev. E 85(2), 026108 (2012).

D'Souza, R.M., Borgs, C. et al., Emergence of tempered preferential attachment from optimization, P. Natl. Acad. Sci. USA 104(15), 6112-6117 (2007).
Fabrikant, A., Koutsoupias, E. & Papadimitriou, C., Heuristically optimized trade-offs, In: Proceedings of ICALP ’02 (Malaga, Spain, 2002), pp. 110-122.
Pržulj, N., Corneil, D.G. & Jurisica, I., Modeling interactome: Scale-free or geometric?, Bioinformatics 20(18), 3508–3515 (2004).
Ferrer i Cancho, R. & Solé, R.V., Optimization in complex networks, e-print arXiv:cond-mat/0111222v1, pp. 4 (2006).
Gastner, M.T. & Newman, M.E.J., Optimal design of spatial distribution networks, Phys. Rev. E 74(1), 016117 (2006).
Papadopoulos, F., Kitsak, M. et al., Popularity versus similarity in growing networks, Nature 489(7417), 537-540 (2012).

Network inference and prediction

Network inference and link prediction methods. Network-based clustering, classification and regression. Network influence maximization and outbreak detection.

Lectures materials:

Network inference and link prediction (slides)
Network-based clustering and classification (slides)
Network influence maximization (video)
Network outbreak detection (video)

Course readings:

Liben‐Nowell, D. & Kleinberg, J., The link‐prediction problem for social networks, J. Am. Soc. Inf. Sci. Tec. 58(7), 1019-1031 (2007).
Clauset, A., Moore, C. & Newman, M.E.J., Hierarchical structure and the prediction of missing links in networks, Nature 453(7191), 98-101 (2008).
Guimera, R. & Sales-Pardo, M., Missing and spurious interactions and the reconstruction of complex networks, P. Natl. Acad. Sci. USA 106(52), 22073-22078 (2009).
Gomez-Rodriguez, M., Leskovec, J. & Krause, A., Inferring networks of diffusion and influence, ACM Trans. Knowl. Discov. Data 5(4), 21:1-37 (2012).
Martin, T., Ball, B. & Newman, M.E.J., Structural inference for uncertain networks, Phys. Rev. E 93(1), 012306 (2016).
Zhou, T., Lü, L. & Zhang, Y.-C., Predicting missing links via local information, Eur. Phys. J. B 71(4), 623-630 (2009).
Backstrom, L. & Leskovec, J., Supervised random walks, In: Proceedings of WSDM '11 (Hong Kong, China, 2011), pp. 635-644.
Yan, B. & Gregory, S., Finding missing edges in networks based on their community structure, Phys. Rev. E 85(5), 056112 (2012).
Li, Z., Fang, X. & Sheng, O., A survey of link recommendation for social networks, e-print arXiv:1511.01868v1, pp. 34 (2015).
Lü, L. & Zhou, T., Link prediction in complex networks: A survey, Physica A 390(6), 1150-1170 (2011).

Getoor, L. & Diehl, C.P., Link mining: A survey, SIGKDD Explor. 7(2), 3–12 (2005).
Getoor, L., Friedman, N. et al., Learning probabilistic models of link structure, J. Mach. Learn. Res. 3, 679–707 (2002).
Neville, J. & Jensen, D., Iterative classification in relational data, In: Proceedings of SRL ’00 (Austin, TX, USA, 2000), pp. 13–20.
Macskassy, S.A. & Provost, F., Classification in networked data: A toolkit and a univariate case study, J. Mach. Learn. Res. 8, 935-983 (2007).
Bhattacharya, I. & Getoor, L., Collective entity resolution in relational data, ACM Trans. Knowl. Discov. Data 1(1), 5:1-9 (2007).
Bhagat, S., Cormode, G. & Muthukrishnan, S., Node classification in social networks, e-print arXiv:1101.3291v1, pp. 37 (2011).
McAuley, J.J. & Leskovec, J., Learning to discover social circles in ego networks, In: Proceedings of NIPS ’12 (Lake Tahoe, NV, USA, 2012), pp. 548-556.
Hric, D., Darst, R.K. & Fortunato, S., Structural communities versus ground truth, Phys. Rev. E 90(6), 062805 (2014).
Šubelj, L., Exploratory and predictive tasks of network community detection, In: Proceedings of NetSci '15 (Zaragoza, Spain, 2015), p. 1.
Hric, D., Peixoto, T.P. & Fortunato, S., Network structure, metadata and the prediction of missing nodes, e-print arXiv:1604.00255v1, pp. 13 (2016).
Zanin, M., Papo, D. et al., Combining complex networks and data mining: Why and how, e-print arXiv:1604.08816, pp. 58 (2016).
Perozzi, B., Al-Rfou, R. & Skiena, S., DeepWalk, In: Proceedings of KDD ’14 (New York, NY, USA, 2014), pp. 701-710.
Grover, A. & Leskovec, J., node2vec, In: Proceedings of KDD ’16 (San Francisco, CA, USA, 2016), pp. 855-864.
Figueiredo, D.R., Ribeiro, L.F.R. & Saverese, P.H.P., struc2vec, In: Proceedings of KDD ’17 (Halifax, Canada, 2017), pp. 1–9.
Peel, L., Graph-based semi-supervised learning for relational networks, In: Proceedings of SDM ’17 (Houston, TX, USA, 2017), pp. 1-11.

Network sampling and comparison

Fractal networks and self-similarity, network sampling, backbones and skeletons. Network comparison by fragments and statistical comparison of network metrics.

Lectures materials:

Network self-similarity and sampling (slides)
Network backbones and skeletons (slides)
Structural network comparison (slides)

Book chapters:

Ch. 3.7: Snowball sampling etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).

Course readings:

Song, C., Havlin, S. & Makse, H.A., Self-similarity of complex networks, Nature 433(7024), 392-395 (2005).
Lee, S.H., Kim, P.-J. & Jeong, H., Statistical properties of sampled networks, Phys. Rev. E 73(1), 016102 (2006).
Leskovec, J. & Faloutsos, C., Sampling from large graphs, In: Proceedings of KDD '06 (Philadelphia, PA, USA, 2006), pp. 631-636.
Furuya, S. & Yakubo, K., Multifractality of complex networks, Phys. Rev. E 84(3), 036118 (2011).
Laurienti, P.J., Joyce, K.E. et al., Universal fractal scaling of self-organized networks, Physica A 390(20), 3608–3613 (2011).
Blagus, N., Šubelj, L. & Bajec, M., Self-similar scaling of density in complex real-world networks, Physica A 391(8), 2794-2802 (2012).
Schneider, C.M., Kesselring, T.A. et al., Box-covering algorithm for fractal dimension of complex networks, Phys. Rev. E 86(1), 016707 (2012).
Guimerà, R., Danon, L. et al., Self-similar community structure in a network of human interactions, Phys. Rev. E 68(6), 065103 (2003).
Blagus, N., Šubelj, L. et al., Sampling promotes community structure in social and information networks, Physica A 432, 206-215 (2015).
Blagus, N., Šubelj, L. & Bajec, M., Assessing the effectiveness of real-world network simplification, Physica A 413, 134-146 (2014).

Grady, D., Thiemann, C. & Brockmann, D., Robust classification of salient links in complex networks, Nat. Commun. 3, 864 (2012).
van den Heuvel, M.P., Kahn, R.S. et al., High-cost, high-capacity backbone for global brain communication, P. Natl. Acad. Sci. USA 109(28), 11372–11377 (2012).
Ruan, N., Jin, R. et al., Network backbone discovery using edge clustering, e-print arXiv:1202.1842v2, pp. 14 (2012).
Hamann, M., Lindner, G. et al., Structure-preserving sparsification methods for social networks, Soc. Netw. Anal. Min. 6(1), 22 (2016).
Coscia, M. & Neffke, F., Network backboning with noisy data, In: Proceedings of ICDE '17 (San Diego, CA, USA, 2017), pp. 425–436.
Šubelj, L., Convex skeletons of complex networks, e-print arXiv:1709.00255v2, pp. 11 (2017).

Milo, R., Itzkovitz, S. et al., Superfamilies of evolved and designed networks, Science 303(5663), 1538-1542 (2004).
Pržulj, N., Biological network comparison using graphlet degree distribution, Bioinformatics 23(2), e177-e183 (2007).
Cooper, K. & Barahona, M., Role-similarity based comparison of directed networks, e-print arXiv:1103.5582v1, pp. 6 (2011).
Bagrow, J.P. & Bollt, E.M., An information-theoretic, all-scales approach to comparing networks, e-print arXiv:1804.03665v1, pp. 18 (2018).
Šubelj, L., Fiala, D. & Bajec, M., Network-based statistical comparison of bibliographic databases, Sci. Rep. 4, 6496 (2014).
Yaveroğlu, Ö.N., Malod-Dognin, N. et al., Revealing the hidden language of complex networks, Sci. Rep. 4, 4547 (2014).
Aparício, D., Ribeiro, P. & Silva, F., Network comparison using directed graphlets, e-print arXiv:1511.01964v1, pp. 9 (2015).
Schieber, T. A., Carpi, L. et al., Quantification of network structural dissimilarities, Nat. Commun. 8, 13928 (2017).

Network dynamics and processes

Decentralized search and network navigation. Percolation theory and network robustness. Spreading and diffusion on networks. Game theory and networks.

Lectures materials:

Percolation and network robustness (slides)
Epidemic spreading on networks (slides)
Network diffusion and contagion (video)
Search and network navigation (video)
Game theory and networks (skipped)

Book chapters:

Ch. 8: Network robustness & Ch. 10: Spreading phenomena in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Ch. 16: Percolation etc. & Ch. 17: Epidemics on networks in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Ch. 6-9: Game theory etc. in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).

Course readings:

Vespignani, A., Modelling dynamical processes in complex socio-technical systems, Nat. Phys. 8(1), 32–39 (2012).

Molloy, M. & Reed, B., A critical point for random graphs with a given degree sequence, Random Struct. Algor. 6(2-3), 161–180 (1995).
Albert, R., Jeong, H. & Barabási, A.-L., Error and attack tolerance of complex networks, Nature 406(6794), 378–382 (2000).
Callaway, D.S., Newman, M.E.J. et al., Network robustness and fragility, Phys. Rev. Lett. 85(25), 5468–5471 (2000).
Cohen, R., Erez, K. et al., Resilience of the Internet to random breakdowns, Phys. Rev. Lett. 85(21), 4626 (2000).
Cohen, R., Erez, K. et al., Breakdown of the Internet under intentional attack, Phys. Rev. Lett. 86(16), 3682–3685 (2001).
Bollobás, B. & Riordan, O., Robustness and vulnerability of scale-free random graphs, Internet Math. 1(1), 1–35 (2003).

Pastor-Satorras, R. & Vespignani, A., Epidemic spreading in scale-free networks, Phys. Rev. Lett. 86(14), 3200–3203 (2001).
Pastor-Satorras, R. & Vespignani, A., Epidemic dynamics and endemic states in complex networks, Phys. Rev. E 63(6), 066117 (2001).
Colizza, V., Barrat, A. et al., Role of airline transportation network in global epidemics, P. Natl. Acad. Sci. USA 103(7), 2015-2020 (2006).
González, M.C., Hidalgo, C.A. & Barabási, A.-L., Understanding individual human mobility patterns, Nature 453, 779-782 (2008).
Castellano, C. & Pastor-Satorras, R., Thresholds for epidemic spreading in networks, Phys. Rev. Lett. 105(21), 218701 (2010).
Karrer, B. & Newman, M.E.J., Message passing approach for general epidemic models, Phys. Rev. E 82(1), 016101 (2010).
Karrer, B. & Newman, M.E.J., Competing epidemics on complex networks, Phys. Rev. E 84(3), 036106 (2011).
Barabási, A.-L., The origin of bursts and heavy tails in human dynamics, Nature 435, 207-211 (2005).

Alternative types of networks

Attributed, valued and signed networks. Multi-relational, multilayer and higher-order networks. Temporal and spatial networks.

Lectures materials:

Attributed, valued and signed networks (see above)
Multi-relational and multilayer networks (skipped)
Higher-order dependencies in networks (skipped)
Temporal and spatial networks (skipped)

Book chapters:

Ch. 5: Negative relationship etc. in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).

Course readings:

Cartwright, D. & Harary, F., Structural balance: A generalization of Heider's theory, Psychol. Rev. 63(5), 277-293 (1956).
Davis, J.A., Structural balance, mechanical solidarity, and interpersonal relations, Am. J. Sociol. 68(4), 444-462 (1963).
Antal, T., Krapivsky, P.L. & Redner, S., Dynamics of social balance on networks, Phys. Rev. E 72(3), 036121 (2005).
Marvel, S.A., Strogatz, S. & Kleinberg, J., Energy landscape of social balance, Phys. Rev. Lett. 103(19), 198701 (2009).
Leskovec, J., Huttenlocher, D. & Kleinberg, J., Signed networks in social media, In: Proceedings of CHI ’10 (Atlanta, GA, USA, 2010), pp. 1361-1370.
Leskovec, J., Huttenlocher, D. & Kleinberg, J., Predicting positive and negative links in online social networks, In: Proceedings of WWW ’10 (Raleigh, NC, USA, 2010), pp. 641-650.
Facchetti, G., Iacono, G. & Altafini, C., Computing global structural balance in large-scale signed social networks, P. Natl. Acad. Sci. USA 108(52), 20953–20958 (2011).
Marvel, S.A., Kleinberg, J. et al., Continuous-time model of structural balance, P. Natl. Acad. Sci. USA 108(5), 1771-1776 (2011).

Barthelemy, M., Spatial networks, Phys. Rep. 499(1-3), 1–101 (2011).
Holme, P. & Saramäki, J., Temporal networks, Phys. Rep. 519(3), 97–125 (2012).
Kivelä, M., Arenas, A. et al., Multilayer networks, J. Complex Netw. 2(3), 203-271 (2014).
Boccaletti, S., Bianconi, G. et al., The structure and dynamics of multilayer networks, Phys. Rep. 544(1), 1–122 (2014).
De Domenico, M., Granell, C. et al., The physics of multilayer networks, e-print arXiv:1604.02021v1, pp. 22 (2016).
Holme, P., Modern temporal network theory: A colloquium, Eur. Phys. J. B 88(9), 234 (2015).

Empirical analysis of networks

Network representations, data structures, fundamental algorithms, programming libraries and software. Node layout and network visualization.

Lectures materials:

Network representations and data structures (slides)
Fundamental network analysis algorithms (slides)
Node layout and network visualization (slides)
Network libraries and software (handout)

Book chapters:

Ch. 4.8: Generating networks etc. in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Ch. 9-11.1: Network algorithms etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).

Course readings:

Brandes, U., A faster algorithm for betweenness centrality, J. Math. Sociol. 25(2), 163-177 (2001).
Batagelj, V. & Brandes, U., Efficient generation of large random networks, Phys. Rev. E 71(3), 036113 (2005).
Sanders, P. & Schulz, C., Scalable generation of scale-free graphs, e-print arXiv:1602.07106v1, pp. 6 (2016).
Clauset, A., Shalizi, C.R. & Newman, M.E.J., Power-law distributions in empirical data, SIAM Rev. 51, 661-703 (2009).
Hočevar, T. & Demšar, J., A combinatorial approach to graphlet counting, Bioinformatics 30(4), 559-565 (2014).
Ahmed, N.K., Neville, J. et al., Graphlet decomposition, e-print arXiv:1506.04322v2, pp. 32 (2016).
Fortunato, S., Community detection in graphs, Phys. Rep. 486(3-5), 75-174 (2010).
Berkhin, P., A survey on PageRank computing, Internet Math. 2(1), 73-120 (2005).

Eades, P., A heuristic for graph drawing, Congressus Numerantium 42, 146-160 (1984).
Kamada, T. & Kawai, S., An algorithm for drawing general undirected graphs, Inform. Process. Lett. 31(1), 7-15 (1989).
Fruchterman, T.M.J. & Reingold, E.M., Graph drawing by force-directed placement, Softw: Pract. Exper. 21(11), 1129-1164 (1991).
Rodrigues, J., Tong, H. et al., GMine, In: Proceedings of VLDB ’06 (Seoul, South Korea, 2006), pp. 1195-1198.
Rodrigues, J., Traina, A. et al., Supergraph visualization, In: Proceedings of ISM ’06 (San Diego, CA, USA, 2006), pp. 227-234.
Kobourov, S.G., Spring embedders and force directed graph drawing algorithms, e-print arXiv:1201.3011v1, pp. 23 (2012).
Gibson, H., Faith, J. & Vickers, P., A survey of two-dimensional graph layout techniques, Infor. Visual. 12(3-4), 324-357 (2013).
Ma, K.-L. & Muelder, C.W., Large-scale graph visualization and analytics, Computer 46(7), 39-46 (2013).

Applications of network analysis

Comparing bibliographic databases, clustering and modeling scientific publications, and analyzing scientific coauthorships. Mining software dependency networks. Detecting automobile insurance fraudsters.

Lectures materials:

Comparing databases (see above)
Clustering scientific publications (slides)
Modeling scientific publications (slides)
Analyzing scientific coauthorships (skipped)
Software dependency networks (slides)
Insurance fraud detection (slides)

Course Activities

Recent Courses

Тематический план

Общее

Advanced Topics in Network Science (ANTS)

Course lecturers

Outline & objective

Literature & readings

Course assignments

Course syllabus

Course discussions

From graph theory to network science

Large-scale structure and models

Mesoscopic structure and fragments

Node position and similarity

Network formation and evolution

Network inference and prediction

Network sampling and comparison

Network dynamics and processes

Alternative types of networks

Empirical analysis of networks

Applications of network analysis