Politecnico di Torino
Politecnico di Torino
   
Login  
en
Politecnico di Torino
Anno Accademico 2009/10
01NUOKK
Sistemi dinamici su reti
Dottorato di ricerca in Matematica Per Le Scienze Dell'Ingegneria - Torino
Docente Qualifica Settore Lez Es Lab Tut Anni incarico
Fagnani Fabio ORARIO RICEVIMENTO PO MAT/05 25 0 0 0 1
SSD CFU Attivita' formative Ambiti disciplinari
*** N/A ***    
Obiettivi dell'insegnamento
Finalità del corso:
In una grande varietà di discipline scientifiche e tecnologiche (scienze sociali ed economiche, informatica, ingegneria, biologia), stanno rapidamente guadagnando importanza modelli matematici basati sulle reti. Il contesto unificante è quello di un grandissimo numero di sistemi 'atomi' caratterizzati da una semplice dinamica temporale, che vengono interconnessi insieme. Come conseguenza di tale interazione, emergono nel sistema complesse proprietà globali: convergenza asintotica ad un equilibrio (generalmente dipendente dalla condizione iniziale), fenomeni di correlazione a diverse scale di lunghezza sulla rete, fenomeni di consenso locale o globale. Il corso vuole essere un'introduzione ad alcune delle linee di ricerca più interessanti e più promettenti riguardo ai sistemi dinamici su reti. Alcuni esempi che abbiamo in mente e che vogliamo coprire con questo corso: modelli per la diffusione delle opinioni in reti sociali ed economiche, algoritmi cooperativi su reti di sensori (consenso), 'flocking' in reti biologiche e robotiche, apprendimento Bayesiano e giochi sulle reti.

Aims of course:
In a large variety of scientific and technological fields (social and economic sciences, computer science, engineering, biology), mathematical models based on networks are rapidly increasing their importance. The unifying setting is a large number of 'atoms' possesing a relatively simple time dynamics, who are interconnected together. As a consequence of this interaction, complex global properties emerge in the network: asymptotic convergence to an equilibrium (typically dependent on the initial condition), correlation phenomena on several possible network length scales, local and global agreement. The course wants to give an introduction to some of the hottest and most promising research topics on dynamics over networks. The examples we have in mind and which we want to cover in this course include: opinion spreading models in social and economic networks, cooperative algorithms over sensor networks (consensus), flocking behavior for biological and robotic networks, Bayesian learning and games over networks.
Programma
Programma del corso:
1. Un po' di esempi. Reti sociali, di informazione, tecnologiche, biologiche. Proprietà delle reti reali: l'effetto 'small world', 'clustering', distribuzione dei gradi 'power law', proprietà 'scale-free'. Dinamiche sulle reti: algoritmi cooperativi su reti di sensori, 'flocking' su reti biologiche e robotiche, modelli continui e discreti di dinamica delle opinioni; modelli di apprendimento e giochi strategici.

2. Modelli di grafi aleatori. Breve richiamo su concetti di teoria dei grafi: cammini, cicli, connettività, geodetiche, diametro, gradi. Il modello di Erdos-Renyi: la distribuzione Poissoniana dei gradi, la componente connessa gigante, transizioni difase, diametro. Il modello di configurazione: grafi con un'assegnata distribuzione di gradi. Grafi aleatori geometrici. Il modello dell'attaccamento preferenziale di Price-Albert-Barabasi.

3. Sistemi dinamici su reti. Richiamo sulle catene di Markov: cammini aleatori su grafi, probabilità invarianti, convergenza, teoria spettrale, funzioni armoniche, tempi di ingresso e di ritorno, tempi di 'mixing'. Algoritmi a media locale, convergenza al consenso. Modelli di 'flocking'. Modelli 'gossip'. Modelli discreti per la dinamica delle opinioni: il modello 'voter'. Modelli continui per la dinamica delle opinioni: i modelli di Hegselman-Krause e di Deffuant-Weisbuch.

4. Apprendimento e giochi su reti. Apprendimento Bayesiano su reti. Modelli iterativi. Giochi strategici su reti. Equilibri di Nash e problemi di convergenza. Stabilità stocastica. Dinamiche di formazione delle reti.



Course contents:
1. A bunch of examples. Social, information, technological, biological networks. Properties of real-world networks: small world effect, clustering, power law degree distribution, scale-free properties. Dynamics on networks: cooperative algorithms over sensor networks, flocking over robotic and biological newtorks; discrete and continuous opinion dynamics models; learning models and strategic games.

2. Random graph models. Brief recap of graph concepts: paths, cycles, connectivity, geodetics, diameter, degrees. The Erdos-Renji model: Poisson degree distribution, giant component, phase transitions, diameter. The configuration model: graphs with given degree distributions. Geometric random graphs. The preferential attachment model by Price-Albert-Barabasi.

3. Dynamical systems on networks. A recap of Markov chains: random walks on graphs, invariant probability distributions, convergence, spectral theory, harmonic functions, return and entrance times, mixing times. Locally averaging algorithms, convergence to consensus. Flocking models. Gossip models. Discrete opinion dynamics models: the voter model. Continuous opinion dynamics models: The Hegselman-Krause and the Deffuant-Weisbuch models.

4. Network learning and games. Bayesian learning on networks. Iterative models. Strategic games on networks. Nash equilibria and convergence issues. Stochastic stability. Network formation dynamics.

Programma: informazioni integrative
CALENDARIO
Il corso inizierà a settembre con calendario da stabilire.
Bibliografia
Bibliografia:

(1) Jackson, Matthew O., Social and economic networks, Princeton Univ. Press, 2008.
(2) Vega-Redondo, Fernando, Complex social networks, Cambridge Univ. Press, 2007.
(3) Durrett, Richard, Random graph dynamics, Cambridge Univ. Press, 2007.

Bibliography:

(1) Jackson, Matthew O., Social and economic networks, Princeton Univ. Press, 2008.
(2) Vega-Redondo, Fernando, Complex social networks, Cambridge Univ. Press, 2007.
(3) Durrett, Richard, Random graph dynamics, Cambridge Univ. Press, 2007.
Orario delle lezioni
Statistiche superamento esami

Programma provvisorio per l'A.A.2009/10
Indietro



© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
WCAG 2.0 (Level AA)
Contatti