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

Il corso 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.

Durante le lezioni vengono svolte esercitazioni al calcolatore, a titolo di esempio, per vedere implementazioni degli algoritmi trattati a lezione e specifici casi studio.

Modalità di verifica e valutazione dell'apprendimento

Verifica con lo sviluppo di un elaborato su un argomento specifico.

Lo studente deve essere capace di:

- applicare i metodi di analisi dei network appresi a lezione

- adattarli al contesto del progetto/elaborato

Strumenti a supporto della didattica

Verranno svolte esercitazioni con software per la generazione e l'analisi di network in Matlab e Python. Visualizzazione di un network: colorazione e ridimensionamento in funzione delle proprietà topologiche. 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. Case studies relativi alle attivitá di ricerca svolte.

Orario di ricevimento

Consulta il sito web di Daniel Remondini

Consulta il sito web di Francesco Durazzi