Algoritmi di Outbreak Detection nella Diffusione su Grafi

Il problema dell’Outbreak Detection si inserisce all’interno di un ambito di ricerca piuttosto vasto e trasversale che comprende l’analisi della diffusione di epidemie, lo studio della propagazione di informazioni e notizie sui social network e addirittura l’individuazione tempestiva di agenti contaminanti che si diffondono su infrastrutture critiche come, ad esempio, le reti idriche. Se disponessimo di alcuni sensori da poter posizionare sulle reti che modellano tali contesti, dove sarebbe più conveniente collocarli per rilevare le diffusioni il prima possibile? All’interno di questa tesi vengono analizzati e testati sperimentalmente i principali algoritmi risolutivi per questo problema. La tesi si focalizza in particolar modo sull’approccio risolutivo greedy e sulle garanzie teoriche delle soluzioni approssimate ottenute tramite esso. Grazie alle sperimentazioni è stato possibile confrontare l’algoritmo greedy con altri metodi canonici basati sulla centrality dei nodi mettendo gli algoritmi alla prova sotto differenti condizioni.