Analisi di reti

Docenti: Miriam Di Ianni, Luciano Guala'

Comunicazioni

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. 1

19-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 CORSO

22-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


Lezioni

2420-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.

2318-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.

2214-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.

2113-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.

2011-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.

1907-12-2023

Local Connection Game. Stima del prezzo della stabilità. Stima del prezzo dell'anarchia. Complessità computazionale del problema di trovare la best move.

1806-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.

1704-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.

1630-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)

1527-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)

1423-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)

1320-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)

1216-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)

1113-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)

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

906-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)

831-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)

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

 

626-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)

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

419-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)

318-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)

216-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

112-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 didattico

Lucidi: 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

Informazioni

Anno accademico2023-2024
Crediti9
SettoreINF/01
Anno1
Semestre1
PropedeuticitàNessuna

Programma

MODULO 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 riferimento

MODULO 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

null

Modalità di esame

L'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.