INA: (Introduction to) Network Analysis
Nimate dovoljenja za ogled razprav v tem forumu
Section outline
-
Introduction to Network Analysis (INA)
-
From classical graph theory to social network analysis and modern network science. Networks in different fields of science.
Lecture slides:
- (1) Networks introduction and motivation
- (1) From graph theory to network science
- (6) Networks through fields of science
Lab notebooks:
Book chapters:
- → Ch. 1: Introduction in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 1-5: Introduction etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Ch. 1: Overview 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).
- → 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).
- Hegeman, T. & Iosup, A., Survey of graph analysis applications, e-print arXiv:180700382v1, pp. 23 (2018).
- Cimini, G., Squartini, T. et al., The statistical physics of real-world networks, Nat. Rev. Phys. 1(1), 58-71 (2019).
- → Cramer, C., Porter, M.A. et al., Network Literacy: Essential Concepts and Core Ideas (Creative Commons Licence, 2015).
- Hidalgo, C.A., Disconnected, fragmented, or united? A trans-disciplinary review of network science, Appl. Netw. Sci. 1, 6 (2016).
- Molontay, R. & Nagy, M., Two decades of network science, In: Proceedings of ASONAM '19 (Vancouver, Canada, 2019), pp. 578–583.
- Ch. 1: Uvod in Šubelj, L., Odkrivanje skupin vozlišč v velikih realnih omrežjih, PhD thesis (University of Ljubljana, 2013).
-
Graphology and networkology. Network representations, formats, and data. Random graph models and real networks models.
Lecture slides:
- (1-2) Graphology and networkology
- (2) Network representations and data
- (2-3) Erdős-Rényi random graph model
- (3) Configuration graph model
Lab notebooks:
- (ii) Network representations and algorithms (I, II, III)
- (iii) Advanced algorithms and random graphs (I, II, III, IV)
Book chapters:
- → Ch. 2: Graph theory & Ch. 4.8: Generating networks in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 6: Mathematics of networks & Ch. 12-13: Random graphs etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Ch. 2: Graphs 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).
- Watts, D.J. & Strogatz, S.H., Collective dynamics of 'small-world' networks, Nature 393(6684), 440-442 (1998).
- Barabási, A.-L. & Albert, R., Emergence of scaling in random networks, Science 286(5439), 509-512 (1999).
- Broder, A., Kumar, R. et al., Graph structure in the Web, Comput. Netw. 33(1-6), 309-320 (2000).
- 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: What goes wrong and how to fix it, J. Complex Netw. 5(3), 337-351 (2017).
- Fosdick, B., Larremore, D. et al., Configuring random graph models with fixed degree sequences, SIAM Rev. 60(2), 315-355 (2018).
- → 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. & Park, J., Why social networks are different from other types of networks, Phys. Rev. E 68(3), 036122 (2003).
- → Backstrom, L., Boldi, P. et al., Four degrees of separation, In: Proceedings of WebSci '12 (Evanston, IL, USA, 2012), pp. 45-54.
- 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.
- Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079-1187 (2002).
- (1-2) Graphology and networkology
-
Degrees of separation, small-world networks and model. Power-law degree distributions, scale-free networks and models.
Lecture handouts:
- (3) Small-world networks and model
- (3-4) Scale-free distributions and networks
- (4) Preferential attachment models
Lab notebooks:
- (iv) Small-world and scale-free models (I, II, III)
- (vi) Errors and attacks on the Internet (III)
Book chapters:
- → Ch. 3.8-9: Small worlds etc. & Ch. 4-5: Scale-free property etc. in
Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 8.4: Power laws etc. & Ch. 14-15: Models of network formation etc. in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Ch. 18: Power laws etc. and Ch. 20: Small-world phenomenon in Easley, D. & Kleinberg, J., Networks, Crowds, and Markets (Cambridge University Press, 2010).
Course readings:
- Milgram, S., The small world problem
, Psychol. Today 1(1), 60-67 (1967).
- Granovetter, M.S., The strength of weak ties, Am. J. Sociol. 78(6), 1360-1380 (1973).
- → 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).
- → Zamora-López, G. & Brasselet, R., Sizing the length of complex networks, e-print arXiv:1810.12825v1, pp. 25 (2018).
- → Kleinberg, J.M., Navigation in a small world, Nature 406(6798), 845 (2000).
- 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).
- Faloutsos, M., Faloutsos, P. & Faloutsos, C., On power-law relationships of the Internet topology, Comput. Commun. Rev. 29(4), 251-262 (1999).
- Clauset, A., Shalizi, C.R. & Newman, M.E.J., Power-law distributions in empirical data, SIAM Rev. 51, 661-703 (2009).
- → 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).
- Dorogovtsev, S.N. & Mendes, J.F.F., Evolution of networks, Adv. Phys. 51(4), 1079-1187 (2002).
- De Domenico, M. & Arenas, A., Modeling structure and resilience of the dark network, Phys. Rev. E 95(2), 022313 (2017).
- Golosovsky, M., Preferential attachment mechanism of complex network growth, e-print arXiv:1802.09786v1, pp. 12 (2018).
- Voitalov, I., van der Hoorn, P. et al., Scale-free networks well done, e-print arXiv:1811.02071v1, pp. 31 (2018).
- Broido, A.D. & Clauset, A., Scale-free networks are rare, Nat. Commun. 10(1), 1017 (2019).
- Barabási, A.-L., Love is all you need, reply to e-print arXiv:1801.03400v1, pp. 6 (2018).
- → Holme, P., Rare and everywhere, Nat. Commun. 10(1), 1016 (2019).
- → Mannion, S. & MacCarron, P., Fitting degree distributions of complex networks, e-print arXiv:2212.06649v1, pp. 21 (2022).
- (3) Small-world networks and model
-
Assortative and disassortative mixing. Degree mixing matrix, function and coefficient. Structural cutoff and disassortativity.
Lecture handouts:
Lab notebooks:
- (x) Node mixing by (not) degree (I, II, III)
Book chapters:
- → Ch. 7: Degree correlations in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 7.13: Homophily & Ch. 8.7: Assortative mixing in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Course readings:
- 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).
- Peel, L., Delvenne, J.-C., & Lambiotte, R., Multiscale mixing patterns in networks, P. Natl. Acad. Sci. USA 115(16), 4057-4062 (2018).
- Estrada, E., Combinatorial study of degree assortativity in networks, Phys. Rev. E 84(4), 047101 (2011).
- (x) Node mixing by (not) degree (I, II, III)
-
Community and core-periphery structure. Graph partitioning, community detection, blockmodeling, stochastic (block) models etc.
Lecture handouts:
- (7) Network community structure
- (7-8) Partitioning and community detection
- (8) Blockmodeling and stochastic models
- (8) Network core-periphery structure
Lab notebooks:
- (vii) Community detection & benchmarks (I, II, III, IV)
- (viii) Blockmodeling & k-core decomposition (I, II, III)
Book chapters:
- → Ch. 9: Communities in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
- Ch. 7.12-13: Homophily etc. & Ch. 11: Graph partitioning in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- Ch. 21: Communities in networks 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).
- Newman, M.E.J. & Girvan, M., Mixing patterns and community structure in networks, Phys. Rev. E 67(2), 026126 (2003).
- 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).
- 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).
- 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).
- → 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).
- → Newman, M.E.J., Communities, modules and large-scale structure in networks, Nat. Phys. 8 (1), 25-31 (2012).
- 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).
- Zhao, Y., Levina, E. & Zhu, J., Community extraction for social networks, P. Natl. Acad. Sci. USA 108(18), 7321-7326 (2011).
- Reichardt, J. & White, D.R., Role models for complex networks, Eur. Phys. J. B 60(2), 217-224 (2007).
- → 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).
- 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).
-
Network motifs, motif significance and ratio profiles. Network graphlets, node orbits and graphlet degree distributions.
Lecture handouts:
- (10) Network motifs and graphlets
- (handout) Graphlets and motifs
Lab notebooks:
Book chapters:
- → Ch. 13: Fragment-based measures in Estrada, E. & Knight, P.A., A First Course in Network Theory (Oxford University Press, 2015).
Course readings:
- 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, In: Proceedings of AISTATS '12 (La Palma, Spain, 2012), pp. 54-63.
- → Sarajlić, A., Malod-Dognin, N. et al., Predictive functional connectivity of real-world systems, e-print arXiv:1603.05470v1, pp. 17 (2016).
- → Sanchez-Garcia, R.J., Exploiting symmetry in network analysis, e-print arXiv:1803.06915v1, pp. 7 (2018).
-
Node clustering coefficients, degrees, eigenvector, closeness, and betweenness centrality. Link analysis algorithms.
Lecture handouts:
Lab notebooks:
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., A set of measures of centrality based on betweenness, Sociometry 40(1), 35-41 (1977).
- 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. 4(3), 319-329 (2015).
- 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).
- 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).
- Jeh, G. & Widom, J., SimRank: A measure of structural-context similarity, In: Proceedings of KDD ’02 (Edmonton, Canada, 2002), pp. 538–543.
- 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).
-
Link betweenness and bridgeness centrality. Link embeddedness and topological overlap.
Lecture handouts:
Lab handouts:
Book chapters:
- Ch. 7: Measures and metrics in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
- → Ch. 9.3: Hierarchical clustering in Barabási, A.-L., Network Science (Cambridge University Press, 2016).
Course readings:
- → Brandes, U., A faster algorithm for betweenness centrality, J. Math. Sociol. 25(2), 163-177 (2001).
- 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).
- 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).
- 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. 4(3), 319-329 (2015).
- → Everett, M.G. & Valente, T.W., Bridging, brokerage and betweenness, Soc. Networks 44, 202-208 (2016).
- Wu, A.-K., Tian, L. & Liu, Y.-Y., Bridges in complex networks, Phys. Rev. E 97(1), 012307 (2018).
- Ch. 7: Measures and metrics in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
-
Hidden populations and network-based sampling. Network comparison by fragments, distances and metrics. Network backbones and skeletons.
Lecture handouts:
- (12) Network collection and sampling
- (handout) Overview of network sampling
- (12) Network similarity and comparison
- (handout) Network comparison methods
- (12) Network backbones and skeletons
Lab handouts:
- (xii) Random-walk sampling and Facebook (I, II)
- (xii) Networks and models comparison (III)
Book chapters:
- → Ch. 3.7: Snowball sampling etc.
in Newman, M.E.J., Networks: An Introduction (Oxford University Press, 2010).
Course readings:
- Granovetter, M., Network sampling: Some first steps, Am. J. Sociol. 81(6), 1287–1303 (1976).
- → 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).
- 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).
- → Blagus, N., Šubelj, L. & Bajec, M., Empirical comparison of network sampling, Physica A 477, 136–148 (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).
- 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).
- → 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).
- Šubelj, L., Bajec, M. et al., Quantifying the consistency of scientific databases, PLoS ONE 10(5), e0127390 (2015).
- Demšar, J., Statistical comparisons of classifiers over multiple data sets, J. Mach. Learn. Res. 7, 1–30 (2006).
- → 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, J. R. Soc. Interface 15(145), 20180422 (2018).
-
Spring embedders and force-directed node layout. Static, dynamic and heterogeneous network visualization.
Lecture handouts:
Lab handouts:
- (xiii) Wiring diagrams vs block models (I, II)
Course readings:
- 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 for information visualisation, 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).
- (xiii) Wiring diagrams vs block models (I, II)
-
Network inference and link prediction indices. Network-based node and link clustering, classification and regression.
Lecture handouts:
Lab handouts:
- (xiv) Node classification and link prediction (py, ows, html, log)
Course readings:
- Leicht, E.A., Holme, P. & Newman, M.E.J., Vertex similarity in networks, Phys. Rev. E 73(2), 026120 (2006).
- 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).
- → Godoy-Lorite, A., Guimerà, R. et al., Accurate and scalable social recommendation using stochastic block models,
P. Natl. Acad. Sci. USA 113(50), 14207–14212 (2016).
- Gomez-Rodriguez, M., Leskovec, J. & Krause, A., Inferring networks of diffusion and influence, ACM Trans. Knowl. Discov. Data 5(4), 21:1-37 (2012).
- 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).
- Wu, Z., Lin, Y. et al., Link prediction with node clustering coefficient, Physica A 452, 1-8 (2016).
- Lü, L. & Zhou, T., Link prediction in complex networks: A survey, Physica A 390(6), 1150-1170 (2011).
- Li, Z., Fang, X. & Sheng, O., A survey of link recommendation for social networks, e-print arXiv:1511.01868v1, pp. 34 (2015).
- Martin, T., Ball, B. & Newman, M.E.J., Structural inference for uncertain networks, Phys. Rev. E 93(1), 012306 (2016).
- Newman, M.E.J., Network structure from rich but noisy data, Nat. Phys. 14, 542-545 (2018).
- 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.
- Š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, Phys. Rev. X 6(3), 031038 (2016).
- → Zanin, M., Papo, D. et al., Combining complex networks and data mining: Why and how, Phys. Rep. 635, 1-44 (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.
- Hu, W., Fey, M. et al., Open graph benchmark: Datasets for machine learning on graphs, e-print arXiv:1101.3291v1, pp. 23 (2020).
-
Applications of network analysis in automobile insurance fraud, software engineering, and bibliometrics & scientometrics.
Lecture handouts:
- (6) Automobile insurance fraud
- (/) Software networks & engineering
- (6-7, 13) Scientometrics & bibliometrics
Further readings:
- Šubelj, L., Furlan, Š. & Bajec, M., An expert system for detecting automobile insurance fraud using social network analysis, Expert Syst. Appl. 38(1), 1039-1052 (2011).
- Šubelj, L. & Bajec, M., Community structure of complex software systems: Analysis and applications, Physica A 390(16), 2968-2975 (2011).
- Šubelj, L. & Bajec, M., Software systems through complex networks science: Review, analysis and applications, In: Proceedings of SoftMine ’12 (Beijing, China, 2012), pp. 9–16.
- → Šubelj, L., Žitnik, S. et al., Node mixing and group structure of complex software networks, Advs. Complex Syst. 17(7-8), 1450022 (2014).
- → Šubelj, L. & Bajec, M., Model of complex networks based on citation dynamics, In: Proceedings of LSNA ’13 (Rio de Janeiro, Brazil, 2013), pp. 527–530.
- Šubelj, L., Žitnik, S. & Bajec, M., Who reads and who cites? Unveiling author citation dynamics by modeling citation networks, In: Proceedings of NetSci '14 (Berkeley, CA, USA, 2014), p. 1.
- Šubelj, L., Van Eck, N.J. & Waltman, L., Comparison of methods for clustering citation networks, In: Proceedings of NetSci-X ’16 (Wroclaw, Poland, 2016), p. 1.
- → Šubelj, L., Van Eck, N.J. & Waltman, L., Clustering scientific publications based on citation relations: A systematic comparison of methods, PLoS ONE 11(4), e0154404 (2016).
-
Importance of scientific publications. Fast algorithm for community detection. Sampling with spanning trees. Model of shrinking networks.
Conference talks: