算法通過向圖比較引導路徑的相似性

Question

我有帶有兩個向路徑的有向圖。

我想要一個算法來確定兩個路徑之間的相似性。

This post提到使用Levenshtein distance來確定近似相似。我也意識到Hamming distance使用了一個類似的指標。

我的問題是：

你是如何處理在兩個路徑平行於對方的情況。也就是說，如果這兩條路徑沒有類似的節點，但它們會被認爲是「相似的」，因爲它們的路徑沿着相互接近的相同方向傳播。

感謝

Answer 1

簡單的回答是，這是一個很難的問題，並依靠很多對你的什麼「相似」是指在圖形定義。在大多數圖表中，您可以平面方式重新排列兩條不相交路徑的節點，以便看似「平行」運行。

開始尋找更高級的相似性度量標準的好地方是考慮圖的鄰接矩陣，並且看看各種各樣的matrix similarity算法。

編輯：限制的問題，以歐氏圖表

限制域歐幾里德圖形時，因爲這是像GIS，機器學習應用到機器人領域適用的話題有大量活躍的研究這個問題，在社交網絡/網絡等人工網絡上進行協作過濾。看看google scholar上的文章。