Multiplicación de matrices booleanas comprimidas usando bicliques.

Abstract

Las matrices booleanas son ampliamente utilizadas en campos como la informática, electrónica, estadística y biología para representar relaciones binarias entre los elementos. El constante crecimiento de datos generado a lo largo de los años, impulsado por la expansión de internet, el auge de las redes sociales y el incremento en el número de páginas web, ha dado lugar a una cantidad masiva de información. Una forma de representarlos, es mediante la utilización de grafos, donde dependiendo de la densidad del grafo se puede representar de distintas formas con el objetivo de reducir el espacio de almacenamiento. La reducción de espacio de representación puede, a su vez, permitir computar operaciones en menor tiempo. A partir de esto, se ve interesante estudiar nuevas representaciones que permitan reducir el espacio y tiempo de cómputo de operaciones de interés. En particular, Hernández y Navarro propusieron un algoritmo para encontrar subgrafos densos compuestos por cliques y bicliques, donde utilizan grafos de hasta 32 bits. Esta memoria de título busca lograr una mejora al extractor de bicliques utilizado por Hernández y Navarro, soportando grafos masivos de 64 bits. Los resultados obtenidos muestran un buen nivel de compresión, llegando a comprimir mas del 50% del grafo en todos los casos, consiguiendo que disminuya la cantidad de bits utilizados por arista en todos los casos. El segundo objetivo es el diseño e implementación de la multiplicación de matrices ralas o dispersas booleanas utilizando sus bicliques. Para esto se definieron dos posibles formas de obtener una matriz resultante, la primera obtenemos la matriz completa y la segunda forma obtenemos la matriz mas una colección de bicliques. Dependiendo del coeficiente de compresión obtenido la multiplicación puede ser una muy buena opción a considerar, o en caso contrario, los bicliques generan una ralentización del algoritmo.