如何將連通的加權圖劃分爲N個半等分子圖

Question

我有一個包含數百個主要相互連接的節點的圖。我可以在整個圖表上進行處理，但它確實需要很長時間，所以我想將它分成幾乎相似大小的較小子圖。

換句話說。我收集了一些航拍圖像，我在它們之間做了兩兩匹配的圖像匹配。因此，我爲每一對（第一張圖像中的像素與第二張圖像上的像素匹配）獲得一組匹配。匹配的數量被認爲是這個（無向）邊的權重。這些邊緣然後形成上面提到的圖形。

我不太熟悉圖論（因爲它是一個非常廣泛的話題）。 這項工作的最佳算法是什麼？

謝謝。

編輯： 這個問題有一個我認爲比較容易理解的完美比喻。想象一下，你有一組人和他們的聯繫/友誼，就像我的社交網絡一樣。每一個友誼都有一個數值/重量來表示他們有多好的朋友。因此，在一大羣人中，我想獲得最相關的子組。

Answer 1

不幸的是，你所描述的問題幾乎肯定是NP難題。從圖形的角度來看，你有一個圖形，每條邊都有一個重量。您試圖將圖分成相對相等的部分，同時削減邊緣切割的最低總成本。這個問題被稱爲最大k切問題，並且是NP難題。如果你引入約束條件，你也想盡量讓碎片尺寸大小一致，那麼你就有了平衡k-切割問題，這也是NP-難題。

好消息是，針對這些問題有很好的近似算法，所以如果您正在尋找「足夠好」的解決方案，那麼您可能會找到一個實現它們的庫。還有其他一些技術，如頻譜聚類，在實踐中運行良好，速度非常快，但對於它們的效果沒有任何保證。