我有一個非常大的連接圖（數百萬個節點）。每個邊都有一個權重 - 識別連接節點的鄰近度。我想在圖表中找到「集羣」（一組非常接近的節點）。例如，如果節點是美國的每個城市，邊緣是城市之間的距離 - 集羣可能是{達拉斯，休斯頓，沃斯堡}和{紐約，布里奇波特，澤西城，特倫頓}。基於網絡X中節點權重的圖的「凝聚」聚類？
羣集不必是相同的大小，並不是所有節點都必須在羣集中。相反，集羣需要有一些平均最小權重，W等於（集羣中權重的總和）/（集羣中邊緣的數量）。
我最舒服的Python和NetworkX似乎是這個
看起來這不會是太難的程序標準的工具，雖然不是特別有效。是否有我描述的算法的名稱？ NetworkX中是否有實現？
我知道一些圖分區算法，他們的目標是儘可能使所有部分的大小大致相同並且邊緣最小，但正如您所描述的那樣，您不需要這樣的算法。無論如何，我認爲你的問題是NP完全像許多其他圖分區問題。 也許有一些算法對你的問題特別有效（我認爲有但我不知道它們），但我認爲你仍然可以找到好的和可接受的解決方案，只需稍微改變一些最初尋找最小邊緣的算法切割相同的元件尺寸。例如參見this。我認爲你可以使用多級k-分區進行一些更改。例如在粗化階段，您可以使用Light Edge Matching。 考慮一種情況，在粗化階段，您已將A和B匹配到一個組中，並將C和D匹配到另一個組中。這兩組之間的邊緣權重是其成員彼此的邊緣的總和，例如， W = Wac + Wad + Wbc + Wbd其中W是邊權重，Wac是A與C之間的邊權重等。我也認爲考慮Wac，Wad，Wbc和Wbd的平均值而不是總和值也是值得一試的。
從我的經驗來看，這個算法非常快，我不確定你能夠在python中找到預編碼庫來進行更改。