Analisi di reti

Analisi dell'algoritmo di ricerca decentralizzata: esponente ottimale nel caso unidimensionale, generalizzazione a dimensioni maggiori ed utilizzo di esponenti diversi (pag.554-564)

Il fenomeno Small World: l'esperimento di Milgram e i sei gradi di separazione, il modello di Watts-Strogats, ricerca decentralizzata e modello che la supporta. Analisi empirica del modello per la ricerca decentralizzata. (Cap. 20, pag 537-554)

Prefenze single peaked e teorema del votante mediano. Sistemi di voto come mezzo di aggregazione dell'informazione. Il teorema della giuria di Condorcet (solo enunciato). Voto non sincero, decisioni di giuria e regoòa dell'unanimità (cap. 23, par. 23.6-23.9)

Dimostrazione del Teorema di Arrow (pag. 675-678). Preferenze singlr-peaked ed enunciato del teorema del votante mediano (par. 23.6)

Principio di uniformità e principio di indipendenza delle alternative irrilevanti. Profili e alternative polarizzanti (pag.673-675). Enunciato del Teorema di Impossibilità di Arrow (par. 23.5)

Sistemi di voto come strumenti di aggregazione dell'informazione. Espressione delle preferenze individuali: relazioni binarie, ranking e loro equivalenza. Voto a maggioranza e paradosso di Condorcet; tornei e il ruolo delle agende. Voto posizionale e il ruolo delle alternative irrilevanti (cap. 23, pag. 645-657)

Analisi del modello Rich get Richer (par. 18.7). Effetti sulla popolarità degli strumenti di web-searc e sistemi di raccomandazioni (pr. 18.6)

Capacità di cascata nella catena in caso di compatibilità (pag 526-531).

Popolarità e fenomeno Riche get Richer: power laws, modello di Erdos Renyi e un modello che tenga conto del fenomeno Rich get Richer, impredicibilità del fenomeno, la lunga coda (cap, 18, par. 18.1-18.5)

Lezione di 3 ore a completamento del recupero della lezione del 13/11/2019.

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 (pag. 517-522).

Questioni di compatibilità: un modello per il bilinguismo, versione della capacità di cascata nel caso del bilinguismo (pag. 522-526)

Lezione di tre ore a parziale recupero della lezione del 13/11/2019.

Diffusione nelle reti: un modello di diffusione. Cascate e cluster. Il ruolo dei weak tie. Nodi eterogenei. Azione collettiva (cap. 19, par. 19.1-19.6)

Un modello per cascate informative. Decisioni sequenziali e cascate (cap. 16, par. 16.5, 16.6, 16.7)

Introduzione agli effeti rete: effetti positivi (diffusione, che sarà ripresa più avanti), negativi (brevi cenni al problema di El Farol Bar, pag. 470), effetti informativi.

Cascate informative /herding): cap. 16, pag. 425-436

Bilancio strutturale in grasi segnati non completi: definizione e caratterizzazioni (par. 5,5-A, pag. 119-127)

Page rank e random walks (pag. 376-378). Evoluzione del web e corrispondente link analysis (par. 14.4).

Reti sociali: relazioni positive e negative, bilancio strutturale forte e debole e loro caratterizzazioni (cap. 5, par. 5.1-5.4)

Completamento della prova di convergenza di Hub e Authorities. Page rank (par. 4.3 e par. 4.6 pag. 374-376)

Il metodo Hubs and Authorities (Cap. 14, par. 14.2, 14.6 pag. 368-374).

La struttura del web (cap. 13). Link analysis e ricerca sul web (Cap. 14, par. 14.1, 14.2).

Modellare il traffico in una rete mediante la teoria dei giochi: traffico all'equilibrio, il paradosso di Braess, equilibrio e costo sociale (cap. 8)

Indici di centralità, betweenness e metodo di Girvan-Newman per il partizionamento di un grafo in comunità (par.3.6). Chiusura, buchi strutturali e il capitale sociale (par. 3.5).

Partizione di un grafo in comunità: metodi divisivi e metodi agglomerativi; pertizionamento gerarchico. Web e cut communities e loro relazione

Introduzione alla teoria della NP-completezza. NP-completezza del problema del partizionamento in due web-communities

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

Mercoledì al termine della lezione, oppure su appuntamento da richiedere a mezzo posta elettronica

Prova orale.

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.

Si comunica agli studenti che l'ultima data utile per sostenere l'esame nella sessione estiva è 1l giorno 17 luglio.