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

摘要：

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

关键词：平衡图分割、标签交换、采样、规格化割、邻域抖动

所属期刊栏目：52

分类号：TP393(计算技术、计算机技术)

资助基金：国家科技部科技支撑计划SQ2013GX07E00985

在线出版日期：2016-07-19（万方平台首次上网日期，不代表论文的发表时间）

页数：共6页

页码：167-172