089194 - ComplessitÓ nei sistemi e nelle reti


AVVISI

Nessun avviso.



ComplessitÓ nei Sistemi e nelle Reti
(5 cfu) Ŕ emisemestrale e viene tenuto nel 2 emisemestre del 1 semestre. E' preceduto nel 1 emisemestre
(col medesimo orario) dal corso:

088877 - Teoria dei sistemi (dinamica non lineare), docente Sergio Rinaldi

ComplessitÓ nei Sistemi e nelle Reti Ŕ fortemente integrato con il corso precedente per stile e contenuti. ╚ consigliato che lo studente inserisca nel proprio piano di studi, oltre a ComplessitÓ nei Sistemi e nelle Reti, anche il corso precedente, oppure il corso 089195 - Dinamica dei sistemi complessi (10 cfu), corso integrato formato dall'unione di Teoria dei sistemi (dinamica non lineare) e ComplessitÓ nei Sistemi e nelle Reti.






ComplessitÓ nei sistemi e nelle reti
(programma ufficiale e note per gli studenti)


Il corso ha lo scopo di illustrare metodi e algoritmi per l'analisi di sistemi complessi, vale a dire sistemi composti da un numero elevato di unitÓ tra loro interagenti. Rientrano in questa categoria, a titolo di esempio, le reti sociali e quelle infrastrutturali per la distribuzione di energia, materia o informazione, le reti di transazioni economico-finanziarie e quelle di interazione biologica (p.e. proteine e processi metabolici), gli ecosistemi e le flotte di agenti (naturali o artificiali) coordinati. Il corso illustra dapprima un insieme di strumenti per l'analisi e la caratterizzazione della struttura delle reti, per poi considerare i fenomeni emergenti dall'interazione di sistemi dinamici attraverso la rete.

 

Programma delle lezioni e delle esercitazioni

Introduzione allo studio della complessitÓ nei sistemi e nelle reti
Reti complesse:

Sistemi complessi:

 

Prerequisiti


Sono sufficienti le nozioni apprese nei corsi di base di matematica e di sistemi dinamici (p.e. "Fondamenti di Automatica"). E' inoltre consigliata la frequenza a "Teoria dei sistemi (dinamica non lineare)" oppure a "Systems theory (nonlinear dynamics)".

 

Bibliografia

 

Altro materiale didattico

Il docente metterÓ a disposizione degli studenti le slide usate a lezione e vari articoli scientifici di approfondimento.

 

ModalitÓ d'esame

La prima parte dell'esame consiste in una prova scritta (esercizi e domande). Ottenuta una votazione sufficiente, allo studente viene assegnato un articolo scientifico sul quale dovrÓ preparare una presentazione powerpoint (o equivalente) di 15 min e presentarla al docente.



PROGRAMMA DETTAGLIATO (con materiale didattico scaricabile) - a.a. 2017/18
[aggiornato il 17/11/2017]


1. Introduction to complex systems and networks 
[lecture ver. 20/10/2014; zip with video files (80Mb)]
Suggested readings: http://www.scholarpedia.org/article/Complex_systems | http://www.scholarpedia.org/article/Complexity

2. Complex networks

Networks and their representation
[lecture ver. 4/11/2016]
Examples of real world networks -
Undirected/directed, weighted/unweighed networks - Adjacency and Laplacian matrices - Bipartite networks and projections - Connected and strongly connected components
Suggested readings: SH Strogatz, Exploring complex networks, Nature 2001 | MEJ Newman, The Structure and Function of Complex Networks, SIAM Review 2003 | XF Wang, G Chen, Complex Networks: Small-World, Scale-Free and Beyond, IEEE Circuits and Systems Magazine 2003 | S Boccaletti, V Latora, Y Moreno, M Chavez, DU Hwang, Complex networks: Structure and dynamics, Physics Reports 2006

Quantifying network properties [lecture ver. 8/11/2017]
Distance and diameter - Clustering coefficient - Degree, strength, and degree distribution - Correlated networks

Network models [lecture ver. 9/11/2017]
Random (Erdos-Renyi) networks - Scale-free (Barabasi-Albert) networks - Small-world (Watts-Strogatz) networks

Centralities [lecture ver. 9/11/2017]
Degree, betweenness, closeness, eigenve
ctor centralities, hub/authority scores - PageRank and other random-walk-based centralities

Mesoscale network analysis [lecture ver. 17/11/2017]
Community detection: max-modularity, Markov chain methods - Core-periphery structure: block-modeling, k-core decomposition, random walks - Rich-clubs

Suggested readings: S Fortunato, Community detection in graphs, Physics Reports 2010 | S Fortunato, D Hric, Community detection in networks: A user guide, Physics Reports 2016 | F Della Rossa, F Dercole, C Piccardi, Profiling core-periphery network structure by random walkers, Scientific Reports 2013 | V Colizza, A Flammini, MA Serrano, A Vespigani, Detecting rich-club ordering in complex networks, Nature Physics 2006

Advanced topics in network analysis [lecture ver. 14/10/2015]
Link prediction - Recommender systems - Network reconstruction

Suggested readingsL Lu, T Zhou, Link prediction in complex networks: A survey, Physica A 2011 | L Lu, M Medo, CH Yeung, YC Zhang, ZK Zhang, T Zhou, Recommender systems, Physics Reports 2012

Networks as critical infrastructures: robustness [lecture ver. 29/10/2014]
Tolerance to random failures and attacks - Cascades of failures

Suggested readings: R Albert, H Jeong, AL Barabasi, Error and attack tolerance of complex networks, Nature 2000 | AE Motter, YC Lai, Cascade-based attacks on complex networks, Physical Review E 2002


3. Complex systems

Introduction to networked dynamical systems
[lecture ver. 30/10/2014]

Spreading (epidemic) processes on networks [lecture ver. 8/1/2016]
Propagation of epidemics - Immunization strategies

Suggested readings: R Pastor-Satorras, C Castellano, P Van Mieghem, A Vespignani, Epidemic processes in complex networks, Review of Modern Physics 2015 | C Piccardi, Social networks and the spread of epidemics, Lettera Matematica Int 2013

Evolutionary games on networks [lecture to be published]
Evolutionary games in finite and infinite well-mixed populations - Evolutionary games in structured populations: from regular to scale-free networks of contact


Consensus in networked multi-agent systems
[lecture ver. 4/11/2016]
Consensus in networks of integrator systems - Topology and speed of consensus

Suggested readings: R Olfati-Saber, JA Fax, RM Murray, Consensus and Cooperation in Networked Multi-Agent Systems, Proceedings of the IEEE 2007

Phase synchronization and complete synchronization [lecture ver. 4/11/2016]
Phase synchronization of coupled oscillators - Bidirectional and unidirectional (master/slave) coupling - Complete synchronization

Suggested readings: M Rosenblum, A Pikovsky, J Kurths, C Schafer, PA Tass, Phase synchronization: from theory to data analysis, Handbook of Biological Physics, Vol. 4, Neuro-informatics, 2001 | S Boccaletti, J Kurths, G Osipov, DL Valladares, CS Zhou, The synchronization of chaotic systems, Physics Reports 2002

Synchronization of networked oscillators [lecture ver. 14/1/2016]
Kuramoto model - Complete synchronization in networked oscillators
Suggested readings: A Arenas, A DÝaz-Guilera, J Kurths, Y Moreno, C Zhou, Synchronization in complex networks, Physics Reports 2008 | tutorial on Liapunov exponents


More resources...

Further readings on topics not included in the program:

Software for network plotting and analysis:

Lab session files (require Matlab): Structural properties of complex networks [zip file], Finding and testing network communities by lumped Markov chains [webpage], Profiling core-periphery network structure by random walkers [webpage]

Books:




PROCEDURA PER L'ESAME - a.a. 2017/18

1) Prova scritta
La prova scritta Ŕ obbligatoria e si svolge nelle date, orari e aule resi noti come di consueto via Webpoliself (Ŕ obbligatoria l'iscrizione nei termini prescritti).
La prova scritta (durata 1 ora e 30 min) mette a disposizione 26 punti.
Lo studente che ha totalizzato almeno 15 punti Ŕ ammesso alla prova orale (facoltativa in generale, obbligatoria per chi ha conseguito meno di 17.5 punti nella prova scritta).
Lo studente che si presenta ad una prova scritta rinuncia implicitamente ad un eventuale voto positivo conseguito in una prova precedente,
anche nel caso non consegni.

2) Prova orale
La prova orale Ŕ facoltativa e mette a disposizione 7 punti.
Lo studente deve preparare - in totale autonomia - la presentazione orale di un articolo concordato con il docente (vedi sotto), accompagnata da pagine powerpoint (o supporto analogo), della durata di 15 minuti. Quando pronta, lo studente concorda con il docente data/ora della presentazione (di norma mediante un "foglio prenotazioni" il cui indirizzo web Ŕ fornito a chi Ŕ ammesso all'orale). Nel corso dell'incontro, lo studente illustrerÓ il proprio lavoro rispettando rigorosamente i 15 minuti prescritti: al termine, il docente potrÓ chiedere chiarimenti o approfondimenti relativi al contenuto dell'articolo discusso. Il docente comunicherÓ quindi il risultato complessivo dell'esame, che verrÓ verbalizzato al primo appello utile previa, se necessaria, nuova iscrizione via Webpoliself. In caso di rifiuto del voto complessivo lo studente dovrÓ ripetere l'intero esame (scritto e orale, con assegnazione di un diverso articolo).

Per l'assegnazione dell'articolo sono possibili due modalitÓ:

a) Lo studente,
prima o dopo la prova scritta, sceglie autonomamente l'articolo nel "serbatoio" pre-approvato (l'indirizzo web Ŕ fornito via email a tutti gli studenti: contattare il docente nel caso venisse smarrito), lo comunica via email al docente (la comunicazione Ŕ OBBLIGATORIA) che conferma la presa in carico.

b) Se lo studente non trova nel "serbatoio" un articolo di proprio gradimento o desidera trattare un argomento specifico, contatta il docente via email specificando le proprie richieste, tipicamente:

Se l'argomento Ŕ specificato, si garantisce l'assegnazione di un articolo pertinente; si cercherÓ inoltre, per quanto possibile, di soddisfare i requisiti ulteriori.

Clicca qui per scaricare tre esempi di file preparati da studenti per la presentazione orale (a.a. 2015/16 e 2016/17).


NOTA BENE (1): La presentazione orale dovrÓ avvenire sia entro 1 anno dall'assegnazione dell'articolo che entro 1 anno dalla prova scritta: in caso contrario, decadono sia l'assegnazione dell'articolo che il voto della prova scritta.

NOTA BENE (2): Nel caso si siano conseguiti almeno 17.5 punti nella prova scritta e NON si intenda svolgere la prova orale, Ŕ necessario comunicare al docente la richiesta di verbalizzazione (accompagnata dall'iscrizione a un appello per permettere la verbalizzazione). In assenza di tale comunicazione, si assume che lo studente intenda svolgere la prova orale.

NOTA BENE (3):
Come di consueto, sia nello scritto che nell'orale il voto massimo (26 e 7, rispettivamente) Ŕ riservato a prove di assoluta eccellenza nella forma, nel rigore matematico, nella scelta dei contenuti presentati. Per l'orale, in particolare, ci˛ significa che il voto di
una prova "normale" (nÚ scadente nÚ eccellente) Ŕ da attendersi attorno ai 4 punti.




TEMI D'ESAME
 


simulazione #1   simulazione #2


a.a. 2014/15 4/2/2015 25/2/2015 8/7/2015

a.a. 2015/16 9/2/2016 24/2/2016 6/7/2016 7/9/2016 21/9/2016
a.a. 2016/17 8/2/2017 22/2/2017 5/7/2017 17/7/2017 20/9/2017