Analisi di reti

Si avvisano gli studenti che, per motivi di salute, la lezione di domani, lunedì 7 novembre, avrà luogo alle ore 11:30 in modalità telematica nella classe Teams di seguito indicata:

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

Si avvisano gli studenti che, per motivi di salute, la lezione di domani, giovedì 3 novembre, avrà luogo alle ore 11:30 in modalità telematica nella classe Teams di seguito indicata:

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

Si avvisano gli studenti che, al fine di andare incontro alle esigenze dell'unico studente sino ad ora frequentante, la lezione di lunedì 24 ottobre avrà luogo alle ore 18 in modalità telematica nella classe Teams di seguito indicata:

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

Si avvisano gli studenti che, al fine di recuperare le lezioni andate deserte, la lezione di giovedì 20 ottobre avrà inizio alle ore 11 anziché alle 11:30

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)

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)

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

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

Lezione di 3 ore.

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) 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.4, 19.7-A, 19.7-B, 19.5, 19.6 e lucidi AR-ProcessiDiffusione dal lucido 19 al lucido 41)

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. (Capitolo 19, par. 19.1-19.4 e 19.7-A, lucidi AR-ProcessiDiffusione fino al lucido 18)

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

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)

Modello per la ricerca decentralizzata: coefficiente di clustering ottimale. Dimostrazione nel caso dell'anello. (Cap. 20 par. 20.7.B, lucidi AR-SmallWorld dal lucido 22 al lucido 36)

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: conclusione della prova della delimitazione superiore al minimo raggio di connessione (Dispensa 1 e lucidi AR-GrafiGeometriciAleatori, dal lucido 38,  disponibili in questa pagina).

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)

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)

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 delle lezioni: sistemi di voto

Lucidi delle lezioni: cascate imitative (herding)

Lucidi delle lazioni: processi di diffusione

Dispensa 2: comunità

Lucidi delle lezioni: Reti come grafi dalla struttura disomogenea

Lucidi delle lezioni: small world e ricerca decentralizzata

Lucidi delle lezioni: appendice ai grafi geometrici aleatori (dimostrazione dell'upper bound mediante Chernoff bound)

Dispensa 1: reti wireless ad-hoc e grafi geometrici aleatori

Lucidi delle lezioni: grafi geometrici aleatori

Lucidi delle lezioni: power law e modello rich-get-richer

Lucidi delle lezioni: Introduzione al corso e modello di Edos-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.

Si informano gli 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 è sempre necessario inviare una e-mail alla docente mediante la quale è possibile concordare la data nella quale effettuare la prova orale.