INA: (Introduction to) Network Analysis

Topic outline

• 

  Introduction to Network Analysis (INA)

  • Course staff

    • Lovro Šubelj (instructor)
      
    • Ilya Makarov (head TA)
      

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

  • Course grade will be based 30% on homeworks (10% on each homework), 35% on course project (5% on proposal and 30% on report), 30% on final exam and 5% on course challenges, participation and commitment. The final exam will be an online open-book written exam for which you register in StudIS, while selected students will also have to attend an oral exam.

  • Course assignments
    

    All course assignments will be out and due according to course syllabus, and must be submitted before Friday at 11:59pm. 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 8:00am.

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

  • 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
  • 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 handouts: 

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

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