有向グラフによる有向パスの類似性を比較するアルゴリズム

Question

私はそこに2つの有向パスを持つ有向グラフを持っています。

2つのパス間の類似性を判断するアルゴリズムが必要です。

This postは、近似類似性を決定するためにLevenshtein distanceを使用して言及しています。私はまた、Hamming distanceが同様の指標を使用していることを認識しています。

私の質問は：

どのように2つのパスが互いに平行を実行ケースを処理します。つまり、2つのパスに似たノードがない場合でも、パスが互いに非常に近い同じ方向に移動するため、「類似」とみなされます。

おかげ

Answer 1

簡単な答えは、これは非常に難しい問題である、と「類似の」はグラフに何を意味するのか、あなたの定義に多くを依存しているということです。ほとんどのグラフでは、2つの独立したパスのノードを平面的に並べ替えることで、 'parallel'を実行するように見えます。

より高度な類似性メトリックを調べ始めるには、グラフの隣接行列を考慮して、さまざまなmatrix similarityアルゴリズムを見てください。

編集：ユークリッドグラフに質問を制限

ありユークリッドグラフにドメインを制限する場合、これはロボット工学のGIS、機械学習アプリケーションなどの分野に適用可能なトピックであるとして、この問題について活発な研究の多くは、だ、とソーシャルネットワーク/ウェブのような人工ネットワーク上のコラボレーションフィルタリング。 google scholarの記事をご覧ください。