Please use this identifier to cite or link to this item: http://repositorio.udec.cl/jspui/handle/11594/984
Title: Diseño e implementación de método de compresión de grafos basado en clustering de cliques maximales.
Authors: Salinas Ayala, Lilian; supervisora de grado
Hernández Rivas, Cecilia; supervisora de grado
Glaría Grego, Felipe Alberto
Keywords: Gráficos por Computador;Algoritmos Computacionales;Grafos Aleatorios;Compresión de Datos (Ciencia de la Computación);Procesamiento Electrónico de Datos
Issue Date: 2019
Abstract: La compresión y manejo eficiente de grandes grafos se vuelve cada día más fundamental en distintos ámbitos, desde la representación de la Web y las redes sociales, hasta representar componentes biológicos. Su crecimiento ha tenido un aumento constante, y con esto se eleva la exigencia en recursos para procesar consultas sobre ellos. Una solución a este problema es buscar una opción de representar estos grafos de maneras alternativas que permitan responder dichas consultas en el menor tiempo posible. En este trabajo se desarrolla un método de compresión para grafos no dirigidos poco densos, que aprovecha la superposición de cliques maximales en la generación de una estructura compacta que permite manejar de manera eficiente dichos grafos. Si bien el problema de obtener los cliques maximales de un grafo es muy complejo (NP-completo), existen algoritmos para grafos poco densos que logran generar el listado en poco tiempo. Además, es un costo que se debe pagar una sola vez, luego de generar la estructura compacta se puede obtener nuevamente el listado de cliques directo de ella. Finalmente se prueba el rendimiento de esta estructura propuesta con diferentes grafos, estudiando qué características deben tener para aprovechar sus ventajas, y se compara con otros algoritmos relevantes del estado del arte, comprobando su rendimiento tanto en la compresión de grafos como en resolver las consultas sobre ella. Se identifica que para grafos altamente clusterizados la compresión logra su máxima eficiencia, ocupando menos de un bit por arco. En cuanto a respuesta de consultas, se muestra que para ciertos casos se logran tiempos cercanos al estado del arte. Además, se desarrollan algoritmos que permiten recuperar el listado de cliques maximales, y consultar la vecindad de dos vértices, sin necesidad de descomprimir. Por último, se proponen líneas de investigación para acelerar las consultas.
Description: Tesis para optar al grado de Magíster en Ciencias de la Computación.
URI: http://repositorio.udec.cl/jspui/handle/11594/984
Appears in Collections:Ingeniería Informática y Ciencias de la Computación - Tesis Magister

Files in This Item:
File Description SizeFormat 
Tesis diseno e implementacion.pdf2,31 MBAdobe PDFThumbnail
View/Open


This item is licensed under a Creative Commons License Creative Commons