Analisi di reti

Docente: Miriam Di Ianni

Comunicazioni

20-12-2016 17:24

Si comunica che, per problemi di salute del docente, la lezione di Analisi di reti di mercoledì 21/12/2016 non si terrà


11-12-2016 21:11

Causa stato influenzale della docente, la lezione di lunedì 12 dicembre non avrà luogo


08-11-2016 18:06

Si informano gli studenti che la lezione di Analisi di Reti di mercoledì 09/11/2016 non avrà luogo.


06-11-2016 19:37

La lezione del 07/11/2016 non avrà luogo


Lezioni

2425-01-2017

Esercitazione

2323-01-2017

Teorema del votante mediano. Voto come espressione di una preferenza e voto come metodo di ricostruzione di una informazione. Il  Teorema della giuria di Condorcet. Voto non sincero. Regola dell'unanimità e decisioni di giurie.

2218-01-2017

Dimostrazione del Teorema di Arrow. Preferenze Single Peaked.

2116-01-2017

Lezione di 3 ore. Ancora sull'analisi dell'algoritmo di ricerca miope: il caso in cui il coefficiente di clustering è diverso dalla dimensione dello spazio.

Sistemi di voto: espressione mediante relazioni binarie complete e mediante ranking e loro equivalenza, sistemi di voto posizionali e paradosso di Condorcet, tornei, sistemi di voto posizionali (Borda count) e ruolo delle alternative irrilevanti. Enunciato del Teorema di Arrow.

2011-01-2017

Lezione di 3 ore. Il fenomeno small world: esperimento di Milgram e i sei gradi di separazione. Modelli per lo small world: il modello di Watt-Strogatz e i suoi limiti. Un modello per la ricerca decentralizzata. Ricerca miope. Analisi della ricerca miope nel modello per la ricerca decentralizzata con esponente di clustering ottimale nel caso unidimensionale. Cenni all'analisi del caso bidimensionale. Aderenza alla realtà del modello.

1909-01-2017

Questioni di compatibilità nei processi di diffusione. Modello. Analisi dell'occorrenza di cascate nella catena illimitata.

Lezione interrotta a questo punto causa freddo insostenibile in aula dovuto ad inattività dell'impianto di riscaldamento con una temperatura esterna inferiore allo zero.

1819-12-2016

Il ruolo dei weaky ties nei processi di diffusione. Capacità di cascata di una rete. Azione e coscienza collettive: il ruolo della pubblicità

1714-12-2016

Introduzione ai processi di diffusione nelle reti. Diffusione come coordination game. Cascate e clusters. Generalizzazione del modello: soglie non omogenee.

1607-12-2016

Analisi euristica del processo rich get richer per mostrare la power law. Effetti degli strumenti di ricerca e dei Recommendation Systems sul fenomeno Rich get richer

1505-12-2016

Popolarità e fenomeno power law. Modelli Rich Get Richer. Impredicibilità degli effetti rich get richer. La lunga coda

1430-11-2016

Un primo esperimento di herding ed un modello basilare generale nel quale definirlo. Cascate e decisioni sequenziali. Considerazioni generali sulle cascate.

1328-11-2016

Ripetizione degli argomenti trattati durante la precedente lezione. Page Rank e Random Walk in un grafo orientato. Modern Web-search.

 

Introduzione agli effetti informativi di una rete: seguire la folla. La regola di Bayes e il suo utilizzo per lo spam filtering.

1225-11-2016

Formalizzazione del Page Rank e dello Scaled Page Rank. Teorema di Perron e convergenza dello Scaled Page Rank.

1123-11-2016

Termine della prova della convergenza della procedura iterativa per il calcolo dei valori di hub e authority. Introduzione al Page Rank.

1021-11-2016

Web search mediante link analysis. Hub e authorities. Convergenza della procedura iterativa per il calcolo dei valori di hub e authority: prima parte della prova.

916-11-2016

La struttura del Web: reti di informazioni, ipertesto, memoria associativa. Precursori del Web. Evoluzione del Web: il WEb 2.0. Il Web come grafo diretto e le suat struttura bow-tie. Introduzione ai problemi di ricerca sul web

814-11-2016

Grafi completi segnati approssimativamente bilanciati e loro caratterizzazione

702-11-2016

Definizioni di bilancio strutturale in grafi non completi e loro equivalenza. Caratterizzazione e algoritmo che verifica se un grafo (non completo) è strutturalmente bilanciato.

626-10-2016

Relazioni positive e negative: grafi segnati. Definizione e caratterizzazione di bilancio strutturale in grafi completi. Definizione rilassata e sua caratterizzazione.

524-10-2016

Web-communities: definizione (Flake) e relazione fra web-communities e minimi tagli in un grafo. NP-completezza del problema di decidere dell'esistenza di una partizione di un grafo in due web-communities che separi una data coppia di nodi.

419-10-2016

Completamento del metodo di Girvan-Newman: calcolo diretto della betweenness di ogni arco, e metodo basato sul flusso. Richiami di teoria della complessità e del concetto di NP-completezza.

317-10-2016

Ricerca delle componenti coese in un grafo: graph partitioning, partizionamenti nidificati, metodi divisivi e metodi agglomerativi. Edge-betweennes e metodo di partizionamento di Girvan-Newman: introduzione. (Paragrafo 3.6 del testo)

212-10-2016

Esperimento di Granovetter: legami forti e deboli. Bridges e Local Bridges. Chiusura triadica, coefficiente di clustering e proprietà della chiusura triadica forte (STCP). Local bridges incidenti su nodi che soddisfano la STCP. Generalizzazione del modello: grafi pesati e Neighborhood Overlap, esperimento di Onnela. Buchi strutturali e capitale sociale.

110-10-2016

Introduzione al corso. Grafi e grafi aleatori. Il modello di Erdos-Renyi: grado medio, grado, componenti connesse.


Materiale didattico

Informazioni

Anno accademico2016-2017
Crediti6
SettoreINF/01
Anno1
Semestre1
PropedeuticitàNessuna

Programma

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

1) Teoria dei grafi e delle reti sociali.

    - Grafi, percorsi, connettività, distanza, ricerca

    - Chiusura triadica, importanza dei collegamenti deboli, struttura di rete in insiemi di grandi dimensioni,

      - indici di centralità e partizionamenti

    - Bilancio strutturale

2) Dinamiche nelle reti: modelli di popolazione.

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

    - Effetti rete: economia con e senza gli effetti rete, il problema di El Farol Bar

    - Power Law e fenomeno rich-get-richer: la popolarità come un effetto rete, modelli rich-get-richer e la long tail

3) Dinamiche nelle reti: modelli strutturali.

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


Testi di riferimento

David Easley, Jon Kleinberg, "Networks, Crowds, and Markets: Reasoning about a Highly Connected World", Cambridge University Press


Ricevimento studenti

Per appuntamento, da richiedere a mezzo posta elettronica


Modalità di esame

Prova orale eventualmente corredata da tesine