Algoritmo per confrontare somiglianza dei percorsi diretti attraverso grafo orientato

Question

Ho un grafo orientato con due percorsi diretti in esso.

Voglio un algoritmo per determinare la somiglianza tra i due percorsi.

Questo post cita utilizzando il Levenshtein distanza per determinare una somiglianza approssimativa. Mi rendo anche conto che il distanza di Hamming usa una metrica simile.

La mia domanda è:

Come si fa a gestire il caso in cui due percorsi corrono parallele l'una all'altra. Cioè se i due percorsi non hanno nodi simili, ma sarebbero considerati 'simile' perché i loro percorsi viaggiano nella stessa direzione molto vicini tra loro.

Grazie

Answer 1

La semplice risposta è che questa è una domanda molto difficile, e si basa molto sulla vostra definizione di ciò che significa 'simili' in un grafico. Nella maggior parte dei grafici è possibile riorganizzare i nodi di due percorsi disgiunti in modo planare in modo da apparire a correre 'in parallelo'.

Un buon posto per cominciare a guardare a metriche di similarità più avanzate sarebbe quella di considerare matrice di adiacenza del grafico, e lo sguardo a vari matrice di similarità algoritmi.

Modifica: Limitare la domanda a grafici euclidee

C'è un sacco di ricerca attiva su questa questione quando limitare il dominio a grafici euclidee, in quanto questo è un argomento applicabile a zone come GIS, applicazioni di apprendimento automatico per la robotica, e il filtraggio collaborativo sulle reti / network artificiali sociali come il web. Scopri gli articoli su Google Scholar .