Búsqueda de caminos relevantes en grafos RDF

Abstract

A partir de información representada en una colección de declaraciones en RDF (Resource Description Framework), esta representa intrínsecamente un multi-grafo etiquetado, dirigido. Con esto es posible utilizar algoritmos de búsqueda de caminos, que permiten encontrar la ruta más corta entre dos nodos. Con el fin de estudiar tecnologías basadas en el desarrollo de la web semántica, el tema de memoria propuesto consiste en la búsqueda de caminos relevantes para grafos en RDF. Para esto se construye una herramienta la que, a partir de un archivo con información en RDF, sea capaz de resolver consultas sobre caminos entre un nodo de origen y un nodo objetivo de tal manera que estos contengan información relevante para el usuario. La relevancia de los caminos se representa a través del peso asignado tanto a aristas, según su etiqueta, como a vértices, principalmente por métodos basados en su grado, PageRank o variaciones de estos. Para la búsqueda del camino mínimo entre un nodo origen y un nodo objetivo se implementa una versión del algoritmo de Dijkstra para grafos ponderados. Con el objetivo de tener la posibilidad de visualizar los resultados obtenidos y usar la herramienta en un contexto real para reportar resultados, es que se construye una aplicación que resuelva consultas de caminos entre dos nodos y represente esta respuesta gráficamente. Finalmente se realizan pruebas de rendimiento del algoritmo utilizado y pruebas para comparar los caminos resultantes de los distintos métodos de ponderación del grafo. Además se lleva a cabo una evaluación con usuarios para la validación de la solución obtenida.