Kernighan-Lin算法的改进对图划分问题的研究
Research on the Improvement of Kernighan-Lin Algorithm for Graph Partitioning

DOI: 10.12677/CSA.2019.95095, PP. 849-854

Keywords: Kernighan-Lin算法，图划分，社交网络
Kernighan-Lin Algorithm, Graph Partitioning, Social Network

Full-Text   Cite this paper   Add to My Lib

Abstract:

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

References

[1]	张军, 熊枫, 张丹. 图像隐写分析技术综述[J]. 计算机工程, 2013, 39(4): 165-168.
[2]	李琪, 钟将, 李雪. 基于启发策略的动态平衡图划分算法[J]. 计算机研究与发展, 2017(12): 2834-2840.
[3]	郑丽丽. 带权图的k划分算法研究[D]: [硕士学位论文]. 天津: 天津工业大学, 2013.
[4]	许金凤, 董一鸿, 王诗懿, 等. LGP-SA: 分布式环境下基于模拟退火的大规模图划分算法[J]. 电信科学, 2016, 32(2): 83-91.
[5]	姜火文, 曾国荪, 胡克坤. 一种遗传算法实现的图聚类匿名隐私保护方法[J]. 计算机研究与发展, 2016, 53(10): 2354-2364.
[6]	Saab, Y.G. (2004) An Effective Multilevel Algorithm for Bisecting Graphs and Hypergraphs. IEEE Transactions on Computers, 53, 641-652. https://doi.org/10.1109/TC.2004.3
[7]	Benlic, U. and Hao, J.K. (2011) A Mul-tilevel Memetic Approach for Improving Graph k-Partitions. IEEE Transactions on Evolutionary Computation, 15, 624-642. https://doi.org/10.1109/TEVC.2011.2136346
[8]	曾华, 崔文, 付连宁, 等. Lin-Kernighan算法初始解的启发式构造策略[J]. 山东大学学报(工学版), 2012, 42(2): 30-35.
[9]	Pellegrini, F. and Roman, J. (1996) Scotch: A Software Package for Static Mapping by Dual Recursive Bi-Partitioning of Process and Architecture Graphs. In: Proceedings of HPCN Europe, Springer, Berlin, 493-498. https://doi.org/10.1007/3-540-61142-8_588
[10]	Simon, H.D. (1991) Partitioning of Unstructured Problems for Parallel Pro-cessing. Computing Systems in Engineering, 2, 135-148. https://doi.org/10.1016/0956-0521(91)90014-V
[11]	Karypis, G. and Kumar, V. (1998) Multilevel K-Way Partitioning Scheme for Irregular Graphs. Journal of Parallel and Distributed Computing, 48, 96-129. https://doi.org/10.1006/jpdc.1997.1404
[12]	Grady, L. and Schwartz, E.L. (2006) Isoperimetric Graph Partitioning for Image Segmentation. IEEE Transactions on Pattern Analysis & Machine Intelligence, 28, 469-475. https://doi.org/10.1109/TPAMI.2006.57
[13]	Kernighan, B.W. and Lin, S.A. (1970) Efficient Heuristic Procedure for Partitioning Graphs. Bell System Technical Journal, 49, 291-307. https://doi.org/10.1002/j.1538-7305.1970.tb01770.x
[14]	李孔文, 顾庆, 张尧, 等. 一种基于聚集系数的局部社团划分算法[J]. 计算机科学, 2010, 37(7): 46-49.
[15]	杨艳萍. 基于双向加权图的社交网络用户可信度算法研究[J]. 信息网络安全, 2017, 17(7): 40-44.

Full-Text