Scienza delle Reti

Obiettivo: L'obiettivo del corso č presentare la storia, i concetti e la matematica della moderna scienza delle reti. Questa č la prima parte del corso. Seguirą una seconda parte a cura di Stefano Mizzaro.

Programma:

  1. Classi: reti tecnologiche, reti sociali, reti di informazione, reti biologiche.
  2. Centralitą: per grado, per autovettore, per vicinanza, per intermediazione.
  3. Struttura: componenti connesse, cammini minimi, distribuzione dei gradi dei vertici, transitivitą, omofilia.

Libro: Mark Newman. Networks: An Introduction. Oxford University Press, 2010.

Letture: Albert-Lįszló Barabįsi. Linked. Plume Books, 2003.

Software: il pacchetto igraph in ambiente R.

Film: Babel, di Alejandro Gonzįlez Ińįrritu, 2006.

Appunti: concatenare l'URL della mia pagina Web con teaching/network/index.html

Modalitą di esame: L'esame per la prima parte del corso consiste in un orale obbligatorio pił un eventuale progetto o approfondimento. L'orale č su appuntamento, e verrą fissato entro due settimane dalla richiesta. La sola prova orale garantisce un punteggio di al massimo 28. Un incremento fino a due punti si ottiene facendo il progetto o l'approfondimento per una delle due parti del corso (prima o seconda).

Il progetto consiste nella costruzione e nell'analisi (con i metodi visti in classe) di una rete di dimensioni significative a scelta del candidato. Il progetto deve essere documentato in una relazione. La relazione dovrą includere una descrizione sommaria della rete analizzata, una descrizione delle analisi fatte e dei risultati ottenuti. La rete e la relazione (in formato PDF) debbono essere spediti al docente al momento della prenotazione dell'orale (compressi in un archivio ZIP).

L'approfondimento consiste nello studio individuale e nella preparazione di un seminario, da svolgersi in data da concordare, su uno dei seguenti argomenti (scrivere al docente per avere una copia originale degli articoli da approfondire):

  1. Four degrees of separation
  2. The anatomy of the Facebook social graph
  3. Mining Twitter in the cloud: a case study
  4. Viscous democracy for social networks
  5. The strength of weak ties
  6. The Perron-Frobenius Theorem and the ranking of football teams
  7. PageRank: standing on the shoulders of giants
  8. Algoritmi per il partizionamento di reti (Capitoli 11.2, 11.3, 11.4, e 11.5 del libro di testo)
  9. Algoritmi per la rilevazione di comunitą nelle reti (Capitoli 11.2, 11.6, 11.7, 11.8, 11.9, 11.10 e 11.11 del libro di testo)

Proposte di tesi

  1. Analisi della rete sociale Twitter. Riferimenti: Mining Twitter in the Cloud: A Case Study
  2. La scienza delle reti nello sport. Riferimenti: The Perron-Frobenius Theorem and the ranking of football teams

Dataset

  1. Pajek
  2. Newman
  3. Barabįsi
  4. Indiana University
  5. Arenas
  6. UCINet

Laboratorio

  1. Bottlenose dolphins