Kernighan-Lin算法

2024-05-30 03:38

文章标签 算法 lin kernighan

本文主要是介绍Kernighan-Lin算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

注意：之前对于公式用LATEX编写，复制的图片，不知怎么就显示不出，凡是框框的地方，用文字表示了公式。

Kernighan-Lin算法是一种启发式算法，基于贪婪原理将网络划分为两个大小已知的社团。

所要解决的问题描述：给定一个无向带权图G=(V,E，C)，其中V为一含有2n个节点的集合，E为边集合，C为2n*2n且对称的权重矩阵（Cij表示节点i和节点j直接边的权重,Cii=0）。将图G划分为两个社区，原节点集合V分为两个大小相同的集合A和B（各含n个节点），并且使得社区之间连接的权重 T=求和Cab Kernighan-Lin算法

为最小值（a是A中的任意节点，b是B中的任意节点）。

为了解决这个问题，先给出如下定义：

节点a的外部权重：Ea=求和Cax（x为B中的节点） Kernighan-Lin算法

。节点b的外部权重类似。

节点a的内部权重：Ia=求和Cax（x为A中的节点） Kernighan-Lin算法

。节点b的内部权重类似。、

令节点z的外部权重与内部权重之差为：Dz=Ez-Iz Kernighan-Lin算法

。

当A中的节点a与B中的节点b交换后，社区间连接的总权重减少量为(此处为了让该值取正，所以定义为增益gain)：gain = Told - Tnew = (W+Ea+Eb-Cab) - (W+Ia+Ib+Cab) = Da+Db-2Cab Kernighan-Lin算法

。

算法描述：（参照原版论文，与wikipedia的算法略有不同，觉得wikipedia的不对）

输入：一个待划分的图G=(V,E，C)

输出：划分A和B

1. 给定一个初始划分A和B

2. do

3. A(1)=A; B(1)=B;

4. 对A(1)和B(1)中的每一个节点计算其D值；

5. for （p=1 to |V|/2）

6. A(p)中选出ai，Bp中选出和bj，使得 Kernighan-Lin算法

gain(p)=Dai+Dbj-2Caibj为最大值；

7. ap'=ai；bp'=bj；A(p+1)=A(p)-ap'；B(p+1)=B(p)-bp'；

8. p=p+1;

9. 更新A(p)和B(p)中每个节点的D值；

10. end for

11. 选择k使得 Kernighan-Lin算法

G=求和gain(i) 为最大值（k为gain(i)为正值的个数）；

12. if (G>0)

13. 把A中的a1',a2',...,ak'与B中的b1',b2',...,bk'进行交换；

14.until (G<=0)

15.return A，B

文章分析其算法时间复杂度在 Kernighan-Lin算法

n^2至(n^2)*logn Kernighan-Lin算法

之间。

之后，文章对算法性能又做了一定的改进，以提高其精度。大概思想是：采用类似分治法（不是很确定），将原解决方案略微转换，使其执行每一轮的时间增加(从t到t')，同时增加其找到最佳划分的概率(从p到p')。那么若原方案执行了k轮，那么原方案找到最佳划分的概率就是1-(1-p)^k Kernighan-Lin算法

，而新方案的成功率就是

1-(1-p)^(kt/t') Kernighan-Lin算法

。那么只要是的后者大于前者即可。

以上解决的是同规模划分，A和B规模大小相等的。那么若要将n个节点划分为两个规模不等的社区，分别含有n1和n2个节点（n1<n2，n1+n2=n）,文章采用如下方法：增加2*n2-n个虚假节点（与原图中节点没有任何连接），那么总结点数就为2*n2个节点，然后用上述方法划分成2个n2规模的社区，再去掉那些虚假节点，那么就得到n1规模和n2规模大小的两个社区了。

另外，对于将网络划分为多个（大于2）社区的情况（kn个节点，划分成k个社区），采用如下两种方法：（1）将kn个节点一直等规模划分，貌似这样对k有要求；

（2）将kn个节点划分为n个节点和(k-1)n个节点的两个社区，之后对(k-1)n个节点的社区再划分为n个节点和(k-2)n个节点的社区，如此往复下去。

参考文献：

1.维基百科对Kernighan-Lin算法的解释：http://en.wikipedia.org/wiki/Kernighan–Lin_algorithm

2.Karypis G, Kumar V. Multilevel< i> k</i>-way Partitioning Scheme for Irregular Graphs[J]. Journal of Parallel and Distributed computing, 1998, 48(1): 96-129.

声明：后半部分，由于文章阅读较浅显，所以可能含有一些错误，希望大家指出。

这篇关于Kernighan-Lin算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！