平衡图分割:基于标签交换的割优化

平衡图分割是基本的组合优化问题之一,针对超大规模图高效实现高质量的平衡图分割仍然是一个极富挑战性的问题。提出了一种基于标签交换图分割算法,以最小化规格化割(normalized cut)作为优化目标,利用顶点标签交换迭代更新以达到平衡图分割;针对大规模图,引入采样技术,通过计算局部最优的方式提高算法效率,最后采用邻域抖动(VNS)策略抖动计算多个局部最优解,然后取其中最好的解近似作为全局最优解。实验结果表明,该算法分割得到的子图内密度较好,与最权威图分割算法METIS相比,算法求得的最小割质量更优。

Balanced graph partitioning:Optimizing graph cut based on label swapping