Una Breve Revisión de los Algoritmos Modernos de Camino Más Corto y Técnicas de Optimización de Grafos

Tabla de Enlaces

Resumen y 1. Introducción

1.1 Nuestra Contribución

1.2 Configuración

1.3 El algoritmo

1. Trabajo Relacionado

2. Algoritmo

   3.1 La Fase de Descomposición Estructural

   3.2 La Fase de Enrutamiento

   3.3 Variantes de WormHole

3. Análisis Teórico

   4.1 Preliminares

   4.2 Sublinealidad del Anillo Interior

   4.3 Error de Aproximación

   4.4 Complejidad de Consulta

4. Resultados Experimentales

   5.1 WormHole𝐸, WormHole𝐻 y BiBFS

   5.2 Comparación con métodos basados en índices

   5.3 WormHole como primitiva: WormHole𝑀

Referencias

2 TRABAJO RELACIONADO

Existe un vasto cuerpo de investigación sobre caminos más cortos y distancias, que abarca muchas décadas e incluye cientos de algoritmos y heurísticas diseñadas para una variedad de entornos. Aquí, solo revisamos varios trabajos que están más estrechamente relacionados con el nuestro. Para una visión más completa, consulte los estudios [42, 55] y las referencias en ellos.

\ Enfoques basados en índices. Como se mencionó anteriormente, un conjunto ubicuo de algoritmos se basa en enfoques de puntos de referencia/esquemas [37, 61, 62], siendo Pruned Landmark Labeling (PLL) [5] quizás el más influyente. Estos algoritmos siguen un procedimiento de dos pasos: el primer paso genera un ordenamiento de los vértices según su importancia (basado en diferentes heurísticas), y el segundo paso genera etiquetado a partir de árboles de caminos más cortos podados construidos según el ordenamiento. Luego, la distancia más corta entre un par arbitrario de vértices 𝑠 y t puede responderse rápidamente basándose en sus etiquetas. Sin embargo, incluso con la poda, PLL requiere un tiempo de configuración significativo. Por lo tanto, ha habido muchos intentos de paralelizarlo [29, 37, 39].

\ Enfoques basados en incrustaciones. Algunos enfoques recientes aprovechan las incrustaciones de grafos para estimar los caminos más cortos. Como en el aprendizaje de representación, buscan encontrar representaciones eficientes de distancias entre pares de nodos [64, 65]. Una línea moderna de trabajo también considera incrustaciones hiperbólicas de los grafos, que están estrechamente relacionadas con las descomposiciones de árboles, para responder consultas de caminos más cortos [11, 33]. Trabajos recientes también han examinado la aceleración de este proceso mediante el uso de métodos de aprendizaje profundo basados en GPU [35, 47, 48]. Query-by-Sketch [57] considera la tarea, relacionada pero incomparable, de responder consultas de grafos de caminos más cortos, donde el objetivo es calcular un subgrafo que contenga exactamente todos los caminos más cortos entre un par dado de vértices. Proponen un esquema de etiquetado alternativo para mejorar la escalabilidad y los tiempos de consulta.

\

\ Enfoques basados en núcleo-periferia. Varios otros trabajos explotan la estructura de núcleo-periferia de las redes [6, 13, 38]. Brady y Cohen [13] utilizan esquemas de enrutamiento compactos para diseñar un algoritmo con pequeño error aditivo basado en la semejanza de la periferia con un bosque. Akiba, Sommer y Kawarabayashi [6] aprovechan la propiedad de bajo ancho de árbol fuera del núcleo, y en [38], los autores diseñan un índice basado en Core-Tree para mejorar los tiempos de preprocesamiento en grafos masivos. Notamos que en todos estos resultados, la sobrecarga de memoria es superlineal.

\ Grafos de peor caso. En el lado teórico, ha habido muchos resultados sobre caminos más cortos exactos y aproximados en grafos de peor caso, por ejemplo, [19, 20, 22, 49, 51, 67], con mejoras tan recientes como el año pasado. La mayoría de estos se centran en el caso de aproximación 2, investigado por primera vez en el trabajo seminal de Aingworth et al. [4]. Dirigimos a los lectores a la encuesta de Zwick [66] sobre algoritmos de caminos más cortos exactos y aproximados, y la encuesta de Sen [53] sobre oráculos de distancia para grafos generales con énfasis en reducir el costo de preprocesamiento. Notablemente, debido a que hacemos una suposición estructural más allá del peor caso que es común en redes grandes, a saber, una estructura de núcleo-periferia, tanto nuestros resultados como el algoritmo difieren sustancialmente de la literatura teórica del peor caso.

\

:::info Autores:

(1) Talya Eden, Universidad Bar-Ilan (talyaa01@gmail.com);

(2) Omri Ben-Eliezer, MIT (omrib@mit.edu);

(3) C. Seshadhri, UC Santa Cruz (sesh@ucsc.edu).

:::

:::info Este artículo está disponible en arxiv bajo licencia CC BY 4.0.

:::

\