一种基于三角环的社区发现算法

李学强　钟大伟　孙圣民

摘要：在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现领域。对于简单图的社区发现，引入了边凝聚系数和三角环等概念，提出了基于三角环的社区结构发现方法。通过Zachary网络的实例验证和算法的对比分析，证明了该算法在时间复杂度上能提高一个数量级。

关键词：社区结构；三角环；边凝聚系数；社会网络

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2013）07-1540-03

在现实生活中存在着各种各样的网络系统，如人际关系网、合作网、交通运输网、计算机网等。许多现实系统的网络模型是介于完全规则和完全随机之间的，这种网络被称为复杂网络[1]。复杂网络不仅具有小世界、无标度特性还具有社区结构[2]的特性。社区内部的节点之间的联系相对紧密，而社区之间的联系相对稀疏[3]。复杂网络中的社区发现的研究起源于社会学的研究工作。能够在大型复杂网络中自动搜寻或发现社区具有重要的实用价值，如社会网络中的社区代表根据兴趣或背景而形成的真实的社会团体[4]，发现社会网络中的这些社区有助于我们更好地理解和应用社会网络。目前，社区发现的算法很多，其中Kernighan-Lin算法[5]、Laplace圖特征值的谱二分法[6]、GN算法[7]等比较经典。其中GN算法是Newman和Girvan在其研究中提出了基于边介数的分割方法，尽管该方法计算量很大，但由于其性能优越而成为社区发现研究的重要参考模型。

尽管人们对复杂网络的社区发现问题已进行了大量的研究，但是仍然还存在一些目前无法解决的问题，如社区的概念虽然大量使用，但缺乏严格的数学定义；大多数的发现算法计算量很大；很多算法不是针对异构数据集。因此，复杂网络中的社区发现研究还远没有形成体系，有许多工作有待于进一步完善[8]。

本文给出一种新的社区发现算法，根据三角环来判断社区。该文的结构如下：第1节算法的整体描述；第2节对算法进行实例验证并与经典算法作对比；第3节总结全文。

1 算法介绍及分析

1.1 相关概念的引入

三角环：网络中边数为3的闭合回路形成的三角形。如图1中，节点3、4、6；节点4、5、6等可以构成三角环的形式。

点凝聚系数：对于某个点的邻居节点之间实际存在的边数与邻居节点之间可能存在的最大边数之比。一个网络的凝聚系数就是网络中节点凝聚系数的平均值。如图1：节点1的邻居节点分别是2、3、4、5、6，共5个节点。它们之间存在的最大边数为：5（5-1）/2=10；实际上这5个节点间的有7条边，那么节点1的点凝聚系数为：7/10=0.7。

边凝聚系数：借助于节点的凝聚系数，来引入边的凝聚系数概念。一条边的边凝聚系数定义为包含该边的三角环所占的比例：

[Cij=zij+1min（ki-1，kj-1）] （1）

其中，[ki]，[kj]分别表示节点i和节点j的度数，[zij]表示网络中实际包含的三角环的个数。上式中的分母表示包含该边的最大可能的三角环的个数。图1中，节点3和节点6的度数分别是5和4，则最多形成min（5-1，3-1）=3个三角环；而实际上包边E3，6的三角环有三个：节点1、3、6，节点3、5、6，节点3、4、6.所以C3，6=4/3。

图1 凝聚系数示意图

将整个网络G视为图，那么一个社区V实际上就是G的子图。社区V中的一个节点i的度[ki]来自两部分，分别是V的内部（[kiin（V）=j∈VAi，j]）和V的外部（[kiout（V）=j?VAi，j]）。下面给出社区紧密程度的两种级别[9]：

如果社区V内的任意一个节点i的[kiin（V）]均大于[kiout（V）]，即[kiin（V）>kiout（V）]，则称该社区是强连接社区。

如果社区V内的所有节点的[kiin（V）]和大于[kiout（V）]的和，即[i∈Vkiin（V）>i∈Vkiout（V）]，则称该社区为弱连接社区。

1.2 算法的思想及主要流程

前面提到的GN算法是一种分裂算法。它的基本思想是，通过不断的从网络中移除介数最大的边将整个网络分解成不同社区。在这里，边的介数定义为网络中经过该边的最短路径的数目。这种算法为区分一个社区内部边和连接社区之间的边提供了一种有效的度量标准。

GN算法虽然能弥补一些传统算法的不足，但是一般要指定社区的个数，否则，该算法不知道要将网络分解到什么程度停止。另外，该算法的时间复杂度较高，为O（n3）。算法效率较低的一个重要原因是边介数的计算开销大。针对上述情况，这里提出一种基于三角环的社区发现方法（Triangle Ring Community Detecting简称TRCD算法）。考虑无向无权重的形式，用邻接矩阵[Ai，j]表示节点间的关系，有边相连则值为1，无边相连则为0。

上述两个社区的级别可以作为判断子图是否为一个社区的标准，只有满足上述两个定义的子图才能作为一个社区。首先从整个网络开始，不断的删除边，直到不存在满足上述定义的社区为止。该文中的方法和前面的GN算法类似，都是分裂式算法。该方法不是根据边介数来选择要删除的边，而

是根据边凝聚系数这个新的指标。

根据上述基本思想得到算法的具体步骤如下：

Step1：根据公式（1）所示，计算整个网络中的每一条边的凝聚系数[Cij]；

Step2：删除凝聚系数最小的边[Eij]；

Step3：重新计算以i和j为顶点的所有边的凝聚系数，而其它的边不需要重新计算；

Step4：返回Step2，直到网络中不存在符合上述定义的社区。

1.3 算法分析

对于一个含有n个节点m条边的网络，整个算法运行的时间为[O（m4/n2）]。显然该算法的时间复杂度要低于GN的时间复杂度。因为所考虑的是局部信息，去边以后无须所有的边重新计算，所以降低了时间复杂度。该算法依赖于网络中的三角环，如果网络中三角环的数量很少，该方法将失去意义。大量的实例研究表明，社会网络中三角环的数量比较大，而非社会网络中，三角环的数量则相对较少。所以这种方法更适合于社会网络。

2 实例验证

2.1 在Zachary网络上的实验

图2所示是某大学空手道俱乐部中34个成员之间的社会关系网络，曾是人类学家怀恩扎卡利（Wayne Zachary）在20世纪70年代研究的对象。Zachary网络在复杂网络的社区结构分析中已经成为一个经典问题，成为了衡量社区结构划分算法准确性的标准[10]。在调查研究过程中，该俱乐部的主管与校长因是否抬高俱乐部收费的问题产生了争执。结果，这个俱乐部分裂成了两个分别以校长和主管为核心的小俱乐部。下面以Zachary网络为例检验TRCD算法在实际网络中的应用。

按照文中算法的流程，得到最终的结果如下图3所示，为了与图2方便比较，图3中没有将边去掉。其中圆形节点代表由节点27得到社区A，方形节点代表另一个社区B。A和B社区就代表着以校长和主管为核心的小俱乐部，这个结果同实际存在的社区是一致的。

2.2 与经典算法的比较

从算法准确性和算法的复杂度两方面将文中的算法与三种经典的算法作对比。

GN算法是一种分裂方法，其基本思想是不断地从网络中移除介数最大的边。谱二分法是利用网络结构的Laplace矩阵中不为0的特征值所对应的特征向量和同一个社区内的节点对应的元素近似值的原理对网络社区进行划分。这两种算法应用到Zachary网络中所得到的社区结构如图4所示。

其中图4中所有的圆形节点是在同一社区，其余节点属于另一个社区。K-L算法是一种试探优化法，它是一种利用贪婪算法将复杂网络划分为两个社区的二分法。若将K-L算法应用到Zachary网络，得到的结果和文中算法一致，如上图3。

图3和图4的区别是：节点3被划分到两个不同的社区。而真实的社区结构如图5所示，所以说，GN算法和谱二分法的结果使得节点3被错误划分。并且谱二分法仅适用于由两个社区组成的大网络结构，而GN算法对网络社区进行划分时必须事先知道网络中存在的社区个数。虽然K-L算法得到的社区跟实际结果一致，但是必須提前知道两个社区的大小分别是16和18，因此K-L算法很难适用于实际网络。这也说明了经典算法存在一些不足。对TRCD算法而言，在进行社区划分之前不需要指定社区个数，这是一种自然划分，能够得到网络中实际存在的社区结构，而且算法的准确性较高，所以该算法能克服其他算法的一些不足。

对于一个含有n个节点m条边的网络，TRCD算法的时间复杂度为O（m），空间复杂度是O（m4/n2）。将该算法与经典的三种算法的复杂度作了对比，如表1。

[算法＼&空间复杂度＼&时间复杂度＼&GN算法＼&O（m+n）＼&O（m2n）＼&谱二分法＼&O（n2）＼&O（n3）＼&K-L算法＼&O（m+n）＼&O（n2）＼&TRCD算法＼&O（m+n）＼&O（m4/n2）＼&]

经过对比分析，我们发现TRCD算法的思想易于理解，步骤简洁；算法的准确性较高；在复杂度方面，该算法也有一定的提高。

3总结

文中的TRCD算法，是在研究了近年来常见的一些方法的基础上提出了根据边的凝聚系数来求得下一步将要去掉的边，因为考虑的是局部信息，去边以后不需要重新计算所有的边，所以与GN算法相比降低了时间复杂度。通过与经典算法的比较，可以发现TRCD算法在算法的准确性和算法复杂度方面都有一定的优越性。特别地，该算法比较适合三角关系较多的网络。

参考文献：

[1] 杨博，刘大有，LIU Jiming，等.复杂网络聚类方法[J].软件学报，2009，20（1）：54-66.

[2] Santo F.Community Detection in Graphs[EB/OL].（2009-06-12）[2012-03-01].http：//arxiv.org/abs/0906.0612.（下转第1550页）

[3] Mucha P J，Richardson T，Macon K，et al.Community Struct- ure in time dependent， mutiscale，and multiplex networks[J].Science， 2010， 328（5980）：876-878.

[4] 林友芳，王天宇，唐锐，等.一种有效的社会网络社区发现算法模型和算法[J].计算机研究与发展，2012，49（2）：337-345.

[5] FORTUNATO S.Community detection in graphs[J].Physics Report，2010，486（3-5）：75-174.

[6] Newman M E J，Girvan M.Finding and evaluating communit-y structure in network[J].Physical Review E，2004，69（2）：26-113.

[7] Luo Ting，Zhong Caiming，Ying Xinyang，et al.Detecting Co-Mmunity Structure Based on Edge Betweenness[EB/OL].（2011-09-15）[2012-03-02].http：//ieeexplore.ieee.org/stamp/stamp.jsp？tp=&arnumber=6019678&tag=1.

[8] 马延妮.在线社会网络团结构分析[D].北京：北京交通大学，2009.

[9] Han jian，Yang Bing-ru.Community structure discovery algo-rithm based on edge clustering coefficient[J]. Application Researchof Computer，2010，46（35）：86-89.

[10] Qi Luo.A new Community Structure Detection Method Based on Structural Similarity.（2012-01-02）[2012-03-02].http：//ieeexplore.ieee.org/stamp/stamp.jsp？tp=&arnumber=6128320.