Analisi di reti

Considerazioni su significato e portata del teorema di Arrow e del teorema del votante mediano. 

Voto come forma di aggregazione dell'informazione e Teorema della giuria di Condorcet. Voto non sincero. Giurie e regola dell'unanimità. Sistemi di voto in relazione alle cascate informative. (Cap. 23, par. 23.7-23.9)

Lezione di tre ore (ad anticipare le lezioni di gennaio).

Il teorema di impossibilità di Arrow (cap. 23, par. 23.5 e 23.11).

Alternative ordinate, preferenze single peaked e teorema del votante mediano (cap 23, par. 23.6).

Sistemi di voto a maggioranza e paradosso di Condorcet. Tornei e agende. Sistemi di voto posizionali e alternative irrilevanti. Enunciato del Teorema di Impossibilità di Arrow e prima parte della sua dimostrazione (Cap. 23, par. 23.3-23.5)

Lezione di tre ore (ad anticipare le lezioni di gennaio).

Algoritmo di ricerca miope nell'anello: completamento dell'analisi nel caso q=0; cenni sul suo comportamento nel caso q=0 e discussione dei casi 0<q<1 e q>1. Considerazioni in supporto dell'ottimalità del modello q=dimensione dello spazio nel caso della griglia (Cap 20, par. 20.7).

Introduzione ai sistemi di voto. Espressione delle preferenze mediante relazioni binarie transitive e mediante ranking e loro equivalenza. Sistemi di voto a maggioranza e paradosso di Condorcet (Cap. 23, par. 23.1-23.4).

Algoritmo di ricerca miope nell'anello, inizio della sua analisi nel caso q=0 (Cap 20, par. 20.7)

Lezione di tre ore (ad anticipare le lezioni di gennaio).

Un modello per la diffusione in presenza di compatibilità: il bilinguismo (par. 19.7 C).

Il fenomeno small world: i sei gradi di separazione e il modello di Watts-Strogatz, la ricerca decentralizzata ed un modello per essa, analisi empirica dei modelli considrati, impatto della struttura centro-peroferia (cap. 20, par. 20.1-20.6).

Capacità di cascata di una rete: catena, griglia, delimitazione inferione per topologie generiche (cap. 19, par. 19.7 A e B).

Lezione di tre ore (per anticipare le lezioni di gennaio).

Processi di diffusione nelle reti. Modello di un processo di diffusione. Relazione fra cluster ed occorrenza delle cascate. Il ruolo dei weak ties. (Cap. 19, par. 19.1-19.4).

Estensione del modello base di diffusione:nodi eterogenei. Azione collettiva e conoscenza comune (cap. 19, par. 19.5, 19.6).

Analisi del modello Rich get richer (par. 18.7). La lunga coda (par. 18.5). Gli effetti dei motori di ricerca e i Recommendation Systems (par. 18.6)

Lezione di 3 ore a completamento del recupero delle lezioni perse.

Cascate informative: un semplice modello generale, relazioni fra decisioni sequenziali e insorgenza di cascate informative, considerazioni conclusive (cap. 16, par. 16.5-16.7).

Popolarità e fenomeno power law. Modelli Rich Get Richer. Impredicibilità degli effetti rich get richer ((cap. 18, par. 18.1-18.4).

La regola di Bayes applicata allo spam filtering (cap. 16, par. 16.3).

Cascate informative: un semplice esperimento di herding e sua analisi (cap. 16, par. 16.1-16.4)

Lezione di tre ore, a parziale recupero delle lezioni perse.Ripetizione della parte finale della convergenza del metodo hub-authorities e dimostrazione che la matrice che lo governa è semidefinita positiva.

Page Rank e sua interpretazione in termini di random walk (cap. 14, par. 14.3 e 14.6). Modern web search. (Cap. 14, par. 14.4)

Lezione di tre ore, a parziale recupero delle lezioni perse.

Link analysis e ricerca sul web: il metodo Hubs and Authorities (Cap. 14, par. 14.1, 14.2, 14.6 fino pag. 374).

Lezione di tre ore, a parziale recupero delle lezioni perse. 

Grafi approssimativamente bilanciati (Cap. 5, Par. 5.5 B).

La struttura del web (cap. 13).

Lezione di tre ore, a parziale recupero delle lezioni perse. 

Omofilia, selezione e influenza sociale (cenni: par. 4.1 e 4.2).

Relazioni positive e negative; bilancio strutturale in grafi completi: definizione e caratterizzazione. Bilancio strutturale in grafi non completi. (Cap 5, par. 5.1, 5.2).

Bilanciamento debole: definizione e caratterizzazione (cap. 5, par. 5.4).

Caratterizzazazione del bilancio strutturale in grafi non completi (Cap. 5 Par. 5.5 A).

Lezione di 3 ore, a parziale recupero delle lezioni saltate. Complessità del partizionamento di un grafo in due web-communities (dispensa 2, in questa pagina). Individuazioni di comunità: metodi divisivi e metoti agglonerativi; partizionamento gerarrchico. Il metodo di Girvan-Newman. (Par. 3.6)

Prime definizioni di comunità: web-communities e cut-communities, loro relazione (dispensa 2, in questa pagina). Breve introduzione alla teoria della complessità (dispensa 1, in questa pagina).

Legami forti e deboli, bridge e local bridge, l'esperimento di Granovetter. Rilassamento del modello, esperimento di Onnela e coincidenza dei risultati sperimentali con le previsioni teoriche. Forza dei legami, capitale sociale. (Pag. 43-58)

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

Dispensa 3 (per gli studenti del Corso di Laurea in Matematica, ai fini dell'acquisizione di 2 CFU aggiuntivi): Clustering

Dispensa 2: web- e cut-communities

Dispensa 1: breve introduzione alla teoria della complessità

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.

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

Per appuntamento, da richiedere a mezzo posta elettronica

Prova orale eventualmente corredata da tesine.

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.