DidaWiki

Questo progetto sostituisce l'esame scritto del corso. Svolto in C/C++ (o altro linguaggio da concordare con il docente), il progetto richiede di applicare le strutture di dati e gli algoritmi sui grafi all'analisi delle reti sociali (Social Network Analysis) utilizzando un particolare caso di studio: i dati disponibili sui film presenti nell'Internet Movie DataBase (IMDB).

È possibile in tal modo definire implicitamente un grafo non diretto G=(V,E) dove:

• i vertici in V sono gli attori e le attrici;
• gli archi non orientati in E collegano attori e attrici tra di loro: uv appartiene a E se e soltanto se u e v hanno recitato insieme in un film.

Il progetto si compone di varie fasi:

1. Scaricare e studiare il formato dei dati utilizzati da IMDB nel sito ufficiale. In particolare, ai fini del progetto sono necessari soltanto i seguenti file testuali, recuperabili al link:
   1. name.basics.tsv.gz: lista di attori, attrici, ecc.
   2. title.basics.tsv.gz: lista di film
   3. title.principals.tsv.gz: chi ha lavorato in quali film
2. Costruire una rete sociale rappresentata tramite il suddetto grafo G=(V,E) utilizzando tali file. Utilizzare le liste di adiacenza per memorizzare il grafo (ed evitare problemi di eccessiva occupazione di memoria).
3. Studiare la nozione di centralità dei nodi nei grafi, da applicare alle reti sociali, seguendo il materiale di questo tutorial online e il contenuto di questo paper.
4. Progettare e implementare degli algoritmi per la centralità, selezionandoli da quanto studiato sopra. Evitare gli algoritmi puramente numerici, essendo quest'ultimi studiati in insegnamenti dedicati, preferendo gli algoritmi che usano la struttura combinatoria del grafo descritto sopra.

Nota sul formato dei file. I file che terminano in *.tsv (tab separated values), sono utilizzati come formato semplice di scambio: ogni riga testuale rappresenta un “record” i cui campi sono separati da una spaziatura tabulata ('\t' in C/C++). . Occorre quindi leggere una linea alla volta di ciascun file e separare i campi. Per esempio, possiamo reindirizzare l'input da tastiera in modo che il comando di lettura cin legga da file invece che da tastiera, usando il comando:

freopen("file.tsv", "r", stdin);

A questo punto possiamo leggere ogni riga di file.tsv come stringa C++ ed estrarne i campi separati dal delimitatore '\t'. Iterando più volte sulla riga, possiamo ottenere tutti i campi.

using namespace std;
string s;
cin >> s;
string delimitatore = “\t”;
string campo = s.substr(0, s.find(delimitatore)); 

Per decomprimere i file *.tsv.gz lanciare il comando

gunzip *.tsv.gz

Per scorrere un file *.tsv usare il comando “less” (“more” oppure “cat”) seguito dal nome del file *.tsv, poiché alcuni editor potrebbero non essere in grado di aprire tali file.

Per vedere le prime N linee di un file *.tsv (o le ultime N righe) lanciare il comando “head -N” (oppure “tail -N”) seguito dal nome del file *.tsv, dove N è appunto il numero di righe che si vuole esaminare. Per vedere i singoli caratteri, i tab, ecc., lanciare il comando “od -c” seguito dal nome del file *.tsv.