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

• 作者: 张华健
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 平衡图分割 标签交换 采样 规格化割 邻域抖动
• 年，卷（期）: 2016,（13）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 167-172
• 页数: 6页
• 分类号: TP393
• 字数: 5957字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.1511-0357

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张华健	南京邮电大学物联网学院	7	21	3.0	4.0