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

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

在信息时代中，随着互联网的使用规模不断扩大，我们需要面对各种各样的网络数据分析和处理， 因此， 大规模和复杂的图数据划分成了讨论中的热点， 另外图信息隐藏技术[1]作为数据保护的措施之一， 也离不开相应的图划分算法。图数据划分问题是经典的NP 问题[2]，针对一个复杂的图数据，很难找出图划分的最优算法。从20 世纪90 年代初期至今，国内外研究者不断对图划分及相关问题进行了深入研究，提出了许多比较好的图划分算法，目前主要有谱方法、几何方法、启发式方法、智能优化算法、多层划分算法、混合方法等[3]。谱方法虽能划分不同类别，但计算量大，H. Simon 和S. Barnard 于1993 年对谱方法进行了改进，具体是使用多层的谱二分(MSB)有效地减少了算法求解特征向量的执行时间。几何方法采用几何最优方式对图信息划分，虽速度快但划分效果不佳，1994 年，S. Ranka 和C. Ou 提出了一种基于多维的空间填充曲线方法。备受关注和广泛使用的智能优化算法近年来一直用来解决图划分问题，例如模拟退火算法[4]、遗传算法[5]等。多层划分法是为了解决规模比较大的图而提出的，在文献[6]和文献[7]中，分别对该算法都进行了不同程度的改进。Kernighan-Lin 算法是一种比较典型的基于启发式规则的求解策略[8]。它的主要思想是先将一个图随机化分成两个已知大小群组，然后交换任意两个顶点使得两个群组之间的割集规模最小，从而得到割集规模最小后的两个群组。该算法通常处理一万个顶点以内的图。M. Fiduccia 和M. Mattheyses 提出的Fiduccia-Mattheyses (FM)算法对Kernighan-Lin 算法进行了改进。FM 算法采用单点移动，并引入了桶列表数据结构，减少了时间复杂度。该类方法不需要知道节点的坐标信息，而是需要根据节点之间的连接信息进行划分。2000 年，S. Dutt 和W. Deng 从顶点的移动次数对FM 算法进行了改进。2002 年，S. Dutt 和W. Deng 又从收益的计算方式进行改进。值得一提的是， Kernighan-Lin 算法是一种典型的基于邻域搜索的路径改进算法， 近年来， 国内外学者以Kernighan-Lin算法为核心操作提出了Chained Kernighan-Lin [9]、Kernighan-Lin Helsgaun [10]和Multilevel Reduction [11] [12]等多种宏启发式算法，不少学者对Kernighan-Lin 算法的初始解构造和边交换策略等方面展开研究， 试图提高算法求解性能。

然而， 目前对基于该启发式 Kernighan-Lin 算法并没有系统的分析和评价， 本文结合算法分析和实验验证，证明了改进LK 算法在运算时间和运算效果方面都有很大的进步，同时根据分析实验结果，选择出最优方案。