Por favor, use este identificador para citar o enlazar este ítem: http://repositorio.udec.cl/jspui/handle/11594/2081
Título : Descubrimiento eficiente de subgrafos densos en superposición y su aplicación para la compresión de grafos
Autor : Hernández Rivas, Cecilia; supervisora de grado
Mella Ibáñez, Carlos Felipe
Palabras clave : Gráficos por Computador;Teoría de Grafos;Algoritmos Computacionales;Heurística
Fecha de publicación : 2016
Editorial : Universidad de Concepción.
Resumen : 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.
Descripción : Ingeniero Civil Informatico Universidad de Concepción 2016
URI : http://repositorio.udec.cl/jspui/handle/11594/2081
metadata.dc.identifier.other: 227485
Aparece en las colecciones: Ingeniería Informática y Ciencias de la Computación - Tesis Pregrado

Ficheros en este ítem:
Fichero Descripción Tamaño Formato  
Tesis_Descubrimiento_Eficiente_de_Subgrafos_Image.Marked.pdf800,85 kBAdobe PDFVista previa
Visualizar/Abrir


Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons Creative Commons