Analisi di reti

Docente: Miriam Di Ianni

Comunicazioni

21-06-2022 18:47

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


18-10-2021 19:00

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


01-10-2021 18:32

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


Lezioni

2022-12-2021

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)

1920-12-2021

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)

1815-12-2021

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)

1713-12-2021

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

1606-12-2021

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)

1501-12-2021

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)

 
   
1429-11-2021

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)

1324-11-2021

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

1222-11-2021

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)

1117-11-2021

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)

1015-11-2021

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)

910-11-2021

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

808-11-2021

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)

703-11-2021

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)

627-10-2021

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

525-10-2021

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)

420-10-2021

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)

318-10-2021

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.

213-10-2021

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

111-10-2021

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

Informazioni

Anno accademico2021-2022
Crediti6
SettoreINF/01
Anno1
Semestre1
PropedeuticitàNessuna

Programma

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

 

 

 

 


Testi di riferimento

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


Ricevimento studenti

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


Modalità di esame

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.