089194 - Complessità nei sistemi e nelle reti

 

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. 2024/25
[aggiornato il 2/10/2024]


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. 25/9/2024]
Examples of real world networks - Undirected/directed, weighted/unweighed networks - Adjacency and Laplacian matrices - Bipartite networks and projections - Connectivity and 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. 1/10/2024]
Distance and diameter - Clustering coefficient - Degree, strength, and degree distribution - Correlated networks

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

Centralities [lecture ver. 1/10/2024]
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. 1/10/2024]
Community detection: max-modularity, random walk methods - Quality indicators - LFR model - 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. 1/10/2024]
Tolerance to random failures and attacks - Critical components - 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. 25/9/2024]
Phase synchronization: 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. 2024/25

[Le precedenti modalità d'esame (a.a. 2023/24) restano valide per gli studenti che hanno superato la prova teorica (scritta) entro settembre 2024.]

 1) Prova Teorica (scritta, OBBLIGATORIA)
Si tratta di una prova scritta contenente esercizi e domande di teoria (sia "aperte" che "chiuse" - vedi i temi d'esame). Ha la durata di 1 ora e 30 min e mette a disposizione 32 punti.

Si svolge nelle date, orari e aule resi noti come di consueto via Servizi Online (è obbligatoria l'iscrizione nei termini prescritti).

2) Prova Integrativa (orale, FACOLTATIVA)
Si tratta di una prova orale che mette a disposizione 1.5 punti e può essere sostenuta prima o dopo la Prova Teorica. Il punteggio ottenuto si somma a quello della Prova Teorica.

Consiste nella discussione di un articolo scientifico: 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 min 10 - max 15 minuti.
Per l'assegnazione dell'articolo, lo studente 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.
Quando lo studente ha preparato l'esposizione, 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 tempi prescritti: al termine, il docente potrà chiedere chiarimenti o approfondimenti.
 
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 sia conseguita la sufficienza nella Prova Teorica (almeno 17.5 punti) 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 nella Prova Integrativa il voto massimo (32 e 1.5, 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. 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 25/6/2024 22/7/2024 3/9/2024