Skip to main content

Graph Algorithms (MDA I level)

Hours
15
CFU
3

Syllabus

This course aims at providing students with an understanding of graph models and algorithms, taking a practical perspective focused on the analysis of complex systems through their network representation. Through examples and exercises, the students will learn how to extract a network representation from information contained in the data and how to analyze the obtained graph to

gain valuable knowledge about the system under study.

The course will cover all the main topics of network theory, including:

  • Network representation (adjacency matrix, adjacency lists, efficient representations for sparse graphs, …)
  • Measures and metrics (centrality, transitivity, assortativity, …)
  • Algorithms (shortest paths, DFS, BFS, Dijkstra, …)
  • Properties of real-world networks (small-world effect, scale-free networks, assortative mixing, …)
  • Graph models (random graphs, configuration model, preferential attachment, …)
  • Community structure (spectral clustering, modularity maximization, …)
  • Dynamic processes on networks (percolation, epidemic spreading, …)

The course will make use of Python and, in particular, of the Python interface to the igraph library.

REFERENCE BOOK: Mark Newman, “Networks (2nd Edition)”, Oxford University Press