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

一种基于三角环社区发现算法 　　摘要：在大型复杂网络中自动搜寻或发现社区具有重要的实际应用价值。该文把超图模型以及基于此的聚类算法应用到社区结构发现领域。对于简单图的社区发现，引入了边凝聚系数和三角环等概念，提出了基于三角环的社区结构发现方法。通过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算法）。考虑无向无权重的形