Servizi per la didattica
PORTALE DELLA DIDATTICA

Processi stocastici/Dinamiche su network

01RMING

A.A. 2018/19

2018/19

Processi stocastici/Dinamiche su network (Dinamiche su Network)

L’insegnamento ha lo scopo di presentare gli elementi fondamentali dei processi stocastici e della teoria dei grafi per arrivare allo studio di modelli matematici che descrivono dinamiche su network sia di tipo deterministico che aleatorio. Vengono descritti i principali processi stocastici a tempo discreto e continuo con particolare attenzione alle loro applicazioni ingegneristiche, gli elementi di base della teoria dei grafi topologica e algebrica e la teoria delle matrici stocastiche. Vengono poi considerati modelli di dinamiche su grafi sia deterministiche che probabilistiche. Sono infine discusse varie applicazioni: teoria delle code, algoritmi su reti per stime e inferenze distribuite, modelli per la dinamica delle opinioni e modelli epidemici, modelli di teoria dei giochi.

Processi stocastici/Dinamiche su network (Processi stocastici)

L’insegnamento ha lo scopo di presentare gli elementi fondamentali dei processi stocastici e della teoria dei grafi per arrivare allo studio di modelli matematici che descrivono dinamiche su network sia di tipo deterministico che aleatorio. Vengono descritti i principali processi stocastici a tempo discreto e continuo con particolare attenzione alle loro applicazioni ingegneristiche, gli elementi di base della teoria dei grafi topologica e algebrica e la teoria delle matrici stocastiche. Vengono poi considerati modelli di dinamiche su grafi sia deterministiche che probabilistiche. Sono infine discusse varie applicazioni: teoria delle code, algoritmi su reti per stime e inferenze distribuite, modelli per la dinamica delle opinioni e modelli epidemici, modelli di teoria dei giochi.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

This course aims at presenting the foundations of stochastic processes and graph theory and their applications in the mathematical modelling of network dynamics. The course covers stochastic processes both in discrete and continuous time with special focus on their engineering applications, the foundations of both algebraic and topological graph theories, and the theory of stochastic matrices. It then focuses on both deterministic and stochastic dynamical processes on graphs. Finally, it introduces the student to several applications: queuing theory, distributed inference algorithms, opinion dynamics, epidemics models, game theory and learning.

Processi stocastici/Dinamiche su network (Processi stocastici)

This course aims at presenting the foundations of stochastic processes and graph theory and their applications in the mathematical modelling of network dynamics. The course covers stochastic processes both in discrete and continuous time with special focus on their engineering applications, the foundations of both algebraic and topological graph theories, and the theory of stochastic matrices. It then focuses on both deterministic and stochastic dynamical processes on graphs. Finally, it introduces the student to several applications: queuing theory, distributed inference algorithms, opinion dynamics, epidemics models, game theory and learning.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

Conoscenze di: - elementi teorici di base dei processi stocastici e delle loro principali caratteristiche e proprietà; - 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: - riconoscere i processi stocastici idonei a modellare sistemi dinamici caratterizzati da evoluzioni non-deterministiche; - analizzare modelli stocastici dinamici, e di descrivere grandezze aleatorie ad essi riferibili, quali tempi di attesa o di raggiungimento di stati assorbenti, o condizioni di stazionarietà e relative distribuzioni; - 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.

Processi stocastici/Dinamiche su network (Processi stocastici)

Conoscenze di: - elementi teorici di base dei processi stocastici e delle loro principali caratteristiche e proprietà; - 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: - riconoscere i processi stocastici idonei a modellare sistemi dinamici caratterizzati da evoluzioni non-deterministiche; - analizzare modelli stocastici dinamici, e di descrivere grandezze aleatorie ad essi riferibili, quali tempi di attesa o di raggiungimento di stati assorbenti, o condizioni di stazionarietà e relative distribuzioni; - 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.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

Knowledge of: - Elements of stochastic processes and their main properties - Elements of algebraic and topological graph theory with special emphasis on centrality, connectivity, periodcity of a node, and network flows. - Nonnegative matrix theory (stochastic and substochastic matrices), their spectral properties, and their use in the mathematical modelling of deterministic and stochastic network dynamics. - Basics of convex network flow optimization, game theory, and related evolutionary dynamics. - Basic models of random graphs and their fundamental properties Ability to: - Identify and select the proper stochastic processes to model non-deterministic system dynamics. - Analyze stochastic dynamical models and their main associated random variables, such as waiting and absorbing times, as well as stationarity conditions and related distributions. - Construct and compare mathematical models for interconnected systems arising in social, economic, biological, and infrastructure networks. - Apply basic notions of algebraic and totpological graph theory, Markov processes, game theory, and dynamical systems in order to analyze networks and interconnected dynamical systems. - Critically identify and evaluate network properties such as centrality, connectivity, emerging behaviors, and scalability. - Design and propose cooperative distributed algorithms on networks, to evaluate their asymptotics, speed of convergence, and complexity, and to implement them on modern platforms for numerical simulation.

Processi stocastici/Dinamiche su network (Processi stocastici)

Knowledge of: - Elements of stochastic processes and their main properties - Elements of algebraic and topological graph theory with special emphasis on centrality, connectivity, periodcity of a node, and network flows. - Nonnegative matrix theory (stochastic and substochastic matrices), their spectral properties, and their use in the mathematical modelling of deterministic and stochastic network dynamics. - Basics of convex network flow optimization, game theory, and related evolutionary dynamics. - Basic models of random graphs and their fundamental properties Ability to: - Identify and select the proper stochastic processes to model non-deterministic system dynamics. - Analyze stochastic dynamical models and their main associated random variables, such as waiting and absorbing times, as well as stationarity conditions and related distributions. - Construct and compare mathematical models for interconnected systems arising in social, economic, biological, and infrastructure networks. - Apply basic notions of algebraic and totpological graph theory, Markov processes, game theory, and dynamical systems in order to analyze networks and interconnected dynamical systems. - Critically identify and evaluate network properties such as centrality, connectivity, emerging behaviors, and scalability. - Design and propose cooperative distributed algorithms on networks, to evaluate their asymptotics, speed of convergence, and complexity, and to implement them on modern platforms for numerical simulation.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

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

Processi stocastici/Dinamiche su network (Processi stocastici)

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

Processi stocastici/Dinamiche su network (Dinamiche su Network)

Basic knowledge of linear algebra, probability theory and calculus is a prerequisite.

Processi stocastici/Dinamiche su network (Processi stocastici)

Basic knowledge of linear algebra, probability theory and calculus is a prerequisite.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

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. 3. Introduzione ai Processi stocastici - Definizione di processi stocastici e loro principali caratterizzazioni e proprietà. - Filtrazioni e tempi di arresto. - Martingale a tempo discreto e relative proprietà. Decomposizione di supermartingale e submartingale. Teorema di Doob, convergenza. - Processi ad incrementi stazionari ed incrementi indipendenti. - Moti browniani: definizione, proprietà notevoli, esempi di applicazione. - Processi di Poisson: definizioni equivalenti, risultati notevoli, loro generalizzazioni (non-omogenei, composti, mixed). 4. Catene di Markov - Processi markoviani a tempo discreto e loro proprietà, matrici di transizione, equazioni di Chapman-Kolmogorov, classificazione degli stati, convergenza in distribuzione e teorema ergodico per catene irriducibili, esistenza e unicità di distribuzioni invarianti. - Tempi medi e probabilità di raggiungimento di stati assorbenti per catene di Markov, tempi di ritorno e teorema di Kac. Ruolo della matrice fondamentale. - 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. - Dominanze stocastiche del I e del II ordine e loro applicazioni nello studio del comportamento asintotico di catene di Markov. 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.

Processi stocastici/Dinamiche su network (Processi stocastici)

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. 3. Introduzione ai Processi stocastici - Definizione di processi stocastici e loro principali caratterizzazioni e proprietà. - Filtrazioni e tempi di arresto. - Martingale a tempo discreto e relative proprietà. Decomposizione di supermartingale e submartingale. Teorema di Doob, convergenza. - Processi ad incrementi stazionari ed incrementi indipendenti. - Moti browniani: definizione, proprietà notevoli, esempi di applicazione. - Processi di Poisson: definizioni equivalenti, risultati notevoli, loro generalizzazioni (non-omogenei, composti, mixed). 4. Catene di Markov - Processi markoviani a tempo discreto e loro proprietà, matrici di transizione, equazioni di Chapman-Kolmogorov, classificazione degli stati, convergenza in distribuzione e teorema ergodico per catene irriducibili, esistenza e unicità di distribuzioni invarianti. - Tempi medi e probabilità di raggiungimento di stati assorbenti per catene di Markov, tempi di ritorno e teorema di Kac. Ruolo della matrice fondamentale. - 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. - Dominanze stocastiche del I e del II ordine e loro applicazioni nello studio del comportamento asintotico di catene di Markov. 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.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

1. Topological and algebraic graph theory - Basics in graph theory: paths, cycles, connectivity, distance, diameter. Undirected graphs: properties and examples (complete, trees, cycle, grids). Combinatorial properties of trees. Bipartite graphs and their properties. Eulerian circuits. Connected components of a graph and the concept of condensation graph. Period of a node. Characterization of aperiodicity and related properties. - Weight matrix of a graph and its powers. Matrices associated with aperiodic graphs. Stochastic matrix and Laplacian associated to a graph. Perron-Frobenius theorem. Spectral properties of stochastic matrices. Centrality (degree, eigenvector, Bonacich, Page-rank, Katz). - Reversible stochastic matrices. Dirichlet form. Variational characterization of the second eigenvalue of a reversible matrix. Conductance and Cheeger bound. Example. - Connectivity and flows on a network: Menger’s theorem, max-flow/min-cut theorem. 2. Averaging and linear flow dynamics - Distributed averaging and compartmental systems for closed networks and for networks with exogeneous inputs. - Convergence theorems, role of centrality, bi-stochastic matrices. - Applications: distributed estimation on a network, Mteorpolis algorithm, opinion dynamics (De Groot model), wisdom of crowds, influential models for social networks, linear flow dynamics, distribued algorithms for computing centrality. - Bounds on convergence times for reversible stochastic matrices: role of the second eigenvalue. Spectra of circulant matrices and Kronecker products. Exlicit computation of spectra for notable graphs: complete, cycles, grids, hypercubes, stars. - Sub-stochastic matrices and their properties. Speed of convergence for distributed averaging and compartmental systems with inputs. - Positive and monotone dynamical systems: definition and basic properties. 3. Introduction to stochastic processes - Definition of a stochastic process and discussion of its main characterizations and properties. - Filtrations and stopping times. -Discrete time martngale and related properties. Decomposition of supermartingales and submartingales. Doob’s theorem, convergence. - Processes with stationary increments and with independent increments. - Brownian motions: definition, main properties, applications. - Poisson processes: equivalent definitions, main results, generalizations (non-homogeneous, composed, mixed). 4. Markov chains - Discrete time Markov processes and their properties, transition matrices, Chapman-Kolmogorov equations, classification of states, convergence in law and ergodic theorem for irreducible chains. Unicity of the invariant distribution. - Mean hitting times and hitting probabilities of absorbing states, return times and Kac’s theorem. Role of the fundamental matrix. - Notable examples: reversible chains and birth and death chains, random walks on graphs. Branching processes: extinction probabilities, critical threshold, supercritical and subcritical processes. - Continuous time Markov processes and their representations, continuous time birth and death processes, Kolmogorov equations, invariant distributions, balance equations. - Coupling, variational distance, mixing time. - Stochastic domination of I and II order. Application to the study of the asymptotic behavior of Markov chains. 5. Optimization of network flows - Optimization of network flows with separable convex costs, necessary and sufficient conditions for optimality, duality, interpretation of Lagrange multipliers as marginal costs. - Electrical networks: interpretation of Ohm and Kirchoff laws, effective resistance, Rayleigh’s variational principle. Application to reversible Markov chains and to influential models on social undirected networks. - Optimization of network flows: system optimum, Wardrop equilibrium, price of anarchie, use of incentives and disincentives. Application to transportation newtorks. 6. Evolutionary game theory - Introduction to non-cooperative game theory. Games in strategic form, best response, dominant strategies, Nash equilibria. Classical examples. - Potential and congestion games. - Network games. Examples: majority, minority, graph coloring. - Analysis of best response and noisy best response dynamics. 7. Epidemics and pairwise interacting models. - Pairwise interacting models: general definition and properties. - Averaging gossip algorithms. - Epidemic models (SI, SIS, SIR), voter model. - Computation of the absorbing times and absorbing probabilities for simple topologies (complete, line, star). - Ergodic models (noisy voter model, SIS with spontaneous mutation). 8. Mean field limits - Interaction models on a complete graph with anonymous transition matrix. Examples. Process of empirical frequencies. - Hydrodynamic limit: Kurtz’s theorem and the limit ODE - Hydrodynamic limit of binary models: voter, SIS, majority, k-majority. - Ergodic models: relation between the invariant distribution and the equilibria of the corresponding ODE. - Multi-dimensional examples: SIR, SIRS, heterogeneous models. 9. Random graphs - Erdos-Renyi random graph: definition, properties, degree distribution, branching process approximation, connectivity threshold, threshold for the existence of a giant component. - Random graphs with preassigned degree distribution (configuration model): elementary properties, branching process approximation, threshold for connectivity and for the existence of a giant component - Other random graph models: preferential attchment, small world. - Hydrodynamic limit of memoryless dynamics on random graphs with preassigned degree distribution.

Processi stocastici/Dinamiche su network (Processi stocastici)

1. Topological and algebraic graph theory - Basics in graph theory: paths, cycles, connectivity, distance, diameter. Undirected graphs: properties and examples (complete, trees, cycle, grids). Combinatorial properties of trees. Bipartite graphs and their properties. Eulerian circuits. Connected components of a graph and the concept of condensation graph. Period of a node. Characterization of aperiodicity and related properties. - Weight matrix of a graph and its powers. Matrices associated with aperiodic graphs. Stochastic matrix and Laplacian associated to a graph. Perron-Frobenius theorem. Spectral properties of stochastic matrices. Centrality (degree, eigenvector, Bonacich, Page-rank, Katz). - Reversible stochastic matrices. Dirichlet form. Variational characterization of the second eigenvalue of a reversible matrix. Conductance and Cheeger bound. Example. - Connectivity and flows on a network: Menger’s theorem, max-flow/min-cut theorem. 2. Averaging and linear flow dynamics - Distributed averaging and compartmental systems for closed networks and for networks with exogeneous inputs. - Convergence theorems, role of centrality, bi-stochastic matrices. - Applications: distributed estimation on a network, Mteorpolis algorithm, opinion dynamics (De Groot model), wisdom of crowds, influential models for social networks, linear flow dynamics, distribued algorithms for computing centrality. - Bounds on convergence times for reversible stochastic matrices: role of the second eigenvalue. Spectra of circulant matrices and Kronecker products. Exlicit computation of spectra for notable graphs: complete, cycles, grids, hypercubes, stars. - Sub-stochastic matrices and their properties. Speed of convergence for distributed averaging and compartmental systems with inputs. - Positive and monotone dynamical systems: definition and basic properties. 3. Introduction to stochastic processes - Definition of a stochastic process and discussion of its main characterizations and properties. - Filtrations and stopping times. -Discrete time martngale and related properties. Decomposition of supermartingales and submartingales. Doob’s theorem, convergence. - Processes with stationary increments and with independent increments. - Brownian motions: definition, main properties, applications. - Poisson processes: equivalent definitions, main results, generalizations (non-homogeneous, composed, mixed). 4. Markov chains - Discrete time Markov processes and their properties, transition matrices, Chapman-Kolmogorov equations, classification of states, convergence in law and ergodic theorem for irreducible chains. Unicity of the invariant distribution. - Mean hitting times and hitting probabilities of absorbing states, return times and Kac’s theorem. Role of the fundamental matrix. - Notable examples: reversible chains and birth and death chains, random walks on graphs. Branching processes: extinction probabilities, critical threshold, supercritical and subcritical processes. - Continuous time Markov processes and their representations, continuous time birth and death processes, Kolmogorov equations, invariant distributions, balance equations. - Coupling, variational distance, mixing time. - Stochastic domination of I and II order. Application to the study of the asymptotic behavior of Markov chains. 5. Optimization of network flows - Optimization of network flows with separable convex costs, necessary and sufficient conditions for optimality, duality, interpretation of Lagrange multipliers as marginal costs. - Electrical networks: interpretation of Ohm and Kirchoff laws, effective resistance, Rayleigh’s variational principle. Application to reversible Markov chains and to influential models on social undirected networks. - Optimization of network flows: system optimum, Wardrop equilibrium, price of anarchie, use of incentives and disincentives. Application to transportation newtorks. 6. Evolutionary game theory - Introduction to non-cooperative game theory. Games in strategic form, best response, dominant strategies, Nash equilibria. Classical examples. - Potential and congestion games. - Network games. Examples: majority, minority, graph coloring. - Analysis of best response and noisy best response dynamics. 7. Epidemics and pairwise interacting models. - Pairwise interacting models: general definition and properties. - Averaging gossip algorithms. - Epidemic models (SI, SIS, SIR), voter model. - Computation of the absorbing times and absorbing probabilities for simple topologies (complete, line, star). - Ergodic models (noisy voter model, SIS with spontaneous mutation). 8. Mean field limits - Interaction models on a complete graph with anonymous transition matrix. Examples. Process of empirical frequencies. - Hydrodynamic limit: Kurtz’s theorem and the limit ODE - Hydrodynamic limit of binary models: voter, SIS, majority, k-majority. - Ergodic models: relation between the invariant distribution and the equilibria of the corresponding ODE. - Multi-dimensional examples: SIR, SIRS, heterogeneous models. 9. Random graphs - Erdos-Renyi random graph: definition, properties, degree distribution, branching process approximation, connectivity threshold, threshold for the existence of a giant component. - Random graphs with preassigned degree distribution (configuration model): elementary properties, branching process approximation, threshold for connectivity and for the existence of a giant component - Other random graph models: preferential attchment, small world. - Hydrodynamic limit of memoryless dynamics on random graphs with preassigned degree distribution.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

Processi stocastici/Dinamiche su network (Processi stocastici)

Processi stocastici/Dinamiche su network (Dinamiche su Network)

Processi stocastici/Dinamiche su network (Processi stocastici)

Processi stocastici/Dinamiche su network (Dinamiche su Network)

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

Processi stocastici/Dinamiche su network (Processi stocastici)

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

Processi stocastici/Dinamiche su network (Dinamiche su Network)

Theoretical lectures and practice classes. Theoretical lectures are devoted to the presentation of the topics, with definitions, properties, introductory examples, as well as a number of selected proofs which are believed to facilitate the learning process. The practice classes are devoted to train the students’ abilities to solve problems and exercises.

Processi stocastici/Dinamiche su network (Processi stocastici)

Theoretical lectures and practice classes. Theoretical lectures are devoted to the presentation of the topics, with definitions, properties, introductory examples, as well as a number of selected proofs which are believed to facilitate the learning process. The practice classes are devoted to train the students’ abilities to solve problems and exercises.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

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: • S. N. Ross, “Stochastic Processes”, 2nd Edition, Wiley, 1996. • J. Jacod and P. Protter, “Probability Essentials”, Springer, 2000. • D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times" AMS, 2008 (disponibile online).

Processi stocastici/Dinamiche su network (Processi stocastici)

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: • S. N. Ross, “Stochastic Processes”, 2nd Edition, Wiley, 1996. • J. Jacod and P. Protter, “Probability Essentials”, Springer, 2000. • D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times" AMS, 2008 (disponibile online).

Processi stocastici/Dinamiche su network (Dinamiche su Network)

Part of the course topics are covered by lecture notes that will be made available to the students through the Portale della Didattica. Other reference texts are: - S.N. Ross, Stochastic Processes, 2nd Edition, Wiley. - J. Jacod and P. Protter, Probability Essentials, Springer, 2000 - D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times" AMS, 2008 (online available). Other material will be suggested in class and made avalaible thorugh the Portale della Didattica.

Processi stocastici/Dinamiche su network (Processi stocastici)

Part of the course topics are covered by lecture notes that will be made available to the students through the Portale della Didattica. Other reference texts are: - S.N. Ross, Stochastic Processes, 2nd Edition, Wiley. - J. Jacod and P. Protter, Probability Essentials, Springer, 2000 - D. A. Levin, Y. Peres, E. L. Wilmer, "Markov chains and mixing times" AMS, 2008 (online available). Other material will be suggested in class and made avalaible thorugh the Portale della Didattica.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

Modalità di esame: prova orale obbligatoria; elaborato scritto individuale;

Processi stocastici/Dinamiche su network (Processi stocastici)

Modalità di esame: prova scritta; prova orale obbligatoria; progetto individuale;

Processi stocastici/Dinamiche su network (Dinamiche su Network)

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 due argomenti teorici trattati nel corso e loro eventuali esempi di applicazione. Gli argomenti in questione vengono scelti dalla commissione e comunicati al candidato, a cui vengono lasciati 30 minuti (per ciascuno dei due temi indicati) 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.

Processi stocastici/Dinamiche su network (Processi stocastici)

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 due argomenti teorici trattati nel corso e loro eventuali esempi di applicazione. Gli argomenti in questione vengono scelti dalla commissione e comunicati al candidato, a cui vengono lasciati 30 minuti (per ciascuno dei due temi indicati) 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.

Processi stocastici/Dinamiche su network (Dinamiche su Network)

Exam: compulsory oral exam; individual essay;

Processi stocastici/Dinamiche su network (Processi stocastici)

Exam: written test; compulsory oral exam; individual project;

Processi stocastici/Dinamiche su network (Dinamiche su Network)

The assessment consists of two parts: 1. Three homework assignments (HW1, HW2, HW3) that will be assigned to the students towards the end of October, November, and December (before Christmas break), respectively. HW1 and HW2 consist of exercises that are aimed at assessing the students’ achieved learning level of the theoretical aspects and their ability to select relevant principles to solve the proposed problems. In addition to an exercise part of the same nature as in HW1 and HW2, the HW3 assignment includes a small project that involves numerical simulations as well as deductive and analytical reasonings and is aimed at testing the mathematical modelling abilities of the students and their ability to present their analyses and results in a proper format of a written report such that a technically qualified person can follow and obtain similar findings. Students will have two weeks each to submit their HW1 and HW2 reports, and three weeks to submit their HW3 report. 2. An oral test consisting of two parts: (2a) a discussion of the submitted HW1, HW2, and HW3 reports, aimed at testing the depth of the students’ understanding of the subjects and their ability to explain, defend, reflect, critically evaluate, and possibly improve their work; (2b) a presentation of two topics studied in the course covering both theoretical aspects and possibly their applications. The two topics are chosen by the examination committee and communicated to the student, who has 30 minutes to prepare her/his presentation: during this time the student has access to books, notes, and other learning material. This part of the oral test is aimed at evaluating the breadth and depth of the kwoledge acquired by the student, and her/his ability to effectively present and communicate it to a technically qualified audience. Grading: the maximum grade for HW1, HW2, and HW3, upon the discussion detailed at point (2a) above, is of 4,4, and 6 points, respectively. If HW1, HW2, and HW3 are not submitted by their deadline, the maximum grades above are lowered to 3, 3, and 5 points, respectively. The maximum grade for part (2b) of the oral test is 18 points. The final course grade is then obtained by summing up the final grades in HW1, HW2, HW3, and of part (2b) of the oral test: if such sum is less than or equal to 30, the final grade coincides with it, if the sum is strictly larger than 30 the final grade is 30 cum laude.

Processi stocastici/Dinamiche su network (Processi stocastici)

The assessment consists of two parts: 1. Three homework assignments (HW1, HW2, HW3) that will be assigned to the students towards the end of October, November, and December (before Christmas break), respectively. HW1 and HW2 consist of exercises that are aimed at assessing the students’ achieved learning level of the theoretical aspects and their ability to select relevant principles to solve the proposed problems. In addition to an exercise part of the same nature as in HW1 and HW2, the HW3 assignment includes a small project that involves numerical simulations as well as deductive and analytical reasonings and is aimed at testing the mathematical modelling abilities of the students and their ability to present their analyses and results in a proper format of a written report such that a technically qualified person can follow and obtain similar findings. Students will have two weeks each to submit their HW1 and HW2 reports, and three weeks to submit their HW3 report. 2. An oral test consisting of two parts: (2a) a discussion of the submitted HW1, HW2, and HW3 reports, aimed at testing the depth of the students’ understanding of the subjects and their ability to explain, defend, reflect, critically evaluate, and possibly improve their work; (2b) a presentation of two topics studied in the course covering both theoretical aspects and possibly their applications. The two topics are chosen by the examination committee and communicated to the student, who has 30 minutes to prepare her/his presentation: during this time the student has access to books, notes, and other learning material. This part of the oral test is aimed at evaluating the breadth and depth of the kwoledge acquired by the student, and her/his ability to effectively present and communicate it to a technically qualified audience. Grading: the maximum grade for HW1, HW2, and HW3, upon the discussion detailed at point (2a) above, is of 4,4, and 6 points, respectively. If HW1, HW2, and HW3 are not submitted by their deadline, the maximum grades above are lowered to 3, 3, and 5 points, respectively. The maximum grade for part (2b) of the oral test is 18 points. The final course grade is then obtained by summing up the final grades in HW1, HW2, HW3, and of part (2b) of the oral test: if such sum is less than or equal to 30, the final grade coincides with it, if the sum is strictly larger than 30 the final grade is 30 cum laude.



© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
m@il