Repositorio Académico Institucional

Los grafos son estructuras de datos cada vez más utilizadas que permiten modelar redes complejas. La dificultad de acceso a grandes conjuntos de datos de estas estructuras ha motivado el desarrollo de métodos para generar grafos con propiedades del mundo real de manera sintética, siendo una de las más importantes una distribución para el grado de los nodos que siga la ley de potencia. Sin embargo, los métodos tradicionales están limitados por la cantidad de memoria de un computador, por lo que en este trabajo se desarrollan e implementan diversos métodos que permitan producir grandes grafos de manera distribuida utilizando Apache Spark. Actualmente se dispone de H4DG y H4UG, que son dos métodos para generar grafos dirigidos y no dirigidos que utilizan el framework Apache Hadoop como motor de cómputo distribuido basando su ejecución en la lectura y escritura de diversos archivos en disco. Para mejorar los tiempos de ejecución se implementan estos métodos en Apache Spark, un motor que mantiene el cómputo distribuido en la memoria de los ordenadores, suponiendo teóricamente una mejora significativa en la rapidez de acceso a los datos. Los resultados muestran que esta implementación no supone una mejora en los tiempos de ejecución. Además, se implementan mejoras a las implementaciones de H4DG y H4UG en Spark que solventan problemas de los métodos originales relacionados a la cantidad de nodos de los grafos generados y la variabilidad en las formas similares de los grafos generados. Con el objetivo de mejorar los tiempos de generación, se desarrollaron nuevos métodos basados en el producto de Kronecker, la generación de números aleatorios con ley de potencia y otros métodos del estado del arte. Los resultados muestran que los mejores tiempos de ejecución para desarrollar un grafo con distribución de ley de potencia se obtienen utilizando la versión con ruido del método de TrillionG.