path - 有向グラフを介して有向パスの類似性を比較するアルゴリズム

Question

2 つの有向パスを持つ有向グラフがあります。

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

この投稿では、レーベンシュタイン距離を使用しておおよその類似性を判断することについて言及しています。また、ハミング距離も同様のメトリックを使用していることに気付きました。

私の質問は：

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

ありがとう

Answer 1

簡単な答えは、これは非常に難しい質問であり、グラフで「類似」が何を意味するかの定義に大きく依存するということです。ほとんどのグラフでは、2 つのばらばらなパスのノードを平面的に再配置して、「平行」に実行しているように見せることができます。

より高度な類似性メトリックを調べるには、グラフの隣接行列を検討し、さまざまな行列類似性アルゴリズムを検討することをお勧めします。

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

ドメインをユークリッド グラフに制限する場合、この問題について多くの活発な研究が行われています。これは、GIS、ロボット工学への機械学習アプリケーション、ソーシャル ネットワークや Web などの人工ネットワークでの協調フィルタリングなどの分野に適用できるトピックであるためです。Google Scholarの記事をご覧ください。