Repositorio Dspace

Diseño e implementación de método de compresión de grafos basado en clustering de cliques maximales.

Mostrar el registro sencillo del ítem

dc.contributor.advisor Salinas Ayala, Lilian; supervisora de grado es
dc.contributor.advisor Hernández Rivas, Cecilia; supervisora de grado es
dc.contributor.author Glaría Grego, Felipe Alberto es
dc.date.accessioned 2020-11-05T15:24:09Z
dc.date.available 2020-11-05T15:24:09Z
dc.date.issued 2019
dc.identifier.uri http://repositorio.udec.cl/jspui/handle/11594/984
dc.description Tesis para optar al grado de Magíster en Ciencias de la Computación. es
dc.description.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. es
dc.language.iso spa es
dc.rights Creative Commoms CC BY NC ND 4.0 internacional (Atribución-NoComercial-SinDerivadas 4.0 Internacional)
dc.rights.uri https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es
dc.subject Gráficos por Computador
dc.subject Algoritmos Computacionales
dc.subject Grafos Aleatorios
dc.subject Compresión de Datos (Ciencia de la Computación)
dc.subject Procesamiento Electrónico de Datos
dc.title Diseño e implementación de método de compresión de grafos basado en clustering de cliques maximales. es
dc.type Tesis es
dc.description.facultad Departamento de Ingeniería Informática y Ciencias de la Computación es


Ficheros en el ítem

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem

Creative Commoms CC BY NC ND 4.0 internacional (Atribución-NoComercial-SinDerivadas 4.0 Internacional) Excepto si se señala otra cosa, la licencia del ítem se describe como Creative Commoms CC BY NC ND 4.0 internacional (Atribución-NoComercial-SinDerivadas 4.0 Internacional)

Buscar en DSpace


Búsqueda avanzada

Listar

Mi cuenta