Temi di tesi

Di seguito, alcuni temi di tesi disponibili (ad eccezione di quelli sbarrati).

Social Network Anonymization/Deanonymization using Evolution Strategy

Le reti sociali (social network o più semplicemente SN) e la loro più recente crescita rappresentano una fonte inestimabile di dati i quali, se rilasciati pubblicamente, si prestano ad una vasta serie di analisi (e relativi problemi correlati). La possibilità di mettere i dati a disposizione di tutti si scontra con il problema della privacy: una SN rappresenta una rete tra individui, per i quali un certo livello di privacy deve essere garantito. In quest’ottica, due problemi particolarmente interessanti sono: Social Network Anonymization e Social Network deanonymization.

Data una SN, il primo problema riguarda la possibilità di modificare la SN in modo tale da preservare la privacy degli utenti e rendere così la rete anonimizzata; data una SN anonimizzata, il secondo problema consiste nel re-identificare un particolare individuo e/o attribuire una qualche proprietà ad uno o più individui (la quale era stata originariamente resa anonima).

Entrambi i problemi possono essere modellati come problemi su grafi. Ad esempio, il problema della deanonymization consiste nel prendere in input una coppia di grafi e definire un algoritmo che associ correttamente i nodi di H (la rete anonimizzata) ai nodi di G (la rete originale). Un algoritmo evolutivo potrebbe essere utilizzato per questo task.

Quali fatiche spetterebbero allo studente interessato?

  • Studio del task e della letteratura disponibile,
  • Studio gli algoritmi evolutivi,
  • Definizione e implementazione di un algoritmo (o più di uno) evolutivo per risolvere il task,
  • Validazione dell’algoritmo tramite una serie di esperimenti.

Analisi e caratterizzazione della rete degli artisti di Spotify e sviluppo di un Recommender System

Spotify è un servizio musicale digitale che consente di ascoltare brani tramite una interfaccia web, desktop o mobile. Ad ogni artista sono associati differenti metadati, tra cui una lista di artisti correlati. A partire da queste informazioni, si può creare un grafo degli artisti, dove ogni nodo è un artista ed esiste un arco tra il nodo a e il nodo b se a appare nella lista degli artisti correlati di b.

Questo grafo può essere usato come base di partenza per diversi tipi di analisi. Alcuni esempi:

  • Caratterizzazione della rete tramite classiche misure usate in network science;
  • Un sistema di Information Retrieval intelligente (rispondere a query del tipo “voglio ascoltare degli artisti simili ad X ma che facciano genere Y”);
  • Un Recommender System (dati gli ascolti di un utente, suggerire nuovi artisti da ascoltare).

Il grafo (non necessariamente contenente tutti i possibili artisti presenti su Spotify) può essere creato a partire dalle API ufficiali di Spotify.

Quali fatiche spetterebbero allo studente interessato?

  • Definizione e implementazione di un crawler per la creazione del grafo degli aristi,
  • Analisi generali del grafo creato con tecniche classiche di network science,
  • Web App che permetta di visualizzare una porzione del grafo, statistiche e proprietà correlate,
  • Creazione di un Recommender System,
  • (opzionale) Definizione e implementazione di un sistema di Information Retrieval intelligente,
  • (opzionale) Esistenza ed analisi di sottostrutture particolari nel grafo degli artisti, e.g., clique e k-plexes.

Altri temi di tesi

Social Network Analysis on Reddit

Reddit è una online social platform. È stata fondata nel 2005 e ad oggi conta più di 430 milioni di utenti attivi mensilmente. Ruota attorno al concetto di subreddit, una community in cui gli utenti interagiscono tra loro condividendo contenuti (testo, immagini e link esterni). I dati riguardanti Reddit sono disponibili pubblicamente, e questo ha permesso il proliferare di nuove analisi e ricerche interessanti al riguardo.

Differenti nuovi tipi di problemi possono essere affrontanti utilizzando questi dati. Un esempio è investigare per la presenza di strutture particolari (quali k-trusses e k-plex) e caratterizzarne la proprietà.

Multi-Parameterized Edit Distance

La Multi-Parameterized Edit Distance (MPED) è una generalizzazione della edit distance basata su alfabeti disgiunti. Specializzazione di un framework per la comparazione di sequenze basate sull’identità, è stata ampiamente utilizzata in diversi contesti, quali l’analisi di serie temporali e la bioinformatica.

Esistono delle estensioni fortemente interessanti della MPED che non sono state ancora oggetto di studio, come ad esempio l’estensione all’analisi di serie temporali multivariate e stringhe bidimensionali.

Altri temi riguardanti la MPED sono disponibili, tra cui:

  • Implementazione della MPED in Rust,
  • Studio, analisi e implementazione di una nuova metaeuristica per la MPED,
  • Studio, analisi e implementazione di tecniche avanzate per il calcolo della edit distance (da utilizzare all’interno della MPED).
Ulteriori informazioni per questi temi di tesi sono disponibili qui.