ComunicazioniInizio corso30-09-2024 19:56
Si avvisano gli studenti che il corso di Analisi di Reti inizierà lunedì 14 ottobre.
| Ultimo appello sessione estiva02-07-2024 12:54
Si informano gli studenti che l'ultima data utile per sostenere l'esame di Analisi di Reti durante la sessione estiva è lunedì 15 luglio
| 30-10-2023 17:49
Si rammenta agli studenti che domani, 31 ottobre, alle ore 11, si terrà una lezione telematica (su piattaforma TEAMS) in recupero della lezione del 2 novembre che è soppressa. Le lezioni riprenderanno regolarmente in presenza da lunedì 6 novembre
| CLASSE TEAMS - mod. 119-10-2023 18:51
il collegamento alla classe TEAMS per il mod. 1 è il seguente:
https://teams.microsoft.com/l/team/19%3acf7bd8a3dd0141568d93feb87c79e1a2%40thread.tacv2/conversations?groupId=d6dadb2f-3c80-424b-b96d-65575496973d&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e
| INIZIO CORSO22-09-2023 17:56
Si informano gli studenti che il corso avrà inizio giovedì 12 ottobre 2023
| 22-09-2023 17:55
Il corso di Analisi di reti per l'anno accademico 2023/24 è suddiviso in due moduli:
MODULO 1: 6 cfu, tenuto dalla Prof. Di Ianni nel periodo ottobre - inizio dicembre
MODULO 2: 3 cfu, tenuto dal Prof. Gualà nel periodo termine MODULO 1 - fine corso |
Lezioni24 | 20-12-2023
Il problema del calcolo di un Equilibrio di Nash (in strategie pure) in un Congestion Game. Perché è improbabile che il problema sia NP-hard. La giusta classe di complessità: PLS-completezza. Il problema del calcolo di un Equilibrio di Nash in strategie miste e cenni sulla classe PPAD. | 23 | 18-12-2023
Mechanism Design without money. Il problema dell'house allocation e l'algoritmo Top Trading Cycle. Un'applicazione importante della progettazione di meccanismi senza soldi: Kidney Exchange. Modelli e meccanismi. | 22 | 14-12-2023
Generalizzando l'asta del singolo oggetto: il problema dell'asta combinatorica. Un meccanismo VCG veritiero ed esatto per il problema, ma non implementabile in tempo polinomiale (a meno che P=NP). Meccanismo one-parameter approssimato: un buon algoritmo monotono per il problema di ottimizzazione soggiacente. | 21 | 13-12-2023
Il problema del cammino minimo tra due nodi in un grafo con archi privati: un meccanismo VCG. Il problema dell'albero dei cammini minimi con archi privati: problemi non utilitari. Problemi one-parameter e meccanismi one-parameter: truthfulness e monotonia. | 20 | 11-12-2023
Algorithmic Mechanism Design. Asta singolo oggetto (versione massimizzazione e minimizzazione). Una soluzione elegante: second-price auction. Meccanismi VCG. Pagamenti di Clarke e volontaria partecipazione. | 19 | 07-12-2023
Local Connection Game. Stima del prezzo della stabilità. Stima del prezzo dell'anarchia. Complessità computazionale del problema di trovare la best move. | 18 | 06-12-2023
Introduzione ai Formation Games; Global Connection Game. Stima del prezzo dell'anarchia. Tecnica del potenziale. Esistenza dell'equilibrio, convergenza all'equilibrio. Stima del prezzo della stabilità. Complessità computazionale del problema di trovare dei buoni equilibri di Nash. Un esercizio: Max-Cut game. | 17 | 04-12-2023
Introduzione al corso. Di cosa di si occupa l'Algorithmic Game Theory. Due tradizioni si incontrano: Teoria degli Algoritmi e Teoria dei Giochi. Concetti fondamentali: gioco, giocatori, strategie, outcome ed equilibri. Equilibro in strategie dominanti. Equilibrio di Nash in strategie pure e miste. Teorema di Nash. Prezzo dell’Anarchia e Prezzo della Stabilità. Esempi di
giochi. Selfish Routing e paradosso di Braess. | 16 | 30-11-2023
Lezione di 3 ore.PageRank, Scaled PageRank e analisi di convergenza. Interpretazione di PageRank e Scaled PageRank come Random Walk e Scaled Random Walk. Evoluzione del web e relazione con gli strumenti di web-search. (Cap. 14 par. 14.3, 14.4, 14.6-B e 14.6-C, lucidi AR-Web-search dal lucido 30) | 15 | 27-11-2023
Lezione di 3 ore. Il metodo HITS (hubs and Authorities): definizione e prova di convergenza. (Cap. 14, par. 14.2 e 14.6-A, lucidi AR-Web-search dal lucido 13 al lucido 29) | 14 | 23-11-2023
Lezione di 3 ore. Preferenze single-peaked e teorema del votante mediano (Cap. 23, par. 23.6, lucidi AR-SistemiDiVoto dal lucido 55 al termine).
Introduzione al web: la memoria associativa e l'ipertesto, MEMEX, il web 2.0, struttura del web. Il problema della ricerca nel web e introduzione alla link analysis. (Cap. 13 e cap. 14 par. 14.1, lucidi AR-Web-search fino al lucido 12) | 13 | 20-11-2023
Lezione di 3 ore. Dimostrazione del teorema di Arrow. (Cap. 23, par. 23.11, lucidi AR-SistemiDiVoto dal lucido 34 al lucido 54) | 12 | 16-11-2023
Lezione di 3 ore. Un modello per decisioni collettive: il teorema della giuria di Condorcet, ragionevolezza del voto non sincero, il caso della giuria. Voto individuale: ranking e relazioni binarie e loro equivalenza. Sistemi di voto: definizione. Sistema di voto a maggioranza e paradosso di Condorcet. Torneo e agenda setting. Sistemi di voto posizionali, Borda count, ruolo delle alternative irrilevanti. Il principio di uniformità e il principio di indipendenza dalle alternative irrilevanti. Il teorema di impossibilità di Arrow: enunciato. (Cap. 23, par. 23.7-23.10 e 23.1-23.5, lucidi AR-SistemiDiVoto fino al lucido 34) | 11 | 13-11-2023
Lezione di 3 ore. Introduzione alle cascate imitative: esempi, il gioco delle due urne. Un modello generale per le cascate imitative: definizione e analisi. (Cap. 16, lucidi AR-Herding) | 10 | 09-11-2023
Lezione di 3 ore. Capacità di cascata di una rete: non occorrenza di una cascata completa nel caso q maggiore di 1/2. Processi di diffusione in caso di nodi eterogenei. Azione collettiva. Processi di diffusione in presenza di compatibilità: esempio sulla catena e analisi qualitativa. Analisi del caso della catena. (Cap. 19, par. 19.5, 19.6, 19.7-B e 19.7-C, lucidi AR-ProcessiDiffusione da lucido 26 alla fine). | 9 | 06-11-2023
Lezione di 3 ore. Processi di diffusione: dal concetto di omofilia alla relazione come strumento per influenzare il comportamento degli individui; modellare i processi di diffusione come network creation games, esempi. Cascate complete e clusters, il ruolo dei weak ties. Clusters e marketing virale.Capacità di cascata di una rete: esempi (catena e griglia) e caratterizzazione dell'insieme di initiators. Capacità di cascata di una rete: esempi (catena e griglia). (Capitolo 19, par. 19.1-19.4 e 19.7-A, lucidi AR-ProcessiDiffusione fino al lucido 25) | 8 | 31-10-2023
Lezione di 3 ore. Partizionamento in comunità: metodi partitivi e metodi agglomerativi. Il metodo di Girvan-Newman per il partizionamento di un grafo in comunità. Algoritmo per il calcolo della edge.betweenness. Rilassamento del modello: grafi pesati e neighborhood overlap. Embeddedness, ruolo di un nodo,buchi strutturali, capitale sociale (Cap. 3 par. 3.6 e par. 3.3 e 3.5, lucidi AR-GrafiStrutturaDisomogenea dal lucido 34 al termine) | 7 | 30-10-2023
Lezione di 3 ore.
Introduzione alla teoria della NP-completezza (lucidi AR-IntroComplexity).
NP-completezza del problema di partizionare un grafo in due strong web- communities. (Dispensa 2 e lucidi AR-GrafiStrutturaDisomogenea dal lucido 21 al lucido 35).
| 6 | 26-10-2023
Lezione di 3 ore.
Modello per la ricerca decentralizzata: coefficienti di clustering non ottimali
(Cap. 20, pag. 544-546, 554-561, lucidi AR-SmallWorld dal lucido 37 alla fine)
Esperimento di Granovetter: potere informativo delle relazioni, bridges e local bridges, archi forti e deboli e chiusura triadica.
Proprietà della chiusura triadica forte: proprietà locali e proprietà globali. Comunità: coefficiente di clustering, cut-communities e web- communities e loro relazione.
(Cap. 3 par. 3.1-3.2, lucidi AR-GrafiStrutturaDisomogenea fino al lucido 20, Dispensa 2) | 5 | 23-10-2023
Lezione di 3 ore. Il fenomeno small world e i sei gradi di separazione. Relazioni forti e deboli e chiusura triadica nelle reti. Il modello di Watts-Strogatz. Ricerca decentralizzata. Modello per la ricerca decentralizzata: coefficiente di clustering ottimale. Dimostrazione nel caso dell'anello. (Cap. 20, par. 20.1-20.4 e 20.7.B, lucidi AR-SmallWorld fino al lucido 36). | 4 | 19-10-2023
Lezione di 3 ore. Grafi geometrici aleatori: prova della delimitazione inferiore al minimo raggio di connessione. (Dispensa 1 e lucidi AR-GrafiGeometriciAleatori, dal lucido 25 al termine, disponibili in questa pagina) | 3 | 18-10-2023
Lezione di 3 ore. mpredicibilità della popolarità. La lunga coda. Gli effetti sulla popolarità degli strumenti di web-search e sistemi di raccomandazioni. (Cap. 18, par. 18.4-18.6). Lucidi: AR-PoverLaw.
Grafi geometrici e Unit Disk Graphs. Grafi geometrici aleatori, reti wireless ad-hoc e problema del minimo raggio di trasmissione. Delimitazione superiore al minimo raggio di connessione. (Dispensa 1 e lucidi AR-GrafiGeometriciAleatori, fino al lucido 25, disponibili in questa pagina) | 2 | 16-10-2023
Lezione di 3 ore. Popolarità e fenomeno Rich get Richer: power laws, modello di Erdos Renyi e un modello che tenga conto del fenomeno Rich get Richer (cap. 18, par. 18.1-18.3). Analisi del modello (pag. 490-493). Lucidi AR-PoverLaw | 1 | 12-10-2023
Lezione di 3 ore. Introduzione al corso (cap. 1 del testo). Grafi: percorsi, componenti connesse e fortemente connesse (cap. 2 del testo). Grafi aleatori. Il modello di Erdos-Renyi: grado medio, popolarità. Lezione corrispondente ai lucidi: Introduzione al corso (file AR-Introduzione) |
Materiale didatticoLucidi: web-search | | Lucidi: sistemi di voto | | Lucidi: cascate imitative (herding) | | Lucidi: processi di diffusione | | Lucidi: reti come grafi dalla struttura disomogenea | | Dispensa 2: comunità | | Lucidi: introduzione alla teoria della NP-completezza | | Lucidi: small world e ricerca decentralizzata | | Lucidi: appendice ai grafi geometrici aleatori (dimostrazione dell'upper bound mediante Chernoff bound, non affrontato a lezione e non in programma) | | Lucidi: connessione dei grafi geometrici aleatori | | Dispensa 1: reti wireless ad-hoc e grafi geometrici aleatori | | Lucidi: modello Rich Get Richer e power law | | Lucid: introduzione al corso | |
| InformazioniAnno accademico | 2023-2024 |
---|
Crediti | 9 |
---|
Settore | INF/01 |
---|
Anno | 1 |
---|
Semestre | 1 |
---|
Propedeuticità | Nessuna |
---|
ProgrammaMODULO 1 (6 cfu, prof.ssa Di Ianni):
1) Modelli generativi di grafi aleatori e loro rilevanza nella rappresentazione di reti
- Modello di Erdos-Renyi
- Modello basato sul fenomeno rich-get-richer: la popolarità come un effetto rete, modelli rich-get-richer, power law e la long tail
- Grafi geometrici aleatori: reti wireless ad-hoc e minimo raggio di connessione
- Il fenomeno Small-world: i sei gradi di separazione, modelli per lo Small-world; ricerca decentralizzata: modelli e analisi
2) Teoria dei grafi e delle reti sociali.
- Chiusura triadica, importanza dei collegamenti deboli, struttura di rete in insiemi di grandi dimensioni,
- Comunità, partizionamenti in comunità, indici di centralità e metodo di Girvan-Newman
3) Dinamiche nelle reti
- Comportamento a cascata: diffusione, cascate e cluster, capacità di una cascata, il bilinguismo
- Cascate informative: il concetto "segui la massa", un modello di cascata, la regola di Bayes e le cascate
4) Istituzioni e comportamento aggregato
- Meccanismi di voto: decisioni di gruppo e preferenze individuali; sistemi di voto a maggioranza e posizionale; Teorema di impossibilità di Arrow; Teorema del Voto Mediano
- Voto come forma di aggregazione dell'informazione: voto sincero e non sincero, la regolaa dell'unanimità e il problema del verdetto della giuria; voto sequenziale e cascate informative.
5) Reti di Informazione: il World Wide Web
- Struttura del Web: reti di informazione, ipertesti e memoria associativa
- Link analysis e ricerca nel Web: il problema del Ranking, Hubs e Authorities, il PageRank
MODULO 2 (3 cfu, prof. Gualà):
Questo modulo tratterà un altro aspetto fondamentale delle reti moderne (e in generale dei sitemi decentralizzati complessi): la presenza di comportamenti egoistici degli utilizzatori della rete. Tale presenza ha portato negli ultimi decenni a sviluppare un'importante teoria: l'Algorithmic Game Theory (AGT), una disciplina che armonicamente fonde insieme la Teoria degli Algoritmi alla Teoria dei Giochi (Game Theory).
L'AGT è un punto particolarmente privilegiato per comprendere sia gli aspetti non-cooperativi di importanti scenari informatici, che gli aspetti computazionali di scenari economici reali.
Alcuni degli argomenti che copriremo sono: concetti di equilibri (per esempio equilibri in strategie dominanti, equilibri di Nash, ecc.), Price of Anarchy, paradosso di Braess, giochi di formazione di reti (Network Formation Games), la progettazione di meccanismi incentive-compatible (meccanismi VCG e One-parameter), aspetti non cooperativi della rete Bitcoin.
Chi volesse farsi un'idea più approfondita degli argomenti trattati, può dare un'occhiata all'edizione precendete di questo modulo qui:
https://www.mat.uniroma2.it/~guala/ADRC_2022.htm
|
Testi di riferimentoMODULO 1:
- David Easley, Jon Kleinberg, "Networks, Crowds, and Markets: Reasoning about a Highly Connected World", Cambridge University Press
- Dispense a cura del docente, disponibili in questa pagina.
- Lucidi delle lezioni on-line, a cura del docente, che saranno resi disponibili in questa pagina
|
Ricevimento studenti
Modalità di esameL'esame consiste in una prova orale.
Gli studenti che lo desiderano possono sostenere separatamente le prove dei due moduli, in qualsiasi ordine. In Tal caso, l'esame verrà verbalizzato solo nel momento in cui le prove per entrambi i moduli saranno state superate.
Al fine di offrire agli studentì una maggiore elasticità nella calendarizzazione dei propri esami, per sostenere l'esame è sempre necessario inviare una e-mail ai docenti di entrambi i moduli (o al docente del modulo di cui si intende sostenere la prova) mediante la quale è possibile concordare la data nella quale effettuare la prova orale. |
|