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

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.