Managing massive graphs

Abstract

Con la popularidad de la Web y, mas recientemente, el amplio uso de las redes sociales, la necesidad de procesar y encontrar información en grafos muy grandes impone varios desafíos: Cómo procesar grafos muy grandes e cientemente, dado que probablemente son muy grandes para la memoria disponible, o incluso si la memoria es su ciente, realizar un paso sobre el grafo es todavía caro computacionalmente? Cómo almacenar esos grafos e cientemente, para ser archivados, o para ejecutar algoritmos de grafos? Cómo descubrir información relevante tal como componentes densos, comunidades, u otras estructuras? Se han propuesto tres enfoques para manejar grafos grandes. El primero es usar formatos de grafos comprimidos que permiten consultas de navegación básicas directamentee sobre la estructura comprimida, sin la necesidad de descompresión. Esto permite simular cualquier algoritmo de grafo en memoria principal usando mucho menos espacio que la representación plana. Una segunda línea de investigación se focaliza en usar modelos de stream o semi- stream de datos de manera de procesar secuencialmente, idealmente en un paso sobre el disco, usando una cantidad limitada de memoria principal. La tercera línea es el uso de sistemas distribuidos y paralelos donde la memoria es agregada sobre múltiples unidades de procesamiento para procesar el grafo en paralelo. En esta tesis presentamos varios enfoques para manejar grafos grandes (con arcos sin etiquetas) considerando los tres enfoques. Primero, buscamos por patrones que aparecen en grafos de la Web y redes sociales los que podemos representar en forma compacta, en particular mostramos como generalizar algoritmos para encontrar cliques o bicliques para encontrar sub-estructuras densas que comprimen ambas. Segundo, basado en estos subgrafos densos, proponemos esquemas comprimidos que soportan consultas de vecinos directos y reversos, así como otras consultas mas complejas sobre subgrafos densos. Algunas de las contribuciones combinan técnicas del estado del arte mientras otras incluyen representaciones comprimidas novedosas basadas en estructuras de datos compactas. Encontrar subgrafos densos es una tarea que consume tiempo y espacio, así que proporcionamos algoritmos de streaming and algoritmos de memoria externa para descubrir subgrafos densos, asi como también algoritmos distribuidos para construir las estructuras básicas que usamos para las representaciones comprimidas.