Algoritmo para comparar la similitud de las rutas dirigidas a través del gráfico dirigido

Question

Tengo un gráfico dirigido con dos rutas dirigidas.

Quiero que un algoritmo determine la similitud entre las dos rutas.

Esta publicación menciones usando el Distancia de levenshtein para determinar una similitud aproximada. También me doy cuenta de que el Distancia de hamming Utiliza una métrica similar.

Mi pregunta es:

¿Cómo manejas el caso donde dos rutas corren paralelas entre sí? Es decir, si las dos rutas no tienen nodos similares, pero se considerarían "similares" porque sus caminos viajan en la misma dirección muy cercana entre sí.

Gracias

Answer 1

La respuesta simple es que esta es una pregunta muy difícil, y se basa mucho en su definición de lo que significa 'similar' en un gráfico. En la mayoría de los gráficos, podría reorganizar los nodos de dos caminos disjuntos de manera plana para parecer correr 'paralelo'.

Un buen lugar para comenzar a ver métricos de similitud más avanzados sería considerar la matriz de adyacencia del gráfico y mirar varias similitud de matriz algoritmos.

Editar: restringir la pregunta a los gráficos euclidianos

Hay muchas investigaciones activas sobre esta pregunta al restringir el dominio a los gráficos euclidianos, ya que este es un tema aplicable para áreas como SIG, aplicaciones de aprendizaje automático a robótica y filtrado colaborativo en redes sociales / redes artificiales como la web. Mira los artículos en Google Académico.