Verranno presentati alcuni elementi più avanzati della teoria dei grafi e vari modelli matematici che descrivono dinamiche su grafi sia deterministiche che probabilistiche. Saranno discusse varie applicazioni: algoritmi su reti per stime e inferenze distribuite, dinamiche di agenti mobili, modelli per la dinamica delle opinioni e modelli epidemici

Conoscenza di elementi di base della teoria dei grafi diretti
Conoscenza della teoria delle matrici stocastiche e substocastiche e delle loro proprietà spettrali.
Conoscenza degli elementi di base delle catene di Markov, delle catene reversibili e del metodo dell’analogia elettrica.
Capacità di costruire modelli matematici che descrivono dinamiche su reti e che hanno utilizzi dalla robotica, all’inferenza statistica, allo studio di modelli socio-economici.
Capacità di analizzare le prestazioni di un algoritmo distribuito su una rete, la sua complessità e la sua velocità di convergenza con particolare riferimento alle proprietà di scalabilità rispetto al numero di nodi nel grafo.

Sono richieste le nozioni di base su insiemi e funzioni, i fondamenti del calcolo in una variabile, dell’algebra lineare e della probabilità elementare.

Grafi diretti, cammini, circuiti, cicli. Connessione e forte connessione. Periodo di un nodo, grafi aperiodici. Componenti connesse e grafo di condensazione.
Laplaciano di grafi, forma di Dirichlet, funzioni armoniche.
Matrici stocastiche e loro utilizzo nelle dinamiche di consenso. Convergenza per le potenze di una matrice stocastica. Proprietà spettrali. Diseguaglianza di Cheeger
Grafi come circuiti elettrici e collegamento con le matrici stocastiche reversibili.
Applicazioni: algoritmi per la stima distribuita, dinamiche di opinione.
Elementi della teoria delle catene di Markov. Probabilità invarianti. Stati assorbenti. Comportamenti transienti e asintotici.
Modelli ad agenti interagenti. Dinamiche gossip. Modelli per la diffusione delle epidemie. Modelli per la dinamica delle opinioni.
L’approssimazione di campo medio.
Dinamiche su alberi. Processi di ramificazione. Modelli soglia

Durante il corso verranno discussi e svolti dai docenti numerosi esercizi, che copriranno tutti gli argome

D. A. Levin, Y. Peres, E. L. Wilmer, “Markov chains and mixing times" AMS, 2008 (disponibile online).

L’esame consiste di una prova scritta con esercizi e domande teoriche. Alcune parti dell’esame potranno essere preventivamente superate durante il corso tramite lavori individuali di tipo homework ed in tal modo eliminate dalla prova scritta finale.