先说下写这篇文章的初衷,首先是为了记录我科研的一些笔记,其次呢是我在网上查阅图分割问题的时候,发现很难找到合适的讲解,基本都被图像处理的知识所占据。但并不是每个人都会有时间去查阅论文,所以就写下这篇博客来填补这方面的空白,谢谢诸位看官

一,图分割

定义:指将网络顶点分割为指定规模,指定数量的非重叠群组,并使得群组之间的边数最小


算法背景:实际上在图挖掘领域最早出现的问题就是图分割,当社团发现问题出现以后科学家首先使用图分割算法来发现社团,但后来渐渐放弃了。原因就是图分割算法有以下的局限:

1,需要事先指定分割的子图规模以及个数

2,一般的图分割算法,只会将图分割成两个子图,如果想获得多个子图那么需要不断的进行二分

二,问题定义




 简单的说就是,在一个无向有权图中,将图划分成若干个子图,并且使得子图之间的割边的权值和最大。对于这样一个NP难的问题,科学家很自然的想到了使用启发式算法来解决。

三,算法说明

1,数学描述


问题的解决思路很简单,就是先随机产生两个划分,计算他们的cost,然后通过一些操作是这个cost不断下降,达到最优解,注意这里的最优解明显是局部的,但是论文作者说这个局部解很有可能也是全局,这个问题我们咱不讨论;因为很多情况,局部最优解也是很优秀的解,而且启发式算法很容易避免局部最优解的问题。

那么如何进行所谓的“操作”呢?




在两路图分割问题中:A,B是初始的两个划分,通过交换内部的点或者集合,形成新的划分,并在算法的指导下,使划分的cost下降,逐渐逼近最优解;现在问题的解决思路基本明晰了,问题转化为在A,B中挑选X,Y




我简单翻译一下,作者定义了三个变量E,I,D分别代表着某点的外部cost,内部cost,和内外部cost之差,并证明了一个定理,如果交换两个点,会对总的cost产生什么样的影响,就是这个gain,显然接下来我们要控制这个gain向下降的方向变化。

2,算法简述


我们先用自然语言描述这个过程,第一步计算出全集里所有元素的D值,第二步在划分A,B中选择a1,b1进行交换并计算gain值,第三步对于A,B中的其他元素进行计算D值;接下来重复第二步,用{A-a1}和{B-b1}替换A,B,再计算gain'值,直到所有节点都被使用。每做一步就将gain值保存起来,并使得 
,我们通过选择算法执行的步数K,来优化参数G,当G>0的时候,说明通过内部交换可以降低G值,算法继续执行;当G=0,我们便到达了局部最优点。以下就是算法的执行过程

 



算法过程中有几个判断需要着重讲一下,一是p=n?二是G>0?


在第一个判断中,集合的总数是2n,n是等大图划分中一半的节点数,也是我们程序的迭代最大次数;在第二个判断中,我们求得k值使得G值最大,接下来交换1至k的节点,然后继续迭代,直到G<=0才终止。

此部分的代码移步https://github.com/mcavus/Kernighan-Lin
<https://github.com/mcavus/Kernighan-Lin>

对于不等大图的划分,目前来解决这个问题的一种主流方法,就是添加哑元素,来使两个集合的数量相同。