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. 2023/24
[aggiornato il 22/9/2023]


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. 14/7/2022]
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/1/2024]
Distance and diameter - Clustering coefficient - Degree, strength, and degree distribution - Correlated networks

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

Centralities [lecture ver. 13/9/2023]
Degree, betweenness, closeness, eigenvector centralities, hub/authority scores, PageRank

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

Mesoscale network analysis [lecture ver. 13/9/2023]
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 readings: L 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 processes on networks [lecture ver. 15/9/2023]
Epidemics on networks - Immunization strategies - Influence propagation ("social contagion")
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
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:

Webinars of the Network Science Society (video recordings)


MODALITA' D'ESAME - a.a. 2023/24

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).
Non sono richiesti né l'accettazione né il rifiuto del voto ottenuto nella prova teorica: Lo studente che si presenta di nuovo a una prova scritta rinuncia implicitamente a un eventuale voto positivo conseguito in una prova precedente, anche nel caso non consegni. Lo studente che presenta la prova integrativa (facoltativa - vedi sotto) accetta implicitamente l'esito della sua ultima prova teorica.

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): Il voto ottenuto nella prova teorica resta valido 1 anno: entro tale termine lo studente dovrà sostenere la prova integrativa o comunicare la rinuncia ad essa.

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.




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

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 9/6/2022 30/6/2022 2/9/2022
a.a. 2022/23 19/1/2023 13/2/2023 9/6/2023 3/7/2023 4/9/2023
a.a. 2023/24 11/1/2024 29/1/2024