INA: (Introduction to) Network Analysis

Osnutek odseka

• Izberi poglavje  

  Skrči Razširi

   

  Skrči vse Razširi vse

  Introduction to Network Analysis (INA)

  • Izberi aktivnost Course staff Lovro Šubelj (instructor)

    Course staff

    Lovro Šubelj (instructor)

  • Izberi aktivnost Course schedule The lectures and labs start on Feb...

    Course schedule

    The lectures start on Feb 19th, and the labs start on Feb 23rd, 2026. Every enrolled student can attend any labs and consultations.

    • Lectures: Thursday at 1:15pm in PR 22
    • Labs (hands-on & consultations):
    • Monday at 10:15am in PR 18
    • Monday at 12:15pm in PR 4
    • Monday at 2:15pm in PR 4
    • Tuesday at 1:15pm in PR 21
    • Office hours: by agreement in R 2.49 or on Zoom

  • Izberi aktivnost Course syllabus by week

    

    Course syllabus by week URL
  • Izberi aktivnost Outline & objective Networks or graphs are ubiquit...

    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 the 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 and information science, and (tentative) invited talks.

    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 discussions 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 of graph theory, probability theory and statistics, and linear algebra.

  • Izberi aktivnost Coursework & grading Students are expected to atte...

    Coursework & grading

    Students are expected to attend and actively participate in lectures and labs.

    The ongoing coursework will consist of two homework assignments on network analysis concepts and techniques. Each homework will require a 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. To pass the course, students must score at least 50% on the exam. The exam schedule is shown below.

    • Jun 9th, 2026 at TBA in TBA
    • Jun 19th, 2026 at TBA in TBA
    • Aug 17th, 2026 at TBA in TBA

    The course grade is based 25% on the 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.

  • Izberi aktivnost Course project overview

    

    Course project overview URL
  • Izberi aktivnost Assignments & submission All course assignments wi...

    Assignments & submission

    All course assignments will be out and due according to the 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 RVYW5D) and eUcilnica (using options below), and must include an assignment cover sheet with a signed honor code! An assignment is considered submitted only when all parts have been submitted.

  • Izberi aktivnost Literature & materials All course materials will b...

    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:210100863v3, 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).

  • Izberi aktivnost Course repository with materials

    

    Course repository with materials URL
  • Izberi aktivnost Course discussions Please use Piazza for all cours...

    Course discussions

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

  • Izberi aktivnost Questions and discussions

    

    Questions and discussions URL
• Izberi poglavje From graph theory to network science

  Skrči Razširi

  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
  • (1) From graph theory to network science
  • (6) Networks through fields of science

  Lab notebooks:

  • (ii) Recitation on NetworkX, Pajek etc.

  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).
• Izberi poglavje Random graphs vs real networks

  Skrči Razširi

  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
  • (2) Network representations and data
  • (2) Erdős-Rényi graph model
  • (3) Configuration graph model

  Lab notebooks:

  • (iii) Network representation and statistics
  • (iv) Network algorithms and random graphs

  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).
• Izberi poglavje Small-world and scale-free networks

  Skrči Razširi

  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
  • (3-4) Scale-free distributions and networks
  • (4) Preferential attachment models

  Lab notebooks:

  • (v) Small-world and scale-free models
  • (vii) Errors and attacks on the Internet

  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).
• Izberi poglavje Node mixing and network structure

  Skrči Razširi

  Node mixing and network structure

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

  Lecture handouts:

  • (9) Node mixing in networks

  Lab notebooks:

  • (xii) Node mixing by (not) degree

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