Descubrimiento eficiente de subgrafos densos en superposición y su aplicación para la compresión de grafos

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.