Busqueda De Subgrafos

ANÁLISIS DE LOS PRINCIPALES MÉTODOS DE BÚSQUEDA DE SUBGRAFOS EN UN GRAFO DE GRANDES DIMENSIONES


Autor: Lic. Isis Jiménez Romero






marzo de 2011

Resumen
Actualmente ha habido un gran incremento de la modelación de datos a través de grandes grafos en múltiples dominios como la web semántica, las redes sociales y las redes biológicas. En estas circunstancias, muchosinvestigadores están interesados en realizar consultas sobre esos grafos de la siguiente manera: Dado un grafo grande y una consulta , obtener las ocurrencias de en .
Es por esto que en este trabajo se realiza un estudio de los principales métodos que existen para la búsqueda de subgrafos en grafos de grandes dimensiones, creando una taxonomía de los mismos y realizando un análisis de sus principalescaracterísticas y áreas de aplicación.

Índice
Introducción 3
Capítulo 1: Introducción a los métodos de búsqueda de subgrafos en grafos grandes. Creación de una taxonomía. 7
1.1 Conceptos Preliminares 7
1.2 Bases de los métodos de búsqueda de subgrafos en grafos de grandes dimensiones 11
1.3 Taxonomía 13
Capítulo 2: Métodos analizados. Características. 15
2.1 GraphMatch 15
2.2Top-K 16
2.3 Graph-at-a-Time 18
2.4 TALE 19
2.5 GADDI 22
2.6 SUMMA 24
2.7 SAPPER 26
2.8 DSI 28
2.9 NOVA 29
2.10 Resumen de las características 31
Conclusiones 34
Bibliografía 35


Introducción
Existen muchos datos que pueden ser naturalmente modelados mediante grafos ya que estos pueden representar fácilmente entidades, sus atributos y susrelaciones con otras entidades. Las entidades serían los vértices del grafo y sus relaciones se representarían a través de las aristas del mismo. Por ejemplo, los grafos pueden ser utilizados para modelar estructuras complejas como:
• Compuestos químicos.
• Documentos XML.
• Redes de telecomunicaciones.
• Redes de interacción de proteínas.
• Redes sociales.
• La Web.
En la Web, por ejemplo, losvértices serían las páginas web y las aristas los enlaces entre las mismas. En una red social los individuos serían representados por los vértices y las relaciones entre ellos por las aristas. En una red de interacción de proteínas los vértices representarían a las proteínas y las aristas a las interacciones entre ellas.
Por otra parte, en muchos sistemas existe información interesante en lasrelaciones entre las entidades de datos. Para extraer esta información a menudo es necesario considerar tanto las relaciones como los datos contenidos en las propias entidades. Debido a esto las bases de datos de grafos han llamado la atención de las comunidades de bases de datos y minería de datos y se han realizado investigaciones sobre búsqueda de subgrafos en bases de datos de múltiples grafos,búsquedas inexactas de subgrafos, minería de subgrafos frecuentes, entre otras. Actualmente existe un gran interés en el análisis de grafos, lo que ha propiciado el desarrollo de diferentes algoritmos de indexado y búsqueda que operan sobre los mismos.
Las bases de datos de grafos pueden ser clasificadas en dos tipos: aquellas en las que existe una colección de muchos grafos relativamente pequeños,con menos de 300 vértices, y aquellas en las que existe un solo grafo considerablemente grande, con más de 10K vértices. En las del primer tipo las búsquedas de grafos consisten en encontrar todos los grafos dentro de una colección que contienen el grafo buscado. En las del segundo tipo el problema consiste en encontrar todas las ocurrencias del subgrafo en cuestión dentro del grafo. En losmétodos existentes para el segundo tipo de búsqueda existe actualmente menor trabajo investigativo y es sobre estos métodos que va a estar basado el presente trabajo.
La información más natural que puede ser extraída de un grafo es un subgrafo del mismo. En la recuperación de información donde el espacio de búsqueda son todos los subgrafos derivados de un grafo, las consultas consisten en grafos y...