87968 - COMPLEX NETWORKS

Conoscenze e abilità da conseguire

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.

Contenuti

Programma indicativo

Introduzione alle reti complesse: esempi dalla fisica, biologia, sociologia, informatica. Esempi: caratteristiche di Internet, network in biologia

Definizione di network: grafo. Grafi semplici e bipartiti. Network pesati e non. Network diretti e non.

Caratterizzazione della topologia di un network a livello globale e di singolo nodo: distribuzione dei parametri per singolo nodo (connettività). Connettività, clustering, misure di centralità. Diametro di un network. Sottonetworks; clustering di un network; cliques e moduli. Definizione e calcolo delle principali misure del network. Metodi di clustering: Newman-Girwan.

Modello base: random networks alla Erdos-Renyi. (Analogia con i modelli di percolazione.) Distribuzione dei parametri del network e teoremi limite per N>>1. Matrici di Wigner e spettro degli autovalori. Transizione di fase e giant cluster. Relazione tra vari parametri del network (assortatività-disassortatività [modelli di MEJ Newman, Maslov-Sneppen], connettività vs. betwenness centrality).

Lattice come network: proprietà. Generalizzazione a small world networks: high clustering short distances (log(N)). Modello di Watts-Strogatz: rewiring.

Scale free networks: esempi. Modello di crescita di Barabasi-Alberts: preferential attachment. Scale log-log. Istogrammi e possibili errori (heavy tails).

Perturbazioni di un network: attack/error tolerance, node relevance & efficiency.

Meccanica statistica dei network: definizione di ensemble, constraints e network entropy.

Network e Machine Learning: node embedding framework

Sviluppo di alcuni esempi particolari: network & Sistema Immunitario, serie temporali di espressione genica, random boolean networks, metabolic networks & flux balance analysis. Esempi in modelli biologici (gerarchia: Jeong-Tombor-Barabasi, motifs: Alon).

Testi/Bibliografia

Dispense e articoli proposti dal docente.

LIBRI

- 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

Metodi didattici

Modulo 1: Il modulo consiste di lezioni frontali dove vengono spiegati concetti della teoria dei network e metodi analisi basate su di essa, con alcuni esempi pratici in network reali.

Modulo 2: In questo modulo agli studenti verrà mostrato come applicare computazionalmente i concetti del modulo 1, con esempi tratti da: generazione di modelli nulli, misure di centralità, diffusione su network, graph neural networks e modelli dinamici. Le lezioni saranno laboratori hands-on, in cui gli studenti potranno eseguire e modificare Jupyter notebooks scritti in Python dal docente.

 

Modalità di verifica e valutazione dell'apprendimento

Progetto computazionale (individuale o gruppo di massimo 3 persone). Agli studenti è richiesto di realizzare un progetto computazionale in cui applichino i metodi di analisi dei network visti a lezione, motivandone le scelte fatte, commentando e discutendo i risultati ottenuti. Al codice scritto, andrà accompagnato un report in forma di articolo (abstract, introduzione, metodi, risultati/discussione, bibliografia). Il tema potrà essere proposto dagli studenti o scelto tra gli esempi presentati a lezione (ricapitolati durante le ultime lezioni del corso).

Progetto compilativo (individuale): analisi critica della letteratura su temi inerenti agli argomenti del corso, presentata sottoforma di report con commenti.

Non è permesso utilizzare strumenti di scrittura automatica (es chatGPT) per la preparazione del report.

Consegnato il progetto, i docenti potranno richiedere ulteriori analisi o approfondimenti per completare l'esame.

Strumenti a supporto della didattica

Verranno svolte esercitazioni con software in linguaggio Matlab e Python.

Esempi: visualizzazione di un network; calcolo dei principali parametri del network; principali formati di file I/O; crescita di un network e transizione di fase per la formazione del Giant Cluster; generazione di classi di networks; case studies relativi alle tematiche del corso.

Orario di ricevimento

Consulta il sito web di Daniel Remondini

Consulta il sito web di Francesco Durazzi