Analisi di reti

AVVISO: il corso inizierà mercoledì 14 ottobre (ore 9:30). Lunedì 12 ottobre non ci sarà lezione.

Link TEAMS:

https://teams.microsoft.com/l/team/19%3acf7bd8a3dd0141568d93feb87c79e1a2%40thread.tacv2/conversations?groupId=d6dadb2f-3c80-424b-b96d-65575496973d&tenantId=24c5be2a-d764-40c5-9975-82d08ae47d0e

Gli studenti interessati a seguire le lezioni possono comunque inviarmi un messaggio (miriam.di.ianni chiocciola uniroma2.it) e li inserirò nella classe dello scorso anno.

PageRank, PageRank scalato e analisi di convergenza. Formulazione del PageRank (di base o scalato) mediante random walks. Web-search e evoluzione del Web (Cap. 14, par, 14-3, 14., 14.6-B, 14.6-C, lucidi AR-Web-search)

Lezone di 3 ore.

Il problema della ricerca sul web. Ranking e link analysis. Il metodo Hubs and Authorities (HITS): definizione e dimostrazione di convergenza (Cap. 14, par, 14-1, 14.2, 14.6-A, lucidi AR-Web-search)

Preferenze single peaked e il teorema del votante mediano (Cap. 23, par. 23.6, lucidi AR-SistemiDiVoto).

La struttura del Web: reti di informazione, memoria associativa e Memex; il Web come grafo diretto, struttura bow-tie e Web 2.0 (Cap 13, lucidi AR-Web-search)

Dimostrazione del teorema di Arrow (Cap. 23, par. 23.11, lucidi AR-SistemiDiVoto)

Sistemi di voto: definizione. Sistema di voto a maggioranza e paradosso di Condorcet. Torneo e agenda setting. Sistemi di voto posizionale, Borda count, ruolo delle alternative irrilevanti. Il principio di uniformità e il principio delle alternative irrilevanti. Il teorema di impossibilità di Arrow: enunciato e prima parte della dimostrazione (Cap. 23, par. 23.3-23.5 e 23.11, lucidi AR-SistemiDiVoto)

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 (Cap. 23, par. 23.7-23.10 e 23.1-23.2, lucidi AR-SistemiDiVoto)

Un modello generale per le cascate imitative: definizione e analisi (Cap. 16, par. 16.4 -16.7, lucidi AR-Herding)

Processi di diffusione in presenza di compatibilità: analisi del caso della catena  (Cap. 19, par. 19.5, 19.6 e 19.7-C, lucidi AR-ProcessiDiffusione).

Introduzione alle cascate imitative: esempi, il gioco delle due urne (Cap. 16, par. 16.1 e 16.2, lucidi AR-Herding)

Processi di diffusione in caso di nodi eterogenei. Azione collettiva. Processi di diffusione in presenza di compatibilità: esempio sulla catena e analisi qualitativa Cap. 19, par. 19.5, 19.6 e 19.7-C, lucidi AR-ProcessiDiffusione)

Capacità di cascata di una rete: esempi (catena e griglia) e caratterizzazione dell'insieme di initiators, non occorrenza di una cascata completa nel caso q maggiore di 1/2(Cap. 19, par. 19.7-A e 19.7-B, lucidi AR-ProcessiDiffusione)

Processi di diffusione: dal concetto di omofilia alla relazione come strumento per influenzare il comportamento degli individui; odellare i processi di diffusione come network creation games, esempi: Cascate complete e clusters, il ruolo dei weak ties. (Capitolo 19, par. 19.1-19.4, lucidi AR-ProcessiDiffusione)

Il metodo di Girvan-Newman per il partizionamento di un grafo in comunità. Algoritmo per il calcolo della edge.betweenness. Rilassamento del modello: grafi peseti e neighborhood overlap. Embeddedness, ruolo di un nodo,buchi strutturali, capitale sociale (Cap. 3 parte finale del par. 3.6 e par. 3.3 e 3.5, lucidi AR-GrafiStrutturaDisomogenea)

NP-completezza del problema di partizionare un grafo in due strong web- communities (dispensa 2 e lucidi AR-GrafiStrutturaDisomogenea).

Partizionamento in comunità: metodi partitivi e metodi agglomerativi. Il concetto di edge.betweenness. (Cap. 3 parte iniziale del par. 3.6, lucidi AR-GrafiStrutturaDisomogenea)

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.2, lucidi AR-GrafiStrutturaDisomogenea, Dispensa 2)

Modello per la ricerca decentralizzata: coefficienti di clustering non ottimali (Cap. 20, par. 20.7.B).

Esperimento di Granovetter: potere informativo delle relazioni, bridges e local bridges, archi forti e deboli e chiusura triadica (Cap. 3 par. 3.1-3.2, lucidi AR-GrafiStrutturaDisomogenea)

Modello per la ricerca decentralizzata: coefficiente di clustering ottimale. Dimostrazione nel caso dell'anello. (Cap. 20, pag. 544-546 e 554-561)

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. (Cap. 20, par. 20.1-20.4 fino pag. 544)

Grafi geometrici aleatori: conclusione della prova della delimitazione superiore al minimo raggio di connessione. (Dispensa D01 e pag. 30 - 42 dei lucidi delle lezioni disponibili in questa pagina)

Grafi geometrici aleatori: prima parte della prova della delimitazione superiore al minimo raggio di connessione. (Dispensa D01 e pag. 21-30 dei lucidi delle lezioni disponibili in questa pagina)

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 delle lezioni disponibili in questa pagina)

Completamento dell'analisi del modello Rich Get Richer (pag. 192-193). Impredicibilità 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)

Popolarità e fenomeno Riche 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). Inizio dell'analisi del modello (pag. 490-492)

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 e modello di Erdos-Renyi

Lucidi: web search

Lucidi: sistemi di voto

Lucidi: cascate imitative

Lucidi: processi di diffusione

Lucidi: reti come grafi dalla struttura disomogenea

Lucidi: Power Law e modello Rich Get Richer

Lucidi: introduzione al corso e modello di Erdos-Renyi

Dispensa 2: comunità

Lucidi: fenomeno Small World e ricerca decentralizzata

Dispensa 1: grafi geometrici casuali e problema del minimo raggio di trasmissione

Lucidi: grafi geometrici aleatori e problema del minimo raggio di trasmissione

Lucidi: appendice alle lezioni sui grafi geometrici aleatori

Programma preventivato (che potrà subire variazioni nel corso di svolgimento delle lezioni):

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,

      indici di centralità e partizionamenti

    - Bilancio strutturale

3) Dinamiche nelle reti

    - Cascate informative: il concetto "segui la massa", un modello di cascata, la regola di Bayes e le cascate

     - Comportamento a cascata: diffusione, cascate e cluster, il ruolo dei weak ties, capacità di una cascata

    - Il fenomeno Small-world: i sei gradi di separazione, modelli per lo Small-world; ricerca decentralizzata: modelli e analisi

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

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

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, disponibili in questa pagina

In quest'anno particolare, i ricevimenti saranno prevalentemente on-line, da richiedere al docente a mezzo posta elettronica o nel corso delle lezioni.

Se qualche studente avesse esigenza di incontro in studio potrà farne richiesta a mezzo posta elettronica - salvo ulteriori sviluppi della situazione emergenziale.

Prova orale - possibilmente in modalità on-line.

Si ricorda agli studenti che le date di esame che compaiono sul sito hanno titolo puramente indicativo e prenotarsi sul totem è necessario ai soli fini della verbalizzazione. Al fine di offrire agli studentì una maggiore elasticità nella calendarizzazione dei propri esami, per sostenere l'esame è necessario inviare una e-mail alla docente mediante la quale è possibile concordare la data nella quale effettuare la prova orale.