L’insegnamento ha lo scopo di presentare gli elementi fondamentali della teoria dei grafi per arrivare allo studio di modelli matematici che descrivono dinamiche su network sia di tipo deterministico che aleatorio. Vengono descritti gli elementi di base della teoria dei grafi topologica e algebrica la teoria delle matrici stocastiche e alcuni elementi dei processi Markoviani Vengono poi considerati modelli di dinamiche su grafi sia deterministiche che probabilistiche. Sono infine discusse varie applicazioni: algoritmi su reti per stime e inferenze distribuite, modelli per la dinamica delle opinioni e modelli epidemici, modelli di teoria dei giochi.

Conoscenze di: - elementi di base della teoria (topologica e algebrica) dei grafi diretti e indiretti con particolare enfasi sui concetti di centralità, connettività, periodo di un nodo, flussi su rete; - teoria delle matrici stocastiche e sub-stocastiche, delle loro proprietà spettrali e del loro uso nei modelli matematici deterministici e stocastici per dinamiche su reti; - nozioni fondamentali di ottimizzazione convessa di flussi su rete, della teoria dei giochi competitivi e delle relative dinamiche evolutive; - principali modelli di grafi aleatori e delle loro proprietà elementari. Capacità di: - costruire e comparare modelli matematici per sistemi interconnessi che nascono in reti sociali, economiche, biologiche e infrastrutturali; - applicare nozioni di base della teoria dei grafi topologica e algebrica, dei processi di Markov, della teoria dei giochi e dei sistemi dinamici per analizzare le reti ed i sistemi dinamici definiti su di esse; - individuare e valutare proprietà delle reti quali centralità, connettività, comportamenti emergenti, scalabilità; - costruire algoritmi di tipo cooperativo su reti, di valutarne la velocità di convergenza e la complessità e di implementarli su moderne piattaforme per la simulazione numerica.

E’ richiesta la conoscenza delle nozioni fondamentali di algebra lineare, probabilità e analisi matematica.

1. Teoria dei grafi (topologica e algebrica) - Elementi di teoria dei grafi: cammini, cicli, connettività, distanza, diametro. Esempi. Grafi indiretti: proprietà ed esempi (completo, alberi, ciclo, griglie). Proprietà combinatorie degli alberi. Grafi bipartiti e loro proprietà. Circuiti euleriani. Componenti connesse di un grafo e concetto di condensation graph. Periodo di un nodo. Caratterizzazione dell'aperiodicità e relative proprietà. - Matrice dei pesi di un grafo e sue potenze. Matrici di grafi aperiodici. Matrice stocastica e Laplaciano associati ad un grafo. Il teorema di Perron-Frobenius. Proprietà spettrale delle matrici stocastiche. Centralità (degree, eigenvector, Bonacich, Pagerank, Katz). - Matrici stocastiche reversibili. Forma di Dirichlet. Formulazione variazionale per il calcolo del secondo autovalore di una matrice reversibile. Conduttanza e stima di Cheeger. Esempi. - Connettività e flussi su rete: teorema di Menger e teorema del massimo flusso / minimo taglio. 2. Dinamiche averaging e di flusso lineari - Modello di averaging distribuito e sistemi compartimentali per reti chiuse e con ingressi esogeni. - Teoremi di convergenza, ruolo della centralità, matrici bi-stocastiche. - Applicazioni: stima distribuita su reti, algoritmo Metropolis, dinamiche di opinioni (modello di De Groot), saggezza delle folle, modelli di influenza in reti sociali, dinamiche lineari di flusso su rete, algoritmi distribuiti per il calcolo della centralità. - Stima dei tempi di convergenza per matrici stocastiche reversibili: ruolo del secondo autovalore. Spettro di matrici circolanti e prodotto di Kronecker di matrici. Calcolo di spettri di matrici associate a grafi notevoli: grafo completo, anelli, griglie, ipercubi, stelle. - Matrici sub-stocastiche e loro proprietà. Velocità di convergenza per averaging distribuito e sistemi compartimentali con ingressi. - Sistemi dinamici positivi e monotoni: definizione e proprietà di base. 4. Catene di Markov - Richiami sui processi Markoviani a tempo discreto: stati assorbenti, tempi e probabilità di assorbimento, tempi di ritorno, teorema di Kac, catene ergodiche, misure invarianti. - Esempi notevoli: catene reversibili e catene di nascita e morte, cammini casuali su grafi. Processi di ramificazione (Galton-Watson): probabilità di estinzione, soglia di criticità, processi supercritici e subcritici. - Processi markoviani a tempo continuo e loro rappresentazioni, processi di nascita e morte a tempo continuo, equazioni di Kolmogorov, distribuzioni invarianti ed equazioni di bilancio. - Coupling, distanza variazionale, mixing time. 5. Ottimizzazione di flussi su reti - Ottimizzazione di flussi su reti con costi convessi separabili: condizioni necessarie e sufficienti per ottimalità, dualità, interpretazione dei moltiplicatori di Lagrange come costi marginali - Reti elettriche: interpretazione delle leggi di Ohm e Kirchoff, nozione di resistenza effettiva, principio variazionale di Rayleigh. Applicazioni alle catene di Markov reversibili e ai modelli di influenza su reti sociali indirette. - Ottimizzazione del traffico su rete: ottimo di sistema, equilibrio di Wardrop, prezzo di anarchia, uso di incentivi e disincentivi. Applicazioni alle reti di trasporto. 6. Teoria evolutiva dei giochi - Introduzione alla teoria dei giochi non cooperativi. Giochi in forma strategica, nozione di best response, strategie dominanti, equilibri di Nash. Esempi classici. - Giochi potenziali, giochi di congestione. - Giochi su reti. Esempi: majority, minority, colorazione di grafi. - Analisi delle dinamiche best response e noisy best response. 7. Modelli epidemici e di interazione a coppie - Modelli di interazione di tipo pairwise. - Algoritmi gossip di averaging. - Modelli epidemici (SI, SIS, SIR), voter model. - Calcolo di probabilità e tempi di assorbimento su topologie semplici (completo, linea, stella). - Modelli ergodici (noisy voter model, SIS con mutazioni spontanee). 8. Limiti di campo medio - Modelli di interazione su grafi completi con matrice di transizione di tipo anonimo. Esempi. Processo delle frequenze empiriche. - Limite idrodinamico: Teorema di Kurtz e descrizione deterministica tramite ODE. - Limite idrodinamico di modelli binari: voter, SIS, majority, k-majority. - Modelli ergodici: la relazione tra misura invariante e punti di equilibrio della ODE. - Esempi multidimensionali: SIR, SIRS. Modelli eterogenei. 9. Grafi aleatori - Grafo aleatorio di Erdos-Renyi: definizione, proprietà elementari, distribuzione dei gradi, approssimazione con il processo di ramificazione, soglia di connettività, soglia per l’esistenza di una componente gigante. - Modello di grafo casuale con distribuzione dei gradi assegnata (configuration model): proprietà elementari, approssimazione con il processo di ramificazione, soglie per connessione ed esistenza di una componente gigante. - Modelli avanzati di grafi aleatori: preferential attachment, small world. - Limite idrodinamico per dinamiche senza memoria su grafi aleatori con distribuzione dei gradi fissata.

Il corso include lezioni che coprono gli aspetti più teorici ed esercitazioni in aula che preparano gli studenti alla risoluzioni di esercizi e problemi.

Parte degli argomenti del corso saranno coperti da dispense che verranno rese disponibili agli studenti tramite il Portale della Didattica. Altri testi di riferimento sono: • D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times" AMS, 2008 (disponibile online).

Slides; Dispense; Esercizi; Video lezioni tratte da anni precedenti;

Modalità di esame: Prova orale obbligatoria; Elaborato progettuale individuale;

Exam: Compulsory oral exam; Individual project;

... La verifica dell’apprendimento consiste nelle seguenti parti: 1. Tre homework (HW1, HW2 e HW3) che vengono assegnati, rispettivamente, alla fine dei mesi di Ottobre, Novembre e Dicembre (prima delle vacanze natalizie). I primi due consistono di esercizi teorici ed applicativi ed hanno lo scopo di verificare l’assimilazione da parte dello studente delle teorie sviluppate nel modulo e a valutarne lo sviluppo delle capacità di modellizzazione matematica. Il terzo homework, oltre ad una parte strutturalmente simile ai primi due, prevede un progetto di tipo simulativo/numerico ed ha lo scopo di valutare le capacità progettuali dello studente. I tempi di consegna sono di due settimane per HW1 e HW2 e di tre per HW3. 2. Una prova orale finale che consiste di due parti: 2a) Discussione degli homework HW1, HW2, HW3 al fine di valutare la capacità critica dello studente rispetto al lavoro svolto. 2b) Presentazione da parte del candidato di un argomento teorico trattato nel corso e di eventuali relativi esempi di applicazione. L' argomento in questione viene scelto dalla commissione e comunicato al candidato, a cui vengono lasciati 30 minuti per la preparazione della risposta, e durante i quali possono essere consultati libri ed appunti. Scopo di questa seconda parte è la valutazione delle conoscenze teoriche di base acquisite e la capacità dello studente di presentarle in modo autonomo ed efficace. Punteggi: I punteggi massimi per gli homework, a seguito della discussione di cui a 2a), sono 4 per HW1 e HW2 ciascuno e di 6 per HW3. Nel caso in cui le consegne siano avvenute in ritardo i massimi scendono a 3 e 5 rispettivamente. Il punteggio massimo della prova 2b) è pari a 18. Al termine delle due prove il punteggio viene sommato: se esso è non superiore a 30, esso costituisce il voto finale, se è superiore il voto finale è 30 e lode.

Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.