Progetto (parte prima dell'esame di Algoritmi e Strutture di Dati / Informatica II)

Progetto in C/C++ (o altro linguaggio da concordare con il docente) per 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, le attrici, i registi e i film; possono essere etichettati (per esempio, l'anno di produzione di un film, il genere o le keyword che lo caratterizzano);
• un arco non orientato (u,v) appartiene a E se e soltanto se u è un film e v è un attore che vi ha recitato oppure un regista che ha diretto tale film; gli archi possono essere etichettati con ulteriori informazioni (per esempio, se v ha ricevuto un premio per il film u).
Il progetto si compone di varie fasi:
1. Scaricarsi il dump di IMDB dal sito ufficiale. In particolare, ai fini del progetto sono necessari soltanto i seguenti file testuali, la cui struttura va analizzata utilizzando le spiegazioni contenute all'inizio e alla fine dei file stessi:

     2011 May 20 12:14  actors.list.gz  (178928095 bytes)     lista di attori (e film in cui hanno recitato)
     2011 May 20 12:17  actresses.list.gz  (97713547 bytes)   lista di attrici (e film in cui hanno recitato) 
     2011 May 20 12:18  directors.list.gz  (18395367 bytes)   lista di registe/i (e film che hanno diretto)    
     2011 May 20 12:26  aka-names.list.gz  (5405940 bytes)    nomi equivalenti di attori/attrici/registe/i
     2011 May 20 12:24  movies.list.gz  (19190799 bytes)      lista dei film (con anno di produzione) 
     2011 May 20 12:24  aka-titles.list.gz  (6206270 bytes)   titoli equivalenti o tradotti dei film
     2011 May 20 12:26  genres.list.gz  (9742278 bytes)       genere dei film 
     2011 May 20 12:29  keywords.list.gz  (26970164 bytes)    keyword dei film 
   

   Potrebbe risultare utile avere anche dei collegamenti tra film (citazioni, rifacimenti, seguiti, ecc.):

     2011 May 20 12:27  movie-links.list.gz  (12112812 bytes) collegamenti tra film
   

2. Costruire un driver di lettura che, letti i file suddetti da disco, crea il corrispettivo grafo implicito G=(V,E) (definito sopra) in memoria principale. La rappresentazione di G è mediante liste di adiacenza: se occorrono problemi di memoria, scegliere un sottoinsieme di attori, attrici, registe/i e film per costituire un insieme ridotto di vertici V (di conseguenza, si induce il corrispondente insieme ridotto degli archi E).
3. Anche se non strettamente necessario alla stesura del progetto, è consigliabile leggersi il capitolo di Lei Tang e Huan Liu su Graph mining applications to social network analysis per avere un'idea sugli argomenti di base di SNA.
4. Dare una definizione di attore/attrice famoso in termini di proprietà combinatoria sul grafo G. Per esempio, il fatto di aver vinto un premio o aver recitato in un film diretto da un regista che ha vinto un premio può essere facilmente verificato in G (a tal fine, il file keywords.list.gz contiene alcune parole chiavi utili per etichettare i film: per esempio, oscar-winner, academy-award, blockbuster, cult, box-office-hit, ecc.). Estendere tale idea per ottenere una definizione in termini di G: tenendo presente che possono esistere varie definizioni di "fama", sceglierne una a piacere e implementare l'algoritmo che trova i k attori/attrici più famosi/e secondo la definizione scelta.
5. Progettare e implementare un algoritmo che procede nel seguente modo: prende in ingresso un insieme Z (contenuto nell'insieme dei vertici V) di attori/attrici/registi/e/film preferiti e suggerisce tre film (non in Z) che hanno contenuti simili ai film che sono indotti da Z. Un film u è indotto da Z se u appartiene a Z oppure almeno uno degli attori/attrici che hanno recitato in u appartiene a Z oppure il regista di u appartiene a Z.