寻找最小交叉边的图分区

Question

最近我一直在研究一些算法，但遇到了以下问题：

给定一个无向、没有权重并且可能不连通的图 G(V, E)，找到 G 的 k 个分区，每个分区有相同数量的节点（假设总节点数是 k 的倍数），并且 G 中连接不同分区中的节点的边数最少。

我不需要一个多项式时间算法来解决这个问题（因为它可能是 NP-Hard），而是需要一个能够在不到24小时内解决150个节点和1200条边的算法。虽然任何好的近似算法都会受到欢迎，但我更喜欢精确解决方案。

尽管我尽可能地简化了问题，但对于有权重的有向图的一般解也很好。

谢谢您的帮助！

更新：我刚刚做了更多的研究，并意识到这可以被重新解释为一个修改后的连通性问题。也许在这样的思路下有解决方案？

- DreamConspiracy

Answer 1

这确实是一个NP难问题。如果您擅长凸优化或者能够学习，我的直觉是将这个问题形式化为一个精确覆盖 整数规划，有许多变量（每个子集有|V|/k个顶点），然后通过生成列与整数规划求解器实际解决该程序，以找到具有许多内部边缘的分区。子问题的制定将如下所示

maximize sum_{vertices v} w_v x_v + sum_{edges uv} y_{uv}
subject to
sum_{vertices v} x_v = |V|/k
y_{uv} <= x_u for all edges uv
y_{uv} <= x_v for all edges uv
x_v in {0, 1} for all vertices v
y_{uv} in {0, 1} for all edges uv

其中w_v是由主问题的对偶解决定的权重，直观地理解为特定顶点需要覆盖的紧急程度。

- David Eisenstat

Answer 2

一种方法是使用聚类算法。您不会得到最优解，但可以获得快速的半优化解决方案。

您可以以各种方式处理此问题。例如，您可以使用双聚类。或者您可以进行主成分分析，选择几个组件并运行修改后的k-means算法。

- ElKamina