复杂网络中社团结构算法的综述

吴 悠

（武汉理工大学，湖北 武汉430070）

0 引言

随着对网络性质的物理意义和数学特性的深入研究， 人们发现许多实际网络都具有一个共同性质，即社团结构。 近年来，社团结构分析在生物学、计算机图形学和社会学中都有广泛的应用[2]。 目前关于复杂网络中社团结构算法的研究有很多，本文将介绍几种有代表性的方法。

1 Kernighan-Lin 算法

1.1 方法概述

Kernighan-Lin 算法是一种试探优化法。 它是一种基于贪婪算法原理将网络划分为两个大小已知的社团的二分法。

1.2 实现过程及应用[3]

K-L 算法可以描述为：首先，将网络的节点随机地划分为已知大小的两个社团。在此基础上，考虑所有可能的节点对，其中每个节点对的节点分别来自两个社团。对每个节点对，如果交换这两个节点的话，计算可能得到Q 的增益Q=Q交换前-Q交换后,然后交换最大的△Q 对应的节点对，同时记录交换后的Q 值。 规定每个节点只能交换一次。 重复这个交换过程，直到某个社团内所有的节点都被交换一次为止。 需要注意的是， 在节点对交换的过程中，Q 值并不一定是单调增加的。 不过，即使某一步的交换会使Q 值有所下降，也仍然可能在其后的步骤中出现一个更大的Q 值。 当交换完毕后，便找到上述交换过程中所记录的最大Q 值。 这时对应的社团结构就认为是该网络实际的社团结构。

1.3 评价

该方法存在一个严重的缺陷，即必须事先知道该网络的两个社团大小分别是多少，否则就很可能不会得到正确的答案。 K-L 算法的这个缺陷使得它在实际网络分析中难以应用。 而且，即使解决了这个问题，它仍然面临着如何事先知道网络社团数目，以确定二分法要重复到哪一步停止的问题。

2 谱平分法

2.1 方法概述

该算法利用网络结构的Laplace 矩阵中不为0 的特征值所对应的特征向量和同一个社区内的节点对应的元素近似值相等的原理对网络社区进行划分。

谱平分法本质上是一种二分法，在每次二分的过程中，网络被分割成两个近似平衡的子网络。 当网络中含有多个社团时，谱平分法递归地分割现存的子网络，直到满足预先定义的停止条件为止。

2.2 实现过程

该算法可以描述为：一个有n 个节点的无向图G 的Laplace 矩阵是一个n×n 维的对称矩阵L。 如果节点i 和节点j 有边相连，则lij=-1，否则lij=0.对角线上的元素lij表示节点i 的度。 由于Laplace 矩阵所有的行或列的和都为0，因此，该矩阵总有一个特征值为0，且其对应的特征向量为I=（1，1，1,···，1）。 我们也可以将矩阵L 表示成L=K-A，其中K 是一个对角矩阵，其对角线上的元素对应各个节点的度，而A则为该网络的连接矩阵。 可以从理论上证明，不为零的特征值所对应的特征向量的各元素中，同一个社团内的节点对应的元素是近似相等的。 因此，可以根据复杂网络的Laplace 矩阵次小特征值λ2对应的特征向量，所有正元素对应的那些节点都属于同一社团，而所有的负元素对应的那些节点都属于另一个社团，这样就将其分为两个社团。

2.3 评价及改进方法

谱平分法主要缺陷是只能将图分成2 个子图， 若要分成多个子图，则只能多次应用该方法。即使这样可行，我们预先也无法确定究竟将图分割成多少个子图才合适。

为了克服这一缺陷，Capocci 等人在传统谱分析法的基础上提出另一种算法。 传统谱平分法是基于Laplace 矩阵L=K-A。Capocci 算法[4]则是基于标准矩阵N=K-1A。 利用行标准化的转换可得，矩阵N 的最大特征值总是等于1，相应的特征向量称为平凡特征向量。 在对社团化明显的网络的分析中发现，如果网络自然呈现g 个社团，则标准矩阵就有g-1 个十分接近1 的第一非平凡特征值，而其余的特征值都与1有较大的距离。 这g-1 个特征值所对应的特征向量（称为第一非平凡特征向量或者第二特征向量）有一个特性：在同一个社团中的顶点所对应的值较为接近。因此，特征向量中元素的值呈现阶梯状分布，并且阶梯的级数与社团的个数相匹配。

3 GN 算法

3.1 方法概述

Girvan 和Newman 提出了一种基于边介数的分裂算法，即G-N 算法。 不断地从网络中移除介数最大的边。 边介数定义为网络中经过每条边的最短路径数目。

3.2 实现过程

首先，计算网络中各条边的边介数，找出边介数最大的边，并将它移除（如果最大边介数的边不唯一，那么既可以随机挑选一条边断开也可以将这些边同时断开）；然后，重新计算网络中剩余各条边的边介数；接着重复上面的步骤，直到网络中所有的边都被移除。

3.3 评价及改进方法

GN 算法弥补了一些传统算法的不足，但是也存在一个缺陷，即它对于网络的社团结构并没有一个量的定义。因此不能直接从网络的拓扑结构判断它所求得的社团结构是否是实际网络中的社团结构，从而需要一些附加的关于网络意义的信息来判断所得到的社团结构是否具有实际意义。

为了得到具有实际意义的社团结构，Newman 等人引进了一个衡量网络划分质量的标准——模块度。 考虑某种划分形式，它将网络划分为k 个社团。 定义一个k×k 维的对称矩阵E=（eij），其中元素eij表示网络中连接两个不同社团的节点的边在所有边中所占的比例，这两个节点分别位于第i 个社团和第j 个社团。

4 结束语

复杂网络中社区的划分具有重要的使用价值。本文给出了三种经典的复杂网络社团划分算法，较为详细的描述了各种算法的核心思想和基本过程，并对各算法进行了适当的分析和比较，为影虎针对不同的复杂网络选择适合的社区划分算法提供了一定的借鉴作用。

［1］韩瑞凯，孟嗣仪.基于兴趣相似度的社区结构发现算法研究[J].铁路计算机应用，2010,19（10）：10-14.

［2］张聪，沈惠璋.复杂网络中社团发现的快速划分算法[J].系统工程，2011,29（208）：93-98.

［3］汪小帆，刘亚冰.复杂网络中的社团结构算法综述[J].电子科技大学学报，2009,38（5）：537-543.

［4］谢福鼎，张磊.一种基于谱平分法的社团划分算法[J].计算机科学，2009,36（11）：186-188.

［5］安娜，谢福鼎.一种基于GN 算法的文本概念聚类新方法[J].计算机工程与应用，2008,44（14）：142-144.