Abstract: Balanced graph partitioning is one of the fundamental combinatorial optimization problems. It is still a challenge to effectively achieve a high-quality balanced graph partitioning for super-large graphs. This paper proposes a graph partitioning algorithm based on label swapping. This algorithm uses normalized cut as the optimization target and iteratively updates the balanced graph by using label swapping. It introduces the sampling to deal with super-large graphs and increases the algorithm’s efficiency by calculating the local optimal solution. In order to escape from the local optimum, the paper introduces VNS strategy in this algorithm to get the global solution approximatively. The experiments show that the partition’s intracluster density is very good and this algorithm outperforms METIS in term of minimum cut.

Key words: balanced graph partitioning, label swapping, sampling, normalized cut, Variable Neighborhood Search（VNS）

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

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