Graph summarization on linked open data

One of the biggest challenges in the area of intelligent information management is the exploitation of the Web as a platform for data and information integration as well as for search and querying. The Linked Data paradigm has evolved as a powerful enabler for the transition of the current documentoriented Web into a Web of interlinked Data and, ultimately, into the Semantic Web. The most visible example of adoption and application of the Linked Data principles has been the Linking Open Data Project. Despite the wealth of information contained in the Web of Linked Data, ordinary Web users, not familiar with Semantic Web technologies and the specific application domains, are difficult to directly consume this information. In this research we study the summarization of graphs stored as Linked Open Data and its visualization, using heuristic and heterogeneous graph summarization algorithms. The purpose of the study was to understand the limitations and advantages of this algorithms in the summarization process and to the implement necessary changes to them in order to overcome this limitations creating a comparison chart and to obtain possible direction to guide future research on this topic. The selected set of algorithms were based on the Snap algorithm, these, are a group of graph summarization algorithms that can work on heterogeneous networks. In order to perform the observations we develop a testing platform based on the LDVM (Linked Data Visualization Model) with a Client-Server architecture. From the initial phase of the study the LOD problems when summarizing a graph were partially solved modifying using methods like Hub and compressing the graph as a post-processing practice. Within the set of modified Snap family of algorithms used in this work, the one that performed the best according to execution time and grouping number was the compressed, combined kSnap, Hub one. The advantages of this algorithm was the initial big grouping, contained iterative cycles for creating new groupings and cleaner output.

Una delle sfide pi`u importanti nella gestione intelligente delle informazioni `e costituita dallo sfruttamento del Web come piattaforma per l’integrazione di dati e informazioni, nonch´e per la ricerca e la risposta a query. Il paradigma dei linked data si `e evoluto come un potente strumento per la transizione dal Web orientato ai documenti a un Web di dati interconnessi e, infine, al Web semantico. L’esempio pi`u significativo di applicazione dei principi dei linked data `e stato il Linking Open Data Project. Nonostante la ricchezza delle informazioni contenute nel Web deilinked data, gli utenti ordinari delWeb hanno difficolt`a a utilizzare direttamente questi dati a causa della loro scarsa familiarit`a con le tecnologie del Web Semantico. La mia ricerca si occupa della sintesi dei grafici memorizzati come Linked Open Data e della loro visualizzazione, utilizzando algoritmi euristici e eterogenei di sommarizzazione di grafi. Lo scopo dello studio era comprendere i limiti e i vantaggi di questi algoritmi nel processo di sommarizzazione e implementare le modifiche necessarie per superare le limitazioni, operando un confronto sistematico in vista di una possibile direzione futura di ricerca in questo ambito. Il set di algoritmi selezionato si basava sull’algoritmo Snap: si tratta di un gruppo di algoritmi di sommarizzazione di grafi che possono funzionare su reti eterogenee. Per eseguire le nostre analisi abbiamo sviluppato una piattaforma di test basata sul modello LDVM (Linked Data Visualization Model) con un’architettura client-server. I problemi di sommarizzazione di grafi di Linked Open Data sono stati parzialmente risolti utilizzando metodi come Hub e comprimendo il grafo ottenuto in fase di post-elaborazione. Nell’ambito degli algoritmi Snap modificati utilizzati in questo lavoro, quello che si `e comportato meglio in base al tempo di esecuzione e al numero di raggruppamenti `e stato una versione di kSnap. I vantaggi di questo algoritmo sono il grande raggruppamento iniziale, i cicli iterativi per la creazione di nuovi raggruppamenti e i risultati pi`u trasparenti