Modeling, classification and analysis of graph structures

Le rappresentazioni basate su grafi hanno visto crescere negli anni la loro popolarità per la loro capacità di descrivere in maniera naturale un ampio numero di sistemi caratterizzati da una forte componente strutturale. Esempi concreti includono l’uso di grafi per rappresentare forme, reti metaboliche, interazioni proteiche, collaborazioni scientifiche e mappe stradali. In questo campo, la sfida è quella di sviluppare strumenti efficienti per l’analisi e la classificazione di grafi, un compito reso ancora più arduo dalle ricche potenzialità espressive dei grafi. La tesi comincia con l’introduzione di un nuovo algoritmo per l’estrazione di un grafo indiretto da un oggetto tridimensionale. Mostriamo quindi come imparare un modello generativo in grado di catturare le variazioni strutturali all’interno di un insieme di grafi, e come selezionare il modello ottimale usando un classico approccio MML, oltre ad un nuovo sistema basato sulla teoria dell’informazione. Spostiamo a questo punto l’attenzione dagli algoritmi di classificazione generativi a quelli deterministici, ed in questo contesto introduciamo una nuova famiglia di kernel su grafi che si basano su un’analisi meccanico-quantistica delle struttura dei grafi. Questo ci porta alla parte finale della tesi, dove proponiamo una serie di algoritmi per l’analisi della struttura dei grafi che si basano sull’idea comune di sfruttare la correlazione tra simmetrie strutturali e i pattern di interferenza tipici dei cammini quantistici.