Please use this identifier to cite or link to this item: http://repositorio.udec.cl/jspui/handle/11594/2081
Title: Descubrimiento eficiente de subgrafos densos en superposición y su aplicación para la compresión de grafos
Authors: Hernández Rivas, Cecilia , supervisora de grado
Mella Ibáñez, Carlos Felipe
Keywords: Gráficos por Computador;Teoría de Grafos;Algoritmos Computacionales;Heurística
Issue Date: 2016
Publisher: Universidad de Concepción . Facultad de Ingeniería. Departamento de Ingeniería Informática y Ciencias de la Computación
Abstract: La exploración de algoritmos eficientes para descubrir patrones en grafos es un tema que ha recibido un renovado interés en los últimos años, debido al rápido crecimiento que se ha dado en grafos vistos en ámbitos como las redes sociales, la web, estudio de interacciones entre proteínas y muchos otros. El procesar estos grafos muy grandes es un desafío: los altos requerimientos de memoria principal pueden hacer infactible la ejecución directa de algoritmos de búsqueda de patrones, mientras que la alta complejidad computacional de algunos de estos algoritmos puede volver impráctica su aplicación. Para tratar las limitaciones de espacio y procesamiento, la comunidad científica ha propuesto, entre otras técnicas, el uso de representaciones compactas para grafos que soportan la ejecución de algunas operaciones básicas de consulta directamente sobre la estructura comprimida; a partir de estas operaciones básicas es posible implementar algoritmos clásicos de grafos. Esto permite relajar los requerimientos de memoria principal para su ejecución. En particular, en grafos de la web y redes sociales, Hernández y Navarro propusieron una estructura compacta para grafos basada en subgrafos densos que incluye una combinación de cliques y bicliques, que son descubiertos utilizando heurísticas eficientes. Estos subgrafos no tienen superposición de aristas entre ellos. Esta memoria de título presenta una propuesta para expandir las herramientas de descubrimiento de Hernández y Navarro para incluir subgrafos con superposición entre ellos. Los resultados obtenidos usando grafos reales de la web y redes sociales muestran un incremento del número, tamaño promedio y cobertura en el grafo de los subgrafos densos con respecto a los resultados obtenidos con las herramientas de Hernández y Navarro. El segundo objetivo principal de este trabajo es el diseño e implementación de una nueva representación compacta para grafos basada en subgrafos densos con superposición. Dos representaciones compactas fueron creadas: una construida a partir de los cliques maximales de un grafo no dirigido, y una segunda para grafos dirigidos y no dirigidos a partir de sus subgrafos densos maximales. En los resultados obtenidos destaca la obtención de una mejor tasa de compresión que las técnicas de referencia actuales con el grafo social no dirigido dblp-2011.
Description: Ingeniero Civil Informatico Universidad de Concepción 2016
URI: http://repositorio.udec.cl/jspui/handle/11594/2081
metadata.dc.identifier.other: 227485
Appears in Collections:Ingeniería Informática y Ciencias de la Computación - Tesis Pregrado

Files in This Item:
File Description SizeFormat 
Tesis_Descubrimiento_Eficiente_de_Subgrafos_Image.Marked.pdf800,85 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.