指示されたグラフを介した指向パスの類似性を比較するアルゴリズム

Question

2つの方向パスが入った指示グラフがあります。

アルゴリズムが2つのパス間の類似性を決定したいと考えています。

この郵便受け を使用して levenshtein距離 おおよその類似性を決定します。私もそれを認識しています ハミング距離 同様のメトリックを使用します。

私の質問は次のとおりです。

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

ありがとう

Answer 1

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

より高度な類似性メトリックを検討するのに適した場所は、グラフの隣接マトリックスを考慮し、さまざまなものを見ることです マトリックスの類似性 アルゴリズム。

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

これは、GIS、ロボット工学への機械学習アプリケーション、Webのようなソーシャルネットワーク /人工ネットワークの共同フィルタリングなどの分野に適用可能なトピックであるため、ドメインをユークリッドグラフに制限する際に、この質問に関する多くの積極的な研究があります。記事をチェックしてください Google Scholar.