87968 - Complex Networks

Learning outcomes

At the end of the course the student will acquire knowledge about the main mathematical properties characterizing a network and he/she will an overview of the most recent and important applications of network models to real situations, in particular related to biology. He/she will be able to master and apply the main algorithms for graph analysis and for implementing dynamical models embedded in networks of different topological structure.

Course contents

Introduction to complex networks: examples from physics, biology, informatics.

Definition of a network: graph. Simple and bipartite graphs. Weighted/unweighted, directed/undirected networks.

Characterization of global network topology and single-node features: single-node parameter distribution. Connectivity degree, clustering, centrality measures. Network diameter. Subnetworks: clustering, cliques and modules. Definition and calculations of the main network features. Clustering methods. Laplacian of a network.

Erdos-Renyi random networks: parameter distribution and limit theorems (N>>1). Wigner matrices and eigenvalue spectrum. Giant cluster phase transition. Relations between parameters (e.g. assortativity/mixing, connectivity degree and betweenness centrality).

Lattices: properties and examples. Generalization to small-world networks: Watts-Strogatz model.

Scale-free networks: examples. Preferential attachmenet growth rules and dynamics.

Network perturbations: attack/error tolerance, node relevance, efficiency.

Statistical mechanics of networks: definition of ensembles, constraints, network entropy.

Network & Machine Learning: node embedding framework

Applications: Immune System network hierarchy, gene expression time series, metabolic networks and flux balance analysis. Examples in biological models (hierarchy, motifs).

Readings/Bibliography

Selected papers and lecture slides.

BOOKS

- Networks: an introduction (Newman, Oxford)

- Large Scale Structure And Dynamics Of Complex Networks – vol. 2

(Caldarelli Vespignani Eds.) – World Press

- Dynamical processes on complex network

(Barrat Barthelemy Vespignani) – Cambridge press 2008

Teaching methods

Module 1: The module consists of lectures where concepts of network theory and analysis methods based on it are explained, with some practical examples in real networks.

Module 2: In this module, students will be shown how to computationally apply the concepts of module 1, with examples from: null model generation, centrality measures, diffusion on networks, graph neural networks and dynamic models. The lectures will be hands-on laboratories, where students will be able to run and modify Jupyter notebooks written in Python by the teacher.

Assessment methods

Computational project (individual or group of up to 3 people). Students are required to create a computational project in which they apply the network analysis methods seen in class, justifying the choices made, commenting and discussing the results obtained. The written code must be accompanied by a report in the form of an article (abstract, introduction, methods, results/discussion, bibliography). The topic can be proposed by the students or chosen from the examples presented in class (recapitulated during the last lessons of the course).

Compilative project (individual): critical analysis of the literature on topics related to the topics of the course, presented in the form of a report with comments.

It is not permitted to use automatic writing tools (e.g. chatGPT) to prepare the report.

Once the project has been submitted, teachers may request further analysis or insights to complete the exam.

Teaching tools

Exercises will be carried out with software in Matlab and Python languages.

Examples: visualization of a network; calculation of the main parameters of the network; main I/O file formats; growth of a network and phase transition for the formation of the Giant Cluster; generation of networks of different types; case studies related to the topics of the course.

Office hours

See the website of Daniel Remondini

See the website of Francesco Durazzi