algorithm - 如何将一个连通的带权图划分为N个半等分子图

Question

我有一个包含数百个主要相互连接的节点的图表。我可以对整个图进行处理，但这确实需要很多时间，所以我想将它分成大小大致相似的较小子图。

换句话说。我有一组航拍图像，我对所有图像进行成对图像匹配。结果，我得到了每对的一组匹配项(第一张图像的像素与第二张图像的像素匹配)。匹配数被视为该(无向)边的权重。然后这些边形成上面提到的图。

我不太熟悉图论(因为它是一个非常广泛的主题)。 这项工作的最佳算法是什么？

谢谢。

编辑:这个问题有一个完美的类比，我认为更容易理解。想象一下你有一群人和他们的联系/友谊，比如我的社交网络。每个友谊都有一个数值/权重，代表他们是多么好 friend 。因此，在一大群人中，我想得到 k 个最相互关联的子组。

Answer 1

不幸的是，您所描述的问题几乎肯定是 NP-hard 问题。从图形的角度来看，您有一个图形，其中每条边都有一个权重。您正在尝试将图形拆分为相对相等的部分，同时切割边切割的总成本最低。这个问题称为最大 k-cut 问题并且是 NP-hard。如果你引入你也想尝试使碎片大小大致均匀的约束，你就有了平衡的 k-cut 问题，这也是 NP-hard。

好消息是这些问题有很好的近似算法，所以如果您正在寻找“足够好”的解决方案，那么您可能可以在某个地方找到实现它们的库。还有其他技术，例如谱聚类，它们在实践中运行良好并且速度非常快，但不能保证它们的性能。