Ordenamiento de páginas web con hipergrafos

Abstract

Se investigaron métodos para ordenar páginas web representadas en hipergrafos mediante la implementación del algoritmo de caminata al azar. En particular, se hizo la comparación del desempeño del algoritmo en hipergrafos (PageRank sobre hipergrafos) contra su representación alterna (PageRank sobre grafos) y también contra otros algoritmos sobre grafos. Para cada algoritmo, se obtuvo un ordenamiento de las calificaciones (“rankings”) para cada nodo del grafo y se compararon entre sí y contra resultados obtenidos previamente en la literatura. Se utilizaron métodos de agrupamientos de grafos para construir grupos que, a su vez, permitieron construir los hipergrafos, ya que es importante que la caminata al azar se realice en grupos que estén relacionados entre sí. La implementación de los métodos de agrupamiento representa una aportación importante a la forma de realizar la caminata aleatoria en hipergrafos. Se aplicó el formalismo matemático de matrices para implementar el algoritmo de caminata aleatoria y mediante el método de potencias se obtuvo el vector propio dominante de las matrices involucradas (matriz de transición del hipergrafo). Con este vector, se obtuvieron el ordenamiento de calificaciones y se comparó con los obtenidos de otros algoritmos. Se hicieron comparaciones con el “golden standard” implementado en el proyecto LETOR, basado en información de proyectos para la evaluación de algoritmos de búsqueda en el área de recuperación de la información (proyecto TREC) y con trabajos previos, obteniéndose, en algunos casos, un desempeño superior.