將圖劃分成k個相似的子圖

Question

我有一個連接的圖形，邊上有權重。邊之間的重量越少，相鄰頂點越靠近。我想將圖分成k個較小的子圖，使得所有子圖中的節點非常相似。

換句話說，我需要對圖進行聚類。有人可以建議適合圖的聚類算法，並且具有較少的時間複雜性（小於O（n^2））嗎？

Answer 1

聚類是一個難以解決的難題，一般只能通過暴力破解extlty。所以在高效算法的情況下，你必須依賴一些啓發式的方法。如果你可以將你的問題解決爲頂點集羣任務，你可以嘗試類似k-means，但是在較大的數據集上它可能會很慢。

對於具體的圖形，我會建議在你的問題上使用MCL算法。 MCL在很多情況下似乎很有效率。它使用隨機流量模擬來檢測加權/未加權圖中的羣集。基本思想是流聚集在一個集羣內，而集羣之間的鏈接往往更少飽和。