嵌入格拉夫歐氏空間

我有一個總的無向圖，其中節點表示於上的平面上的點的點，和邊緣是點之間近似的歐幾里德距離。我想將這個圖嵌入到二維空間中。也就是說，我想每個頂點轉換爲（X，Y）的位置元組，這樣對於任何兩個兩個頂點V和W的邊緣（V，W）的重量接近DIST（V，W）來。例如，如果我有包含節點A，B，C和D以及具有權重（A，B）的邊的圖：20; （A，C）：22; （A，D）：26; （B，C）：30; （B，D）：20，（C，D）：19，那麼你可以分配點A：（0,0）; B：（10，0）; C：（0,10）; D：（10，10）。顯然這是不完美的，但它是一個合理的近似值。嵌入格拉夫歐氏空間

我不在乎獲得最好的解決方案，我只是想在合理的時間內找到合理的解決方案。

（如果您想對這個問題的動機。我有一個物理系統，我有所有的點對距離的噪聲測量。測量距離是嘈雜的，但往往是兩個真正的因素中值我已經做了所有這些測量，現在有一個包含幾千個節點和幾百萬個邊的圖，並且希望將這些點放在一個平面上。）

來源

2013-01-14 John Dillerd

您可以根據需要修改force-based圖形繪製算法。

該算法試圖通過治療V各頂點作爲笛卡爾點和在E爲線性彈簧每個邊緣找到無向圖G(V,E)佈置好。此外，成對的排斥力（即庫侖定律）的頂點之間計算全局 - 這防止在笛卡爾空間中處於G(V,E)不相鄰的頂點的聚類。

在你的情況下，你可以設置彈簧的平衡長度等於你的邊緣權重 - 這應該給出一個佈局，其歐幾里得頂點距離接近你的邊緣權重。

該算法基於每個頂點的力的總和以僞時間步進方式更新初始分佈（可能是隨機的）。該算法在達到近似穩定狀態時終止。一個簡化的僞代碼：

while(not converged) 
    for i = vertices in V 
     F(i) = sum of spring + repulsive forces on ith vertex 
    endfor 
    Update vertex positions based on force vector F 
    if (vertex positions not changing much) 
     converged = true 
    endif 
endwhile

有一些優化，可以應用於降低算法的複雜性。例如，可以使用空間索引（例如四叉樹）來有效計算「接近」頂點之間的近似排斥力，而不是慢速全局計算。也可以使用多級圖形聚集技術來提高收斂性和最優性。

最後，請注意，有幾個優秀的圖形庫用於實現該算法的優化版本 - 例如，您可能想要查看Graphviz。

來源

2013-01-15 00:50:06

對於初學者，我想我會去一種啓發式搜索方法。

你真的想找到一個設定點P1，P2，...，P_N該功能最大程度地減少：

f(X) = Sum (|dist(p_i,p_j) - weight(n_i,n_j)|) [for each i,j ]

的問題可以通過一些算法，包括Hill Climbing和Genetic Algorithms可以試探性地解決。

我個人很喜歡爬山和方法如下：

best <- [(0,0),(0,0),...,(0,0)] 
while there is still time: 
    S <- random initialized vector of points 
    flag <- true 
    while (flag): 
     flag <- false 
     candidates <- next(S) (*) 
     S <- X in candidates such that f(X) <= f(Y) for each X in candidates (**) 
     if f(S) was improved: 
      flag <- true 
    if f(S) <= f(best): 
     best <- S 
return best

(*)下一個（）產生的候選人名單。它可以利用的信息有關的功能梯度（和基本上衰變成類似於gradient descent的東西），例如，或採樣幾個隨機「方向」，並把它們作爲候選（全部在多維向量，其中每個點是一個維度）。
(**)在這裏，你基本上選擇了「最佳」候選人，並將其存儲在S，所以你會用它繼續下一次迭代。

請注意，該算法是any-time，所以預計您得到更多的時間，你必須給它。這很可能改變結局的結果，並通過分的考生隨機選擇 - 此行爲是由起點的隨機初始化實現。

來源

2013-01-14 22:46:23 amit

嵌入格拉夫歐氏空間

回答

相關問題