Estimación y Corrección de Distancias en Grafos Masivos

Abstract

Una red es la estructura que modela las interacciones en una gran variedad de situaciones y sistemas tales como las interacciones sociales, la estructura de la Web, rutas terrestres y aereas, etc. Su modelo formal es un grafo y, en muchos casos, principalmente en el mundo digital, las dimensiones son muy grandes, albergando millones de entidades y relaciones. En grafos de estas caracter ́ısticas el desarrollo de algoritmos y procesos escalables y efi- cientes es una de las metas mas difıciles y requeridas, convirtiendose en un topico donde la comunidad cient ́ıfica pone sostenida atenci ́on. Por ejemplo, la complejidad en el calculo exacto de la distancia entre dos nodos ha resultado de interes desde el auge de las re- des sociales y otras que tambi ́en se han tornado masivas. Tecnicas como la estimacion han sido propuestas como alternativas al tiempo y costo computacional inviable. En este sentido, este trabajo propone nuevas t ́ecnicas de selecci ́on de nodos llamados landmarks que se utilizan para estimar la distancia entre dos nodos. Los resultados muestran que las nuevas estrategias consiguen un mejor desempe ̃no que las estrategias baseline. Ademas, se propone una novedosa tecnica de correccion de los valores estimados que logra reducir considerablemente el error, llegando a una disminuci ́on de hasta el 50 % en el mejor de los casos.