Kernighan-Lin算法是一种启发式算法&＃xff0c;基于贪婪原理将网络划分为两个大小已知的社团。
所要解决的问题描述&＃xff1a;给定一个无向带权图G&＃61;(V,E&＃xff0c;C)&＃xff0c;其中V为一含有2n个节点的集合&＃xff0c;E为边集合&＃xff0c;C为2n*2n且对称的权重矩阵&＃xff08;Cij表示节点i和节点j直接边的权重,Cii&＃61;0&＃xff09;。将图G划分为两个社区&＃xff0c;原节点集合V分为两个大小相同的集合A和B&＃xff08;各含n个节点&＃xff09;&＃xff0c;并且使得社区之间连接的权重 T&＃61;求和Cab ![Kernighan-Lin算法]( "Kernighan-Lin算法")
为最小值&＃xff08;a是A中的任意节点&＃xff0c;b是B中的任意节点&＃xff09;。
为了解决这个问题&＃xff0c;先给出如下定义&＃xff1a;
节点a的外部权重&＃xff1a;Ea&＃61;求和Cax&＃xff08;x为B中的节点&＃xff09;![Kernighan-Lin算法]( "Kernighan-Lin算法")
。节点b的外部权重类似。 节点a的内部权重&＃xff1a;Ia&＃61;求和Cax&＃xff08;x为A中的节点&＃xff09;![Kernighan-Lin算法]( "Kernighan-Lin算法")
。节点b的内部权重类似。、 令节点z的外部权重与内部权重之差为&＃xff1a;Dz&＃61;Ez-Iz![Kernighan-Lin算法]( "Kernighan-Lin算法")
。 当A中的节点a与B中的节点b交换后&＃xff0c;社区间连接的总权重减少量为(此处为了让该值取正&＃xff0c;所以定义为增益gain)&＃xff1a;gain &＃61; Told - Tnew &＃61; (W&＃43;Ea&＃43;Eb-Cab) - (W&＃43;Ia&＃43;Ib&＃43;Cab) &＃61; Da&＃43;Db-2Cab![Kernighan-Lin算法]( "Kernighan-Lin算法")
。
算法描述&＃xff1a;&＃xff08;参照原版论文&＃xff0c;与wikipedia的算法略有不同&＃xff0c;觉得wikipedia的不对&＃xff09;
输入&＃xff1a;一个待划分的图G&＃61;(V,E&＃xff0c;C)
输出&＃xff1a;划分A和B
1. 给定一个初始划分A和B
2. do
3. A(1)&＃61;A; B(1)&＃61;B;
4. 对A(1)和B(1)中的每一个节点计算其D值&＃xff1b;
5. for &＃xff08;p&＃61;1 to |V|/2&＃xff09;
6. A(p)中选出ai&＃xff0c;Bp中选出和bj&＃xff0c;使得![Kernighan-Lin算法]( "Kernighan-Lin算法")
gain(p)&＃61;Dai&＃43;Dbj-2Caibj为最大值&＃xff1b; 7. ap&＃39;&＃61;ai&＃xff1b;bp&＃39;&＃61;bj&＃xff1b;A(p&＃43;1)&＃61;A(p)-ap&＃39;&＃xff1b;B(p&＃43;1)&＃61;B(p)-bp&＃39;&＃xff1b;
8. p&＃61;p&＃43;1;
9. 更新A(p)和B(p)中每个节点的D值&＃xff1b;
10. end for
11. 选择k使得![Kernighan-Lin算法]( "Kernighan-Lin算法")
G&＃61;求和gain(i) 为最大值&＃xff08;k为gain(i)为正值的个数&＃xff09;&＃xff1b; 12. if (G>0)
13. 把A中的a1&＃39;,a2&＃39;,...,ak&＃39;与B中的b1&＃39;,b2&＃39;,...,bk&＃39;进行交换&＃xff1b;
14.until (G<&＃61;0)
15.return A&＃xff0c;B
文章分析其算法时间复杂度在![Kernighan-Lin算法]( "Kernighan-Lin算法")
n^2至(n^2)*logn![Kernighan-Lin算法]( "Kernighan-Lin算法")
之间。
之后&＃xff0c;文章对算法性能又做了一定的改进&＃xff0c;以提高其精度。大概思想是&＃xff1a;采用类似分治法&＃xff08;不是很确定&＃xff09;&＃xff0c;将原解决方案略微转换&＃xff0c;使其执行每一轮的时间增加(从t到t&＃39;)&＃xff0c;同时增加其找到最佳划分的概率(从p到p&＃39;)。那么若原方案执行了k轮&＃xff0c;那么原方案找到最佳划分的概率就是1-(1-p)^k![Kernighan-Lin算法]( "Kernighan-Lin算法")
&＃xff0c;而新方案的成功率就是 1-(1-p)^(kt/t&＃39;)![Kernighan-Lin算法]( "Kernighan-Lin算法")
。那么只要是的后者大于前者即可。
以上解决的是同规模划分&＃xff0c;A和B规模大小相等的。那么若要将n个节点划分为两个规模不等的社区&＃xff0c;分别含有n1和n2个节点&＃xff08;n1
另外&＃xff0c;对于将网络划分为多个&＃xff08;大于2&＃xff09;社区的情况&＃xff08;kn个节点&＃xff0c;划分成k个社区&＃xff09;&＃xff0c;采用如下两种方法&＃xff1a;&＃xff08;1&＃xff09;将kn个节点一直等规模划分&＃xff0c;貌似这样对k有要求&＃xff1b;
&＃xff08;2&＃xff09;将kn个节点划分为n个节点和(k-1)n个节点的两个社区&＃xff0c;之后对(k-1)n个节点的社区再划分为n个节点和(k-2)n个节点的社区&＃xff0c;如此往复下去。
参考文献&＃xff1a;
1.维基百科对Kernighan-Lin算法的解释&＃xff1a;http://en.wikipedia.org/wiki/Kernighan–Lin_algorithm
2.Karypis G, Kumar V. Multilevel k-way Partitioning Scheme for Irregular Graphs[J]. Journal of Parallel and Distributed computing, 1998, 48(1): 96-129.
声明&＃xff1a;后半部分&＃xff0c;由于文章阅读较浅显&＃xff0c;所以可能含有一些错误&＃xff0c;希望大家指出。
京公网安备 11010802041100号