Analisi di reti

Docenti: Miriam Di Ianni, Luciano Guala'

Comunicazioni

Struttura del corso

12-09-2024 16:57

Il corso di Analisi di reti è suddiviso in due moduli:

 

MODULO 1: 6 cfu, tenuto dalla Prof. Di Ianni nel periodo ottobre - inizio dicembre

 

MODULO 2: 3 cfu, tenuto dal Prof. Gualà nel periodo termine MODULO 1 - fine corso

 


Lezioni

1007-11-2024

Lezione di 3 ore. Capacità di cascata di una rete: non occorrenza di una cascata completa nel caso q maggiore di 1/2. Processi di diffusione in caso di nodi eterogenei. Azione collettiva. 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, 19.7-B e 19.7-C, lucidi AR-ProcessiDiffusione da lucido 26 alla fine).

904-11-2024

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

831-10-2024

Lezione di 3 ore. Partizionamento in comunità: metodi partitivi e metodi agglomerativi. 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 par. 3.6 e par. 3.3 e 3.5, lucidi AR-GrafiStrutturaDisomogenea dal lucido 34 al termine)

 

 

728-10-2024

Lezione di 3 ore.

Introduzione alla teoria della NP-completezza (lucidi AR-IntroComplexity).

NP-completezza del problema di partizionare un grafo in due strong web- communities. (Dispensa 2 e lucidi AR-GrafiStrutturaDisomogenea dal lucido 21 al lucido 35).

 

624-10-2024

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)

 

523-10-2024

Lezione di 3 ore. 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. Modello per la ricerca decentralizzata: coefficiente di clustering ottimale. Dimostrazione nel caso dell'anello. (Cap. 20, par. 20.1-20.4 e 20.7.B, lucidi AR-SmallWorld fino al lucido 36).

421-10-2024

Lezione di 3 ore. Grafi geometrici aleatori: prova della delimitazione inferiore al minimo raggio di connessione. (Dispensa 1 e lucidi AR-GrafiGeometriciAleatori, dal lucido 25 al termine,  disponibili in questa pagina)

317-10-2024

Lezione di 3 ore. mpredicibilità 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.

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)

 

216-10-2024

Lezione di 3 ore. 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). Analisi del modello (pag. 490-493). Lucidi AR-PoverLaw

114-10-2024

Lezione di 3 ore. 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)


Materiale didattico

Lucidi delle lezioni: processi di diffusione

Lucidi delle lezioni: reti come grafi dalla struttura disomogenea

 

Dispensa 2: cut-communities e web-communities

Lucidi delle lezioni: breve introduzione alla teoria della NP-completezza

Lucidi delle lezioni: un modello per lo small world e la ricerca decentralizzata

Lucidi delle lezioni: grafi geometrici aleatori e reti wireless

Dispensa 1: grafi geometrici aleatori e minimo raggio di connessione

Lucidi delle lezioni: il modello di Barabasi-Albert, un modello per la power law

Lucidi delle lezioni: introduzione al corso e modello di Erdos-Renyi

Informazioni

Anno accademico2024-2025
Crediti9
SettoreINF/01
Anno1
Semestre1
PropedeuticitàNessuna

Programma

MODULO 1 (6 cfu, prof.ssa Di Ianni):

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

       - Comportamento a cascata: diffusione, cascate e cluster, capacità di una cascata, il bilinguismo

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

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

 

 

MODULO 2 (3 cfu, prof. Gualà):

 


Testi di riferimento

MODULO 1:

       - 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, a cura del docente, che saranno resi disponibili in questa pagina

 


Ricevimento studenti

Su richiesta degli studenti


Modalità di esame

L'esame consiste in una prova orale.

 

Gli studenti che lo desiderano possono sostenere separatamente le prove dei due moduli, in qualsiasi ordine. In Tal caso, l'esame verrà verbalizzato solo nel momento in cui le prove per entrambi i moduli saranno state superate.

 

Al fine di offrire agli studentì una maggiore elasticità nella calendarizzazione dei propri esami, per sostenere l'esame è sempre necessario inviare una e-mail ai docenti di entrambi i moduli (o al docente del modulo di cui si intende sostenere la prova) mediante la quale è possibile concordare la data nella quale effettuare la prova orale.