INA: (Introduction to) Network Analysis

Topic outline

• 

  Introduction to Network Analysis (INA)

  • Course instructor

    Lovro Šubelj (R 2.49)

  • Course schedule
    

    The lectures start on Feb 19th, 2021 and the labs start on Mar 1st, 2021.

    • Lectures: Fridays at 2:15pm online (Zoom)
    • Labs: Mondays, Tuesdays, Thursdays online (Zoom)
    • Office hours: by agreement (Piazza)

  • Course syllabus by week URL
  • Outline & objective
    

    Networks or graphs are ubiquitous in everyday life. Examples include online social networks, Web, terrorist affiliations, LPP bus map, plumbing systems and your brain. Many such real-world networks reveal characteristic patterns of connectedness that are far from regular or random. However, while small networks can be drawn by hand and analyzed by a naked eye, real-world networks require specialized computer algorithms, techniques and models. This led to the emergence of a new scientific field more than 20 years ago denoted network analysis or network science.

    The course will first introduce the field of network analysis and highlight the differences between classical graph theory and modern network science. In the main part of the course, students will learn about fundamental concepts and techniques for the analysis of real-world networks including node centralities and equivalence, motifs and graphlets, blockmodeling, community detection, role discovery, link prediction, network modeling, sampling, comparison and visualization. The last part of the course will be devoted to selected practical applications of network analysis in fraud detection, software engineering, information science and other.

    The objective of the course is to present a broad spectrum of network analysis concepts and techniques, clarify their theoretical foundations and demonstrate their practical applicability. The lectures will give theoretical discussion on network concepts and present efficient algorithms and techniques for their analysis, while students will work on practical examples of applying network analysis within labs and their coursework. The topics covered were selected thus to be suitable for a wider range of students and to serve as an introduction to more advanced network analysis courses like Machine Learning with Graphs and Advanced Topics in Network Science (see network courses design).

    Except for good programming skills in some general purpose language (e.g. Python, Java, C/C++), there are no specific prerequisites for the course. However, students will benefit from a solid knowledge in graph theory, probability theory and statistics, and linear algebra.
  • Coursework & grading
    

    Students are expected to attend and actively participate in lectures and labs. The ongoing coursework will consist of three homeworks (and one setup homework) on network analysis concepts and techniques. Each homework will require certain amount of programming, some analytical derivations and some practical applications to real-world problems.

    The main part of the coursework consists of a substantial course project. Students will be encouraged to submit a report describing their course project to the preprint server arXiv.org or make their work publicly available. All students will have to present their project in front of their peers. Students are encouraged to work in groups of three, while other sizes of groups will be allowed only in special cases. 

    Course grade will be based 40% on homeworks (13.3% on each homework), 50% on course project (10% on project proposal, 35% on project paper and 5% on presentation), and 10% on course challenges, participation and commitment. There will be no written exam for this course, but selected students will have to attend oral exam.

  • Course assignments
    

    All course assignments will be out and due according to course syllabus, and must be submitted before Friday at 9:00pm. Twice during the semester you can take advantage of late days, which means that an assignment is submitted late. Late days for an assignment that is due this Friday expire next Monday at 12:00pm.

    Students can prepare their assignments in either English or Slovene. Each assignment must be submitted through eUcilnica and must include course cover sheet with signed honor code!

  • Submit Homework #3 Assignment
  • Literature & materials
    

    All course materials will be posted periodically on this web page. The following course books are 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, 2018).
    • Coscia, M., The Atlas for the Aspiring Network Scientist (e-print arXiv:210100863v2, 2021).
    • 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 discussions

  • Questions and discussions URL
• 

  From graph theory to network science

  From classical graph theory to social network analysis and modern network science. Networks in different fields of science.

  Lecture handouts: 

  • (1) Networks introduction and motivation [pdf]
  • (1) From graph theory to network science [pdf]
  • (5) Networks through fields of science [pdf]

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

  Random graphs vs real networks

  Graphology and networkology. Network representations, formats and data. Random graph models and real networks models.

  Lecture handouts:

  • (2) Graphology and networkology [pdf]
    
  • (2) Network representations and data [pdf]
  • (3) Erdős–Rényi random graph model [pdf]
    
  • (3) Configuration graph model [pdf]
  • (3) Real networks models [pdf]

  Lab handouts:

  • (ii) Network representations and algorithms [html, java, py, log]
  • (iii) Advanced algorithms and random graphs [html, java, log]

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

  Small-world and scale-free networks

  Degrees of separation, small-world networks and model. Power-law degree distributions, scale-free networks and models.

  Lecture handouts:

  • (5) Small-world networks and model [pdf]
    
  • (6) Scale-free distributions and networks [pdf]
  • (6) Preferential attachment models [pdf]

  Lab handouts:

  • (v) Small-world networks and model [html, java, log, zip]
  • (vi) Scale-free networks and models [html, java, log, zip]

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

  Node mixing and network structure

  Assortative and disassortative mixing. Degree mixing matrix, function and coefficient. Structural cutoff and disassortativity.

  Lecture handouts:

  • (7) Node mixing in networks [pdf]

  Lab handouts:

  • (vii) Node mixing by (not) degree [html, java, log]
    

  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).
• This topic
  

  Node clusters and mesoscopic structure

  Community and core-periphery structure. Graph partitioning, community detection, blockmodeling, stochastic (block) models etc.

  Lecture handouts:

  • (8) Network community structure [pdf]
  • (8) Partitioning and community detection [pdf]
  • (9) Blockmodeling and stochastic models [pdf]
  • (9) Network core-periphery structure [pdf]

  Lab handouts:

  • (viii) Community detection and partitioning [html, java, log]
  • (x) Block models and k-cores decomposition [html]

  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 fragments and frequent subgraphs

  Network motifs, motif significance and ratio profiles. Network graphlets, node orbits and graphlet degree distributions.

  Lecture handouts:

  • (7) Network motifs and graphlets [pdf]
    

  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 position and measures of centrality

  Node clustering coefficients, degrees, eigenvector, closeness and betweenness centrality. Link analysis algorithms.

  Lecture handouts:

  • (4) Measures of node centrality [pdf]
    
  • (5) Link analysis algorithms [pdf]

  Lab handouts:

  • (iv) Node centrality and PageRank [html, java, log]
    

  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 importance and measures of bridging

  Link betweenness and bridgeness centrality. Link embeddedness and topological overlap.

  Lecture handouts:

  • (5) Measures of link bridging [pdf]

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

  Node layout and network visualization

  Spring embedders and force-directed node layout. Static, dynamic and heterogeneous network visualization.

  Lecture handouts:

  • (11) Node layout and network visualization [pdf]
    

  Lab handouts:

  • (xi) Board with pegs & bands
    

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

  Network collection, sampling and comparison

  Network comparison by fragments and metrics. Hidden populations and network-based sampling. Network backbones and skeletons.

  Lecture handouts:

  • (11) Network metrics comparison [pdf]
  • (12) Network collection and sampling [pdf]
  • (12) Network backbones and skeletons [pdf]

  Lab handouts:

  • (xi) Networks and models comparison
  • (xii) Random-walk sampling and Facebook
    

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

  Network inference and network-based mining

  Network inference and link prediction indices. Network-based node and link clustering, classification and regression.

  Lecture handouts:
  

  • (13) Network inference and link prediction
  • (13) Clustering, classification and regression

  Lab handouts:

  • (xiii) Mining nodes of networks

  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

  Applications of network analysis in automobile insurance fraud, software engineering and bibliometrics & scientometrics.

  Lecture handouts:

  • Automobile insurance fraud
  • Software networks & engineering
  • Bibliometrics & scientometrics

  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).