我有一个非常大的连接图（数百万个节点）。每个边都有一个权重 - 识别连接节点的邻近度。我想在图表中找到“集群”（一组非常接近的节点）。例如，如果节点是美国的每个城市，边缘是城市之间的距离 - 集群可能是{达拉斯，休斯顿，沃斯堡}和{纽约，布里奇波特，泽西城，特伦顿}。基于网络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中找到预编码库来进行更改。