圖分區

Question

考慮我有一個包含10,000個節點的圖。現在我想在圖中尋找一定數量的節點。我想用圖分區技術實現這一點，以便在某個分區中找到合理數量的所需節點時，我可以停止搜索。那麼如何做分區？什麼是適合的算法或工具使用？

我的圖形是矩陣格式。其中mat [i] [j]給出兩個節點'i'和'j'之間的邊權值。

找到分區後，我想要列出該分區中存在的所有節點。

Answer 1

有太多的algorthim圖分區。這些算法的最大目標是減少分區間的縮減。但如果你有另一個目標，你必須轉換或模型來削減目標。 你可以使用「圖形Voronoi圖分區程序」進行分區 進行分區另一個軟件是METIS（http://glaros.dtc.umn.edu/gkhome/metis/metis/overview）和Kaffpa（http://algo2.iti.kit.edu/documents/kahip/）

Answer 2

如果我理解正確的話，你要搜索一組節點匹配一些客觀的說 - 在分區級別上並行執行此搜索。在這種情況下，一個好的分區策略是平衡跨分區的「匹配節點」的數量。

原因是，如果這些匹配節點是平衡的，那麼所有在分區上獨立工作的並行工作者都有相同的機會來查找/匹配頂點。

根據我的經驗，即使edge-cut大小不是最優時，在使用隨機分配頂點到分區時，您可以針對不同目標達到非常穩固的平衡。

但是，如果不知道更多關於您的目標的問題，很難回答您的問題，所以也許您可以更新您的問題並提供更多詳細信息。