论文导读:：复杂网络是复杂系统的高度抽象。即社区结构特性[3]。算法是一种试探优化法[4]。算法。
关键词：复杂网络，社区结构，Laplace图谱，Kernighan-Lin算法，GN算法
1引言
现实生活中存在着各种各样的网络系统，如人际关系网、合作网、交通运输网、计算机网等。网络模型是描述这些复杂系统的最有效模型。通过对现实系统网络模型的研究，人们发现许多现实系统的网络模型是介于完全规则和完全随机之间的。由于这种网络是真实复杂系统的拓扑抽象因此它被称为复杂网络。
复杂网络是复杂系统的高度抽象，除具备小世界[1]、无标度[2]等重要特性外，还拥有另外一个重要特征，即社区结构特性[3]。也就是说，整个网络是由若干个“群（group）”或“团（cluster）”构成的。每个群内部的节点之间的连接相对非常紧密，但是各个群之间的连接相对来说却比较稀疏。如图1所示。图中的网络包含三个社团，分别对应图中三个圆圈包围的部分。在这些社团内部，节点之间的联系非常紧密，而社团之间的联系就稀疏的多。
在大型复杂网络中进行社区搜寻或发现社区，具有重要的实用价值。如，社会网络中的社区代表根据兴趣或背景而形成的真实的社会团体；引文网络中的社区代表针对同一主题的相关论文；万维网中的社区就是讨论相关主题的若干网站而生物化学网络或者电子电路网络中的社区则可能是某一类功能单元。发现这些网络中的社区有助于研究人员更加有效地理解和开发这些网络。
图1 一个小型的具有社团结构性质的网络
网络社团结构的研究起源于社团学，已经有很长的历史期刊网。它与计算机科学中的图形分割和社会学中的分级聚类有着密切的关系。目前GN算法，关于复杂网络中的社区发现算法已有很多，这些方法的核心思想、执行效率、使用范围等方面差别较大。本文着重叙述了三种典型的复杂网络社区识别算法，Kernighan-Lin 算法、Laplace图特征值的谱二分法和GN算法，并对此三种方法进行了适当的分析和比较。
2典型的网络社区识别算法
(1) Kernighan-Lin 算法
Kernighan-Lin算法是一种试探优化法[4]。它是一种利用贪婪算法将复杂网络划分为两个社团的二分法。该算法引入增益值P，并将P定义两个社团内部的边数减去连接两个社团之间的边数，然后再寻找使 P值最大的划分方法。整个算法可描述如下：
首先，将网络中的节点随机地划分为已知大小的两个社团。在此基础上，考虑所有可能的节点对，其中每个节点对的节点分别来自两个社团。对每个节点对，计算如果交换这两个节点可能得到的P的增益ΔP=P交换后-P交换前，然后交换最大的ΔP对应的节点对，同时记录交换以后的 P值。规定每个节点只能交换一次。重复这个交换过程，直到某个社团内所有的节点都被交换一次为止。需要注意的是，在节点对交换的过程中，P值并不一定是单调增加的。不过，即使某一步的交换会使P值有所下降，仍然可能在其后的步骤中出现一个更大的P值。当交换完毕后，便找到上述交换过程中所记录的最大的P值。这时对应的社团结构就认为是该网络实际的社团结构。
(2)基于Laplace图特征值的谱二分法
该算法利用网络结构的Laplace矩阵中不为零的特征值所对应的特征向量和同一个社区内的节点对应的元素近似值相等的原理对网络社区进行划分。该算法过程如下：
设图G是一个具有n个节点的无向图，G的Laplace矩阵L是一个n×n的对称矩阵。L的对角线元素Lii是节点i的度，非对角线元素Lij表示节点i和节点j的连接关系，当节点i和节点j之间有边连接时,则 Lij = -1,否则为Lij = 0。容易验证，L的每一行的和以及每一列的和均为0，因而，向量I=(1,1,l……1)'是L相应于特征值0的特征向量。
如果图G可以被分解成g个互不重叠、互不相连的子图Gk，则其Laplace矩阵L就是一个分成g块的对角矩阵块，每个对角矩阵块就是相应的分支子图的Laplace矩阵。显然，此时L存在g个与特征值0对应的特征向量v(k)，k=1,2,,gGN算法，当节点i属于该社团时，vi(k)=1，否则vi(k)=0。
如果图G可以被分解成g个子图，但子图之间存在少量连接时，其相应的Laplace矩阵L就不再是一个分成g块的对角阵。此时，对应0这个特征值就只有一个特征向量I。但是，在0的附近还有g-1个比零稍大的特征值，并且这g-1个特征值相应的特征向量可以近似地看成上述特征向量v(k)的线性组合。因此，从理论上来说，只要找到Laplace矩阵中比零稍大的那些特征值，并且对其特征向量进行线性组合，就可以近似的得到这些子图[5]。
考虑一个例子，即将图G分割成2个子图。由于对称矩阵的任意两个2个特征值所对应的特征向量相互正交，因此Laplace矩阵L的任意对应于非零特征值的特征向量均正交于向量I=(1,1,l……1)'，从而所有非零特征值的特征向量必须具有正分量和负分量。如果图G可以分解为2个子图使得这2个子图之间仅存在很少的连接，则必存在一个特征向量，其特征值近似于0；该特征向量的正分量对应于一个子图，负分量对应于另一个子图。因此，可以通过观察最小非零特征值所对应的特征向量，根据特征值元素的正负将一个网络分解成2个社区，该方法称为谱二分法[6-7]期刊网。
(3) GN算法
GN算法是一种分裂方法[8]。其基本思想是不断的从网络中移除介数最大的边。边介数定义为网络中经过每条边的最短路径的数目。具体算法如下：
①计算网络中所有边的介数。
②移除介数最高的边。
③重新计算所有受影响的边的介数。
④重复步骤②，直到每个节点就是一个退化社团为止。
3三种算法的对比分析
从上述三种算法的过程来看，Laplace图特征值谱二分法，Kernighan-Lin算法和GN算法计算简洁，都易于程序实现。Kernighan-Lin算法的时间复杂度相对于与其他两种算法较小些，但该算法对网络中社区划分的准确度不高，适用于小规模网络社区划分。而Laplace图特征值谱二分法和GN算法则适合于较大网络的社区划分。其中，Laplace图特征值谱二分法仅适用于由2个社团组成的大网络结构GN算法，其时间复杂度比GN算法要大些。而GN算法在对网络社区进行划分时必须事先知道网络中存在的社团个数，如表1所示。
总之，三种社区划分算法各有优缺点，在实际应用时，可根据所要划分的网络特点，选择单独一种算法或综合多种算法对网络进行划分，以使划分结果更接近于网络社区实际状况。
表1 三种社区划分算法比较
|
算法名称
|
时间
复杂度
|
优点
|
缺点
|
|
Kernighan-
Lin算法
|
O(n2)
|
计算简单，易于划分
|
准确度不高，且必须事先知道网络中社团规模大小，适用于小规模网络
|
|
Laplace图特征值谱二分法
|
O(n3)
|
计算简单，易于程序实现
|
仅适用于由2个社团组成的网络结构，时间复杂度较大
|
|
GN算法
|
O(m2n)
|
考虑网络全局，划分社区准确度较高
|
对网络社团结构缺少量的定义，事先知道社团个数
|
注：n ,m分别为网络中的节点数和边数
3 结论
复杂网络中社区的划分具有重要的使用价值。本文给出了三种经典的复杂网络社团划分算法，较为详细地描述了各种算法的核心思想和基本过程，并对各算法进行了适当的分析和比较，为用户针对不同的复杂网络选择合适的社区划分算法提供了一定的借鉴作用。
参考文献：
[1]Watts D J,Strogatz S H. Collective dynamics of ‘small-world’ networks. Nature, 1998,393(66844): 440-442
[2]Barabasi A L,Albert R. Emergence of scaling in random networks. Science, 1999,286(5493):509-512
[3]Newman M E J,Girvan M. Finding and Evaluating Community Structure in Networks[J]. PhysicalReview E ,2004,69(2):26-113.
[4]Kernighan BW,Lin S. A efficent heuristic procedure for partitioning graphs. Bell SystemTechnical Journal. 1970, 49:291-307
[5]Newman M E J. Detecting Community Structure inNetworks[J]. Eur.Phys.J.B., 2004, 38(2):321-330.
[6]Fildler M. Algebraic Connectivity of Graphs[J]. CzechMath J. 1973, 23 (98): 2 98-305.
[7]Phothen A, SimonH. Partitioning Sparse Matrices with Eigenvectors of Graphs[J]. SIAM J. Matrix Anal. Appl., 1990, 11 (3):430-452.
[8]Girvan M, Newman MEJ. Community structure in socialand biological networks. Proc. Natl. Acad. Sci. 2001, 99:7821-7826
|
