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

• 作者: 宋晨明 赵娜 郁湧 阚世林 顾捷 骆永军
• 来源期刊: 计算机科学与应用
• 学科: 数学
• 关键词: Kernighan-Lin算法 图划分 社交网络
• 年，卷（期）: 2019,（5）
• 页码范围: 849-854
• 页数: 6页
• 分类号: O1

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵娜	云南大学软件学院	15	71	6.0	8.0
2	郁湧	云南大学软件学院	26	169	7.0	12.0
3	阚世林	云南大学软件学院	3	2	1.0	1.0
4	骆永军	云南大学软件学院	3	2	1.0	1.0
5	顾捷	云南大学软件学院	3	2	1.0	1.0
6	宋晨明	云南大学软件学院	1	0	0.0	0.0