Kernighan-Lin算法的改进对图划分问题的研究

Research on the Improvement of Kernighan-Lin Algorithm for Graph Partitioning

摘要: 随着互联网技术的发展以及大数据时代的来临，复杂网络的社团划分已成为研究的热点，其中大图迭代计算作为其研究的重点，降低划分后子图之间的通信边规模是改善计算性能的关键。Kernighan-Lin算法是图划分问题中最简单、最知名的启发式算法之一，由于传统的Kernighan-Lin算法在图划分问题上很难提高其执行效率，因此，本文基于传统算法的思想与图划分问题研究后，提出了对Kernighan-Lin算法的改进算法。最后，采用空手道俱乐部数据集为实验数据，实验结果证明了改进算法的有效性和可行性。

Abstract: With the development of Internet technology and the advent of the era of big data, the community division of complex networks has become a research hotspot. Among them, the large graph iterative calculation is the focus of its research, and the reduction of the communication edge between sub-graphs is to improve the computing capability. Kernighan-Lin algorithm is one of the simplest and most well-known heuristic algorithms in graph partitioning problem. Because traditional Kernighan-Lin algorithm is difficult to improve its execution efficiency in graph partitioning problem, this paper is based on the idea and graph of traditional algorithm. After the research of partitioning problem, an improved algorithm for Kernighan-Lin algorithm is proposed. Finally, using the karate club dataset as experimental data, the experimental results demonstrate the effectiveness and feasibility of the improved algorithm.