Analisi di reti

Si avvisano gli studenti che l'ultima data utile per sostenere l'esame durante la sessione estiva è il 15 luglio

Si informano gli studenti che la lezione di mercoledì 20/10/2021 avrà inizio alle ore 9.

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

Lezione di 3 ore.

Il metodo Hubs and Authorities (HITS): completamento della dimostrazione di convergenza.

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-2, 14-3, 14.6-A, 14.6-B, 14.6-C, lucidi AR-Web-search dal lucido 28 al temine)

Il metodo Hubs and Authorities (HITS): definizione e inizio della dimostrazione di convergenza (Cap. 14, par. 14.2, 14.6-A, lucidi AR-Web-search dal lucido 13 al lucido 27)

Lezione di 3 ore.

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

La struttura del Web: reti di informazione, memoria associativa e Memex; il Web come grafo diretto, struttura bow-tie e Web 2.0. Il problema della ricerca sul web. Ranking e link analysis. (Cap 13, Cap. 14, par, 14-1, 14.2, lucidi AR-Web-search fino al lucido 12)

Dimostrazione del teorema di Arrow (Cap. 23, par. 23.11, lucidi AR-SistemiDiVoto dal lucido 40 al lucido 54)

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 e prima parte della dimostrazione (Cap. 23, par. 23.3-23.5 e 23.11, lucidi AR-SistemiDiVoto dal lucido 24 al lucido 39)

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.

(Cap. 23, par. 23.7-23.10 e 23.1-23.3, lucidi AR-SistemiDiVoto fino al lucido 24)

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

Lezione di 3 ore.

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 e 19.7-C, lucidi AR-ProcessiDiffusione da lucido 42 alla fine).

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

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. Processi di diffusione in caso di nodi eterogenei. Azione collettiva. (Cap. 19, par. 19.7-A, 19.7-B, 19.5, 19.6 e lucidi AR-ProcessiDiffusione dal lucido 25 al lucido 41)

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. Capacità di cascata di una rete: esempi (catena e griglia) e caratterizzazione dell'insieme di initiators. (Capitolo 19, par. 19.1-19.4 e 19.7-A, lucidi AR-ProcessiDiffusione fino al lucido 24)

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 dal lucido 35 al termine)

NP-completezza del problema di partizionare un grafo in due strong web- communities.

Partizionamento in comunità: metodi partitivi e metodi agglomerativi.

(Cap. 3 parte iniziale del par. 3.6, dispensa 2 e lucidi AR-GrafiStrutturaDisomogenea dal lucido 21 al lucido 35).

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)

Lezione di 3 ore.

Modello per la ricerca decentralizzata: coefficiente di clustering ottimale. Dimostrazione nel caso dell'anello.

Modello per la ricerca decentralizzata: coefficienti di clustering non ottimali

(Cap. 20, pag. 544-546, 554-561 e par. 20.7.B, lucidi AR-SmallWorld dal lucido 22 alla fine)

Lezione di 3 ore.

Grafi geometrici aleatori: conclusione della prova della delimitazione superiore al minimo raggio di connessione (Dispensa 1 e lucidi AR-GrafiGeometriciAleatori, dal lucido 38,  disponibili in questa pagina).

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, lucidi AR-SmallWorld fino al lucido 21).

Grafi geometrici aleatori: prima parte della prova della delimitazione inferiore al minimo raggio di connessione. (Dispensa 1 e lucidi AR-GrafiGeometriciAleatori, dal lucido 25 al lucido 37,  disponibili in questa pagina)

Lezione di 3 ore. 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. Prima parte della prova della delimitazione inferiore al minimo raggio di connessione. (Dispensa 1 e lucidi AR-GrafiGeometriciAleatori, fino al lucido 25,  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). Lucidi: AR-PoverLaw.

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). Inizio dell'analisi del modello (pag. 490-492). Lucidi AR-PoverLaw

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)

Lucidi: web-search

Lucidi: sistemi di voto

Lucidi: cascate imitative (seguire la folla)

Lucidi: processi di diffusione

Lucidi: reti come grafi dalla struttura disomogenea

Dispensa 2: web-communities e cut-communities

Lucidi: il fenomeno Small World

Lucidi: grafi geometrici aleatori e reti wireless

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

Lucidi: appendice ai grafi geometrici aleatori

Lucidi: la Power Law e il modello Rich get Richer

Lucidi: introduzione al corso e modello di Erdos-Renyi

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,

     - Comunità, partizionamenti in comunità, indici di centralità e metodo di Girvan-Newman

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

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

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

Da richiedere al docente a mezzo posta elettronica o nel corso delle lezioni. Il ricevimento potrà avvenire in presenza o in modalità telematica.

Prova orale.

Si ricorda agli studenti che le date di esame che compaiono sul sito (ove presenti) 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.