31642 - RETI COMPLESSE

Anno Accademico 2017/2018

  • Docente: Daniel Remondini
  • Crediti formativi: 6
  • SSD: FIS/07
  • Lingua di insegnamento: Italiano
  • Modalità didattica: Convenzionale - Lezioni in presenza
  • Campus: Bologna
  • Corso: Laurea Magistrale in Fisica (cod. 8025)

Conoscenze e abilità da conseguire

Al termine del corso, lo studente ha una conoscenza delle principali proprietà matematiche che caratterizzano un grafo, ed ha una panoramica delle più recenti e importanti applicazioni dei modelli a network in situazioni reali, specialmente in ambito biologico. Inoltre, acquisisce competenze sui principali algoritmi utilizzati per analizzare un grafo e per implementare modelli dinamici immersi in una struttura a network di varia topologia.

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.

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 orale 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 con Octave e/o Matlab (Matlab BGL toolbox e/o octave network toolbox). 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.

Orario di ricevimento

Consulta il sito web di Daniel Remondini