查找具有最小边交叉分区的图分区
Finding Graph Partitions with Minimum Edges Crossing Partitions
我最近一直在研究一些算法，但遇到了以下问题：
给定一个无向无权可能断开图G(V, E)找到G的k个分区使得每个分区具有相同数量的顶点（假设顶点总数是k的倍数）并且有G 中连接不同分区中的顶点的最小边数。
我不是在寻找这个问题的多项式时间算法（因为它可能是 NP-Hard 无论如何），而是在 24 小时内找到 150 个顶点和 1200 条边的解决方案的算法。虽然任何好的近似算法也将不胜感激，但我更喜欢精确的解决方案。
我让问题尽可能简单，但是有向加权图的通用解决方案也很好。
感谢所有帮助！
更新：我刚刚做了更多研究，意识到这可以重新解释为修改后的连接问题。也许按照这种思路有解决方案？
这确实是一个 NP-hard 问题。如果您熟悉凸优化或可以学习，我的直觉是将此问题表述为 exact cover integer program with many variables (one per subset of |V|/k vertices) and then actually solve that program by generating columns 并使用整数程序求解器来查找具有许多内部边的分区。子问题的公式看起来像
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 是由主问题的对偶解确定的权重，直观理解为特定顶点需要覆盖的紧急程度。
一种方法是使用聚类算法。您不会获得最佳解决方案，而是快速 semi-optimal 解决方案。
您可以通过多种方式解决这个问题。例如，您可以使用双聚类。或者您可以进行主成分分析，选择一些成分和 运行 修改后的 k-means 算法。
我最近一直在研究一些算法，但遇到了以下问题：
给定一个无向无权可能断开图G(V, E)找到G的k个分区使得每个分区具有相同数量的顶点（假设顶点总数是k的倍数）并且有G 中连接不同分区中的顶点的最小边数。
我不是在寻找这个问题的多项式时间算法（因为它可能是 NP-Hard 无论如何），而是在 24 小时内找到 150 个顶点和 1200 条边的解决方案的算法。虽然任何好的近似算法也将不胜感激，但我更喜欢精确的解决方案。
我让问题尽可能简单，但是有向加权图的通用解决方案也很好。
感谢所有帮助！
更新：我刚刚做了更多研究，意识到这可以重新解释为修改后的连接问题。也许按照这种思路有解决方案？
这确实是一个 NP-hard 问题。如果您熟悉凸优化或可以学习，我的直觉是将此问题表述为 exact cover integer program with many variables (one per subset of |V|/k vertices) and then actually solve that program by generating columns 并使用整数程序求解器来查找具有许多内部边的分区。子问题的公式看起来像
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 是由主问题的对偶解确定的权重，直观理解为特定顶点需要覆盖的紧急程度。
一种方法是使用聚类算法。您不会获得最佳解决方案，而是快速 semi-optimal 解决方案。
您可以通过多种方式解决这个问题。例如，您可以使用双聚类。或者您可以进行主成分分析，选择一些成分和 运行 修改后的 k-means 算法。