Modelling dynamics of RDF graphs with formal concept analysis

Abstract

La Web Semántica es una red de datos organizados de tal manera que permite su manipulación directa tanto por humanos como por computadoras. RDF es el framework recomendado por W3C para representar información en la Web Semántica. RDF usa un modelo de datos basado en grafos que no requiere ningún esquema fijo, provocando que los grafos RDF sean fáciles de extender e integrar, pero también difíciles de consultar, entender, explorar, resumir, etc. En esta tesis, inspirados en formal concept analysis (un subcampo de las matemáticas aplicadas, basados en la formalización de conceptos y jerarquı́as conceptuales, llamadas lattices) proponemos un data-driven schema para grandes y heterogéneos grafos RDF La idea principal es que si podemos definir un formal context a partir de un grafo RDF, entonces podemos extraer sus formal concepts y computar una lattice con ellos, lo que resulta en nuestra propuesta de esquema jerárquico para grafos RDF. Luego, proponemos un álgebra sobre tales lattices, que permite (1) calcular deltas entre dos lattices (por ejemplo, para resumir los cambios de una versión de un grafo a otro), y (2) sumar un delta a un lattice (por ejemplo, para proyectar cambios futuros). Mientras esta estructura (y su álgebra asociada) puede tener varias aplicaciones, nos centramos en el caso de uso de modelar y predecir el comportamiento dinámico de los grafos RDF. Evaluamos nuestros métodos al analizar cómo Wikidata ha cambiado durante 11 semanas. Primero extraemos los conjuntos de propiedades asociadas a entidades individuales de una manera escalable usando el framework MapReduce. Estos conjuntos de propiedades (también conocidos como characteristic sets) son anotados con sus entidades asociadas, y posteriormente, con su cardinalidad. En segundo lugar, proponemos un algoritmo para construir la lattice sobre los characteristic sets basados en la relación de subconjunto. Evaluamos la eficiencia y la escalabilidad de ambos procedimientos. Finalmente, usamos los métodos algebraicos para predecir cómo el esquema jerárquico de Wikidata evolucionaría. Contrastamos nuestros resultados con un modelo de regresión lineal como referencia. Nuestra propuesta supera al modelo lineal por un gran margen, llegando a obtener un root mean square error 12 veces más pequeño que el modelo de referencia. Concluimos que, basados en formal concept analysis, podemos definir y generar un esquema jerárquico a partir de un grafo RDF y que podemos usar esos esquemas para predecir cómo evolucionarán, en un alto nivel, estos grafos RDF en el tiempo.