Tesis "Algoritmos paralelos para la propagación de etiquetas en redes complejas"
Sustentante: Eder Said Camacho Camacho.
Directores: Dr. Arturo Díaz Pérez, investigador Cinvestav Unidad Guadalajara y Dr. Miguel Morales Sandoval, investigador Cinvestav Tamaulipas.
Sinodales: Dr. José Luis González Compeán, Cinvestav Unidad Tamaulipas;Dr. Iván López Arévalo, Cinvestav Unidad Tamaulipas.
Resumen:
Debido a las propiedades estructurales que se presentan en las redes complejas como su estructura en comunidades, distribución de grado en ley de potencia, el fenómeno de mundo pequeño y componentes gigantes, el desarrollo de algoritmos paralelos eficientes para su análisis y procesamiento representa un desafío importante. Dada la baja densidad que tienen los grafos que representan a redes complejas y la gran cantidad de vértices, no es conveniente utilizar representaciones estructuradas para su procesamiento. Sin embargo, las representaciones con listas de adyacencia no permiten aprovechar adecuadamente el procesamiento paralelo debido a la dificultad para tener un balance de carga adecuado, Por otro lado, la diversidad en los grados de los vértices de las redes complejas hace que el procesamiento por listas de adyacencia tenga un pobre desempeño en el uso de la memoria caché. En este trabajo se aborda el problema de propagación de etiquetas utilizando como medio de propagación una red compleja. Este problema representa el núcleo básico de procesamiento para el análisis de redes complejas. El etiquetado de los vértices de la red puede ser de utilidad para realizar segmentación, así como determinar la influencia de los vértices con respecto a otros. Este trabajo se enfoca particularmente en algoritmos de detección de comunidades y difusión de información paralelos, utilizando arquitecturas multicore y GPU. La evaluación de la eficiencia de los algoritmos se realiza con respecto al tiempo de ejecución. Utilizando la aceleración como métrica de comparación entre las diferentes arquitecturas. Obteniendo aceleraciones para redes irregulares de entre 4x y 7x aproximadamente en algoritmos multicore a 10 núcleos y entre 20x y 50x en algoritmos GPU con 448 núcleos CUDA. En este trabajo se muestra también un caso de estudio para darle significado a las etiquetas que se usan en el análisis de redes complejas, viéndolas como políticas de control de acceso CP-ABE en una red de documentos. Se analiza el tratamiento que se podría darle a las etiquetas en el proceso de difusión de etiquetas.