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

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）