089194 - Complessità nei sistemi e nelle reti


AVVISI

Nessun avviso.
 



Complessità nei sistemi e nelle reti


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

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)".

 


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 Fabio Dercole

Complessità nei Sistemi e nelle Reti è fortemente integrato con il corso precedente per stile e contenuti. E' 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.



PROGRAMMA DETTAGLIATO (con materiale didattico scaricabile) - a.a. 2021/22
[aggiornato il 13/12/2021]


1. Introduction to complex systems and networks 
[lecture ver. 10/9/2021; 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. 10/9/2021]
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. 10/9/2021]
Distance and diameter - Clustering coefficient - Degree, strength, and degree distribution - Correlated networks

Network models [lecture ver. 15/9/2021]
Random (Erdos-Renyi) networks - Scale-free (Barabasi-Albert) networks - Small-world (Watts-Strogatz) networks - Stochastic block-model

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

Suggested readings: DF Gleich, PageRank beyond the web, SIAM Review 2015

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

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

Advanced topics in network analysis [lecture ver. 24/9/2021]
Link prediction - Recommender systems - Advanced network models

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. 13/9/2021]
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. 24/9/2021]

Spreading (epidemic) processes on networks [lecture ver. 30/9/2021]
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 ver. 12/10/2017] (non svolto nell'a.a. 2021/22)
Evolutionary games in finite and infinite well-mixed populations - Evolutionary games in structured populations: from regular to scale-free networks of contact

Suggested readings: G Szabó, G Fáth, Evolutionary games on graphs, Physics Reports 2007 | FC Santos, JM Pacheco, T Lenaerts, Evolutionary dynamics of social dilemmas in structured heterogeneous populations, PNAS 2006 | C Gracia-Lázaro, A Ferrer, G Ruiz, A Tarancón, JA Cuesta, A Sanchez, Y Moreno, Heterogeneous networks do not promote cooperation when humans play a Prisoner's Dilemma, PNAS 2012

Consensus in networked multi-agent systems [lecture ver. 2/12/2021]
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. 13/12/2021]
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. 30/9/2021]
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:

Network datasets:


Lab session files (require Gephi; Matlab; Phyton/NetworkX): Gephi lab session [zip file] - Matlab lab session [zip file] - NetworkX lab session [zip file]

Books:




MODALITA D'ESAME - a.a. 2021/22

1) Prova teorica
La prova teorica è obbligatoria: si tratta di una prova scritta contenente esercizi e domande teoriche. Si svolge nelle date, orari e aule resi noti come di consueto via Servizi Online (è obbligatoria l'iscrizione nei termini prescritti). Ha la durata di 1 ora e 30 min e mette a disposizione 30 punti.
Lo studente che totalizza almeno 17.5 punti ha superato l'esame e, se lo desidera, è ammesso alla prova integrativa (facoltativa - vedi sotto).
Lo studente che si presenta a una prova scritta rinuncia implicitamente a un eventuale voto positivo conseguito in una prova precedente,
anche nel caso non consegni.

2) Prova integrativa
La prova integrativa è facoltativa e mette a disposizione 3 punti. Può essere sostenuta solo dopo il superamento della prova teorica.

Vi sono due differenti tipologie di prova integrativa, a
scelta dello studente:

a) Presentazione articolo:
Lo studente prepara - in totale autonomia - la presentazione orale di un articolo concordato con il docente, accompagnata da pagine powerpoint (o supporto analogo), della durata di 15 minuti. Per l'assegnazione dell'articolo, lo studente, prima o dopo la prova teorica, sceglie autonomamente l'articolo nel "serbatoio" pre-approvato (l'indirizzo web è fornito via email a tutti gli studenti) e lo comunica via email al docente (la comunicazione è OBBLIGATORIA) che conferma la presa in carico.

b) Analisi dati: Lo studente analizza - in totale autonomia - un dataset a sua scelta rappresentativo di una rete complessa, secondo le metodologie apprese nel corso, e illustra i risultati nel corso di una presentazione orale della durata di 15 minuti. E' OBBLIGATORIA la comunicazione preventiva via email al docente del dataset utilizzato, inclusa la pagina web in cui è stato reperito.

Quando lo studente ha preparato la prova integrativa, concorda con il docente data/ora della presentazione (di norma mediante un foglio prenotazioni online). Nel corso dell'incontro, lo studente illustra il proprio lavoro rispettando rigorosamente i 15 minuti prescritti: al termine, il docente potrà chiedere chiarimenti o approfondimenti. Il docente comunica quindi il risultato complessivo dell'esame, che verrà verbalizzato al primo appello utile previa, se necessaria, nuova iscrizione via Servizi Online.
 


NOTA BENE (1): La presentazione orale della prova integrativa dovrà avvenire sia entro 1 anno dall'assegnazione che entro 1 anno dalla prova teorica (vale il termine più restrittivo): in caso contrario, decadono sia l'assegnazione dell'articolo/dataset che il voto della prova teorica.

NOTA BENE (2): Nel caso si siano conseguiti almeno 17.5 punti nella prova teorica e NON si intenda svolgere la prova integrativa, è 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 integrativa.

NOTA BENE (3):
Come di consueto, sia nella prova teorica che in quella integrativa il voto massimo (30 e 3, rispettivamente) è riservato a prove di assoluta eccellenza nella forma, nel rigore matematico, nella scelta dei contenuti presentati.


[Le regole d'esame in vigore fino all'a.a. 2020/21, in particolare i punteggi conseguibili nella prova teorica e integrativa (26 e 7, rispettivamente) valgono per chi ha superato la prova teorica entro settembre 2021 e presenta la prova integrativa nei termini ammissibili.]




TEMI D'ESAME
 
I temi d'esame (prova teorica) degli ultimi tre a.a. sono scaricabili cliccando sulla data della prova scritta.

a.a. 2018/19 23/1/2019 15/2/2019 25/6/2019 18/7/2019 9/9/2019
a.a. 2019/20 20/1/2020 18/2/2020


a.a. 2020/21 18/1/2021 16/2/2021 11/6/2021 2/7/2021 2/9/2021
a.a. 2021/22 13/1/2022 31/1/2022