I grafi sono presenti in una gran quantità di applicazioni e lo studio delle loro proprietà consente di capirne la struttura. In questo corso, si studiano algoritmi efficienti per affrontare i seguenti due problemi: l'analisi e il confronto di una collezione di molti grafi relativamente piccoli e l'analisi delle proprietà di un solo grafo molto grande.
Lo scopo di questo corso è quello di introdurre gli studenti alla progettazione, all'analisi e alla sperimentazione di algoritmi per l'analisi di grafi. Alla fine del corso gli studenti avranno una buona conoscenza dei fondamenti dell'analisi di grafi e saranno in grado di valutare metodi per l'analisi di grafi, di formulare e risolvere problemi legati ai grafi e di analizzare grafi di grandi dimensioni.
Prerequisiti
Gli studenti devono (1) avere una conoscenza di base di algoritmi e strutture dati, (2) avere una conoscenza di algebra lineare, (3) avere familiarità con la teoria della probabilità e la statistica di base, (4) avere buone capacità di programmazione (per esempio, in Java).
Metodi Didattici
Lezioni frontali.
Modalità di verifica apprendimento
Il voto finale sarà distribuito tra un esame orale (al momento dell'appello), una presentazione di un articolo e un piccolo progetto pratico, secondo il seguente schema: 25% progetto e relazione, 25% presentazione di un articolo, 50% esame orale.
Programma del corso
Matching e calcolo di distanze in grafi. Calcolo di distanze basate su trasformazioni. Ricerca di sottostrutture frequenti. Clustering. Reti sociali: preliminari e proprietà. Rilevamento di comunità. Classificazione collettiva. Predizione dei collegamenti. Analisi dell'influenza sociale.