Analisi di reti

Algoritmo di ricerca miope nell'anello, sua 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)

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

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

Considerazioni su significato e portata del teorema di Arrow. Alternative ordinate, preferenze single peaked e teorema del votante mediano (cap 23, par. 23.6).

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

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. Tornei e agende. Sistemi di voto posizionali e alternative irrilevanti. (Cap. 23, par. 23.1-23.4)

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

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

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

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)

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

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

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

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

Ancora sul Page rank. Interpretazione del page rank in termini di random walk (cap. 14, par. 14.6).

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

Termine della prova di convergenza del metodo Hubs and Authorities. Page Rank. Modern web search. (Cap. 14, par. 14.3, 14.4, 14.6)

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

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

La struttura del web (cap. 13).

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

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

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)

Individuazioni di comunità: metodi divisivi e metoti agglonerativi; partizionamento gerarrchico. Il metodo di Girvan-Newman. (Par. 3.6)

Posizioni di nodi ed archi rispetto alle regioni coese di una rete e capitale sociale (par. 3.5). Prime definizioni di comunità: we-communities e cut-communities, loro relazione, complessità del partizionamento di un grafo in due web-communities (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, social media e passive engagement. (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 1: web-communities e cut-communities

Dispensa 2: introduzione informale alla teoria della complessità (per gli studenti del CdL in Matematica)

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

Per appuntamento, da richiedere a mezzo posta elettronica

Prova orale eventualmente corredata da tesine