[科普中国]-Girvan和Newman社团发现算法

Girvan和Newman1于2002年提出的分裂算法已经成为探索网络社团结构的一种经典算法,简称GN算法。由网络中社团的定义可知，所谓社团就是指其内部顶点的连接稠密，而与其他社团内的顶点连接稀疏。这就意味着社团与社团之间联系的通道比较少，一个社团到另一个社团至少要通过这些通道中的一条。如果能找到这些重要的通道，并将它们移除，那么网络就自然而然地分出了社团。Girvan和Newman提出用边介数（2002）来标记每条边对网络连通性的影响。某条边的边介数是指网络中通过这条边的最短路径的数目。两顶点间的最短路径在无权网中为连接该顶点对的边数最少的路径。由此定义可知，社团间连边的边介数比较大，因为社团间顶点对的最短路径必然通过它们；而社团内部边的边介数则比较小。

GN算法的基本流程如下：

1)计算网络中各条边的边介数；

2)找出边介数最大的边，并将它移除(如果最大边介数的边不唯一，那么既可以随机挑选一条边断开也可以将这些边同时断开)；

3)重新计算网络中剩余各条边的边介数；

4)重复第2)、3)步,直到网络中所有的边都被移除。

算法中包括了重复计算边介数值的环节是十分必要的。因为当断开边介数值最大边后，网络结构发生了变化，原有的数值已经不能代表断边后网络的结构，各条边的边介数需要重新计算。举一个形象的例子：假如网络中有两个社团，它们之间只有两条边相连。起初其中一条边的边介数最大，而另外一条边介数较小， 则第一条边被断开。如果不重新计算各条边的边介数，那么第二条边依据其原有边介数值可能不会被立即断开。如果重现计算各条边的边介数，那么第二条边的边介数可能成为最大值,会被立即断开。这显然会对社团结构的划分产生重大的影响。