INA: (Introduction to) Network Analysis

Topic outline

• 

   

  Introduction to Network Analysis (INA)

  • Course staff

    Lovro Šubelj (instructor)
    

  • Course schedule
    

    The lectures start on Feb 16th, 2023 and the labs start on Feb 20th, 2023.

    • Lectures: Thursday at 11:15am in PR 22
    • Labs (hands-on & consultations):
    • Monday at 12:15pm in PR 8
    • Monday at 3:15pm in PR 8
    • Wednesday at 4:15pm in PR 8
    • Thursday at 2:15pm in PR 7 (or 4)
    • Office hours: by agreement on Zoom

    Every student can attend any labs and consultations.

  • Course syllabus by week URL
  • Outline & objective
    

    Networks or graphs are ubiquitous in everyday life. Examples include online social networks, the 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 about 25 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 wide range of students and to serve as an introduction to more advanced network analysis courses such as Machine Learning with Graphs (see network courses design).

    Except for good programming skills in some general purpose language (preferably Python), 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 two homeworks 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 will consist of a group course project. Students can choose the project topic on their own or select one of the suggested topics. Projects must be done in groups of three or four students, whereas other group sizes will be allowed only in exceptional cases.

    The final exam will be an open-book written exam for which you register in StudIS, while students can also ask for an oral exam. Students must score at least 50% on the exam to pass the course. The schedule of the exams is shown below.
    

    • Jun 7th, 2023 at 12:00pm in PR 22
    • Jun 29th, 2023 at 12:00pm in PR 22
    • Sep 4th, 2023 at 12:00pm in PR 22

    The course grade is based 25% on two homeworks (12.5% each), 25% on the course project and 50% on the final exam. Additional points may be awarded based on course challenges, participation, commitment etc.

  • Assignments & submission
    

    All course assignments will be out and due according to course syllabus, and must be submitted before Friday at 11:59pm.

    Students can prepare their assignments in either English or Slovene. Each assignment must be submitted to Gradescope (entry code G2JD8Y) and eUcilnica (using options below), and must include assignment cover sheet with signed honor code! An assignment is considered submitted only when both parts have been submitted.

  • Submit Homework #1 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).
    • Menczer, F., Fortunato, S. & Davis, C.A., A First Course in Network Science (Cambridge University Press, 2020).
    • 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

    Please use Piazza for all course-related disscussions and also personal matters.

  • Questions and discussions URL
  • Course announcements Forum
• 

  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 slides: 

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

  Lab handouts:

  • (i) Recitation on NetworkX, Pajek etc. [py, log]

  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 slides:

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

  Lab handouts:

  • (ii) Network representations and algorithms [pdf, py, log]
  • (iii) Advanced algorithms and random graphs [pdf, py, 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:

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

  Lab handouts:

  • (iv) Small-world and scale-free models [pdf]

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

  Node position and measures of centrality

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

  Lecture handouts:

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

  Lab handouts:

  • (vi) Node centrality and PageRank
    

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

  Applications of network analysis

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

  Lecture handouts:

  • (4) Automobile insurance fraud [pdf]
  • (?) 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).