结合熵有效性函数的FCM算法识别社团结构

贾宁宁，　封　筠

(石家庄铁道大学 信息科学与技术学院,河北 石家庄　050043)



结合熵有效性函数的FCM算法识别社团结构

贾宁宁，封筠

(石家庄铁道大学 信息科学与技术学院,河北 石家庄050043)

摘要：挖掘和发现复杂网络中的社团结构是复杂网络研究的基础性问题。针对复杂网络中的社团结构往往具有重叠性，提出了结合熵有效性函数的模糊聚类(Fuzzy c-means, FCM)算法。首先基于信息熵提出了熵有效性函数，用于确定网络的“最佳”聚类数；其次给出了聚类数范围和两个过滤条件；最后将三者与FCM算法相结合，应用到Zachary’s karate club network、Dolphin social network和American college football network的社团结构检测。为了进一步体现熵有效性函数的优越性，将熵有效性函数和模块度函数，分别与k-means算法相结合，对3个网络进行了实验。实验结果表明，熵有效性函数可以较准确的找到“最佳”聚类数，且结合熵有效性函数的FCM算法划分结果精确度都在90%以上。

关键词：熵有效性函数；聚类数范围；过滤条件；模糊聚类；社团结构

0引言

复杂网络一般指由数量巨大的节点和节点之间错综复杂的连边共同构成网络，可刻画Internet网、交通网、生物网和社会关系网等实际系统[1-2]。2002年Girvan和Newman首次提出社团结构，给出了社团结构的定性描述：社团内部联系紧密，社团之间联系稀疏，并基于边介数提出了GN算法[3]，在国际上掀起了一股社团结构发现的热潮。

根据节点能否同时属于多个社团，可将社团分为非重叠社团和重叠社团。初期的社团结构发现算法对象为非重叠社团，主要算法有谱方法[4-6]、GN算法[3]和Newman快速算法[7]。最近人们发现，这种硬划分并不能真正反映真实世界中节点与社团的实际关系，例如：在人际关系网中，每个人都可能会属于家庭、工作单位、朋友圈子等多个社会团体。在蛋白质相互作用网络中，一个节点可能会有多种生物功能，比如大部分蛋白质都同时属于多个蛋白质复合物[1,8]。因此重叠社团发现更符合真实世界的社团组织规律，成为了近几年社团发现研究的新热点。2005年Palla等[9]基于完全子图提出了首个能够发现重叠社团的派系过滤算法(clique percolation method,CPM)。同年Adamcsek等[10]开发了一个基于CPM算法的免费应用软件CFinder。张世华[11]利用谱方法将网络空间转换到特征空间，进而结合模糊聚类算法(fuzzy c-means,FCM)识别复杂网络中的重叠社团。FCM算法属于基于目标函数的算法，具有原理简单、解决问题范围广、可转化为优化问题。借助经典数学的非线性规划理论求解和易于实现的特点，使其在重叠社团发现方面得到了广泛关注。但FCM算法也存在一些问题：一是需要预先确定聚类数，破坏了算法的无监督性和自适应性；二是模糊加权指数的选择缺少理论指导；三是对初始化敏感，容易陷入局部最小值，从而得不到全局最优解[12]。

为了发现复杂网络的重叠社团，在FCM算法的基础上，针对FCM算法需要预先确定聚类数的问题提出了熵有效性函数，提高了FCM算法的无监督性；对初始化敏感问题，将FCM算法初始化为随机初始化隶属度，改为采用度“最”大的节点作为初始中心点，降低了陷入局部最小值的概率。

1相关概念与算法

1.1熵有效性函数

熵的概念起源于热力学，用来衡量系统的无序程度。Shannon利用熵定义了一个离散型随机变量随机性大小的程度，称为信息熵[13]，如果一个随机变量的随机性越大，则用于表示该随机变量的信息量就越大，反之亦然。熵在信息论中表示信源的平均不定度[14]，用Pi表示信源取第个符号的概率，信源所含信息熵表示形式为

(1)

受文献[3]对社团结构的定性描述、文献[12]中为确定模糊聚类算法的“最佳”聚类数而提出的基于粒度原理的有效性函数以及信息熵[13-14]概念的启发，提出了基于信息熵的有效性函数，简称熵有效性函数，用于衡量FCM算法划分结果的有效性，并确定“最佳”聚类数。

熵有效性函数由两部分组成：社团内部熵和社团之间熵，简称社团内熵和社团间熵。由熵的概念可知，熵越小表明系统的无序程度越低，因此社团内熵越小表明社团内部联系越紧密，社团间熵越大表明社团之间联系越稀疏[13]。熵有效性函数定义为社团内熵与社团间熵差，且熵有效性函数值越小表明划分结果所得社团结构越明显。

熵有效性函数

(2)

式中，H(inc)表示社团内熵；H(betc)表示社团间熵。

在介绍社团内熵与社团间熵之前，先介绍一下节点度概率，节点度概率为节点度的值比最大节点度值，如式(3)所示，通过节点度概率可以表明节点的重要度，重要度大的节点随机性小，信息量小，与节点熵成正比关系。

(3)

式中，di表示节点i的度数；dmax表示网络中节点度数的最大值。

社团内熵的求解方式为各节点熵之和，根据熵的定义式(1)，结合节点度概率式(3)，得到社团内熵为

(4)

式中，N是网络总节点数；di是节点的度数；dmax是最大节点度数；PCm表示节点属于社团的概率，计算方法是社团m的节点数除网络总节点数。若节点i属于多个社团，则先求节点i属于各社团的概率，再求算术平均值。

社团间熵的求解方式与社团内熵一致，在求解社团间熵时，将社团抽象为节点，社团之间的连边抽象为节点之间的连边，由于在求解两两社团之间的连边时，每个社团被计算了两次，因此最后再除2。社团间熵为

(5)

式中，lij表示社团i与社团j之间的连边；lmax表示社团间连边数的最大值；Lin(i)表示社团中边数和。

1.2聚类数范围

(6)

式中，N是网络节点总数；dmax表示网络中节点度数最大值；dmin表示网络中节点度数最小值，若dmin小于2，令dmin为2。

1.3两个过滤条件

考虑到聚类数范围的最大聚类数和最小聚类数之间跨度较大，当聚类数较大时，所得社团中出现完全重叠的社团的慨率较大；当聚类数较小时，所得社团可能会出现社团之间存在较大重叠部分。因此针对以上两个问题，对每个划分结果，首先执行两个过滤条件：重叠社团数比例和边重叠率，再计算熵有效性函数值。两个过滤条件定义如下：

重叠社团数比例

(7)

边重叠率

(8)

1.4谱方法与FCM算法

通过谱变换[6]可将网络数据转换为特征空间中的数据，给定一个网络，可得该网络的邻接矩阵A=(aij)n×n和度矩阵D=(dii)，dii=∑kaik,利用广义特征系统Ax=tDx的前K个特征向量组成特征矩阵，特征矩阵的每一行对应于原网络相应各节点。再应用FCM算法对特征空间中的数据进行划分，可得到相应网络的社团划分结果。

FCM是模式识别中常用的方法，该方法由Dunn[15]开发于1973年，Bezdek[16]于1983年对其进行改进。张世华[7]首先将FCM算法应用于复杂网络的重叠社团发现。FCM算法的目标函数为

(9)

(10)

(11)

1.5算法描述与时间复杂度分析

给定网络的邻接矩阵A=(aij)n×n，设置参数最大迭代次数lmax=100,阈值error=0.001算法具体流程如下：

(1) 初始化和谱映射：

step1,计算度矩阵D=(dii)，其中dii=∑kaik,k=1,2,3,…,n；

step2，由广义特征系统Ax=tDx，得特征矩阵V=[e1,e2,…,en]；

step3，由聚类范围式(6)初始化最大聚类数Cmax和最小聚类数Cmin，根据度矩阵D，选择前最大Cmax个数据点作为初始中心点，构成初始中心点矩阵Center。

(2) FCM和熵有效性函数：

主循环执行c取值由Cmax递减到Cmin

step1，根据特征矩阵V，形成c对应的特征矩阵Ec=[e2,e3,…,ec]，并对Ec的行向量进行L2规范化；

step2，内循环l取值从1到lmax，根据式(10),式(11),式(9)更新隶属度矩阵U，中心点矩阵center和目标函数obj_fcn，直到obj_Fcn(l+1)-obj_Fcn(l)

step3，通过隶属度矩阵U获得聚类划分结果，对划分结果分别执行两个过滤条件式(7),式(8)，剔除无意义的结果；

step4，根据式(2),式(4),式(5)计算熵有效性函数值H(c)。

主循环结束

step5，熵有效性函数H(c)中最小值对应的c值，即为“最佳”聚类数best_c，对应的划分结果即为改进后算法的社团划分结果。

FCM算法中，每一次迭代过程中都要计算每一个数据点与所有类中心点的距离，然后计算隶属度矩阵U，因此，如果数据集维数为p，计算距离的时间复杂度就为O(p)，将有N个数据点的数据集聚类为c个类，总的时间复杂度就是O(pNc)[17]。而本文中的聚类数需要取到聚类范围的最大值N/dmin,因此算法的时间复杂度是O(pN(N/dmin))，时间复杂度与网络的最小节点度数成反比。

2实验结果分析

为了验证算法的有效性，将结合熵有效性函数的FCM算法应用于Zachary’skaratenetwork、Dolphinsocialnetwork和Americancollegefootballnetwork。实验结果表明熵有效性函数求得的“最佳”聚类数与实际社团数完全一致，且划分情况与实际社团结构基本一致。

2.1Zachary’karateclubnetwork

著名的zachary’skarateclubnetwork被广泛应用于复杂网络的社团结构发现[3]，它反映的是一所美国大学跆拳道俱乐部成员之间的社会关系。该数据集包括34个节点78条边，其中节点代表成员，边表示成员之间的社会关系。图1(a)是网络对应的社团内熵、社团间熵与熵有效性函数曲线，从图中可以看出熵有效性函数非零最小值对应的聚类数为2，与实际社团数一致，近一步观察可见，聚类数为2时，社团内熵与社团间熵的差值最大，且社团间熵的值为社团间熵曲线的峰值。过滤条件rateoverlop过滤掉了c值7,8,10,11,12,13,14,15,16 ,17. 网络结构如图1(b)所示，其中圆形和方形节点分别代表分裂后小俱乐部中各成员。图1(c)是本文算法的划分结果，从图中可看出只有节点3划分错误， 近一步观察可得节点3与两个社团的连边数都是5，划分正确率为33/34=97.1%。

图1　Zachary’s karate club network划分结果与熵有效性函数

2.2Dolphin social network

第二个数据是dolphin social network来自Newman个人网络数据网站http://www-personal.umich.edu/～mejn/netdata/，该数据集包含62个节点159条边。图2(a)是该网络的社团内熵、社团间熵与熵有效性函数曲线图，从图2中可以看出熵有效性函数非零最小值对应的聚类数是5, 重叠率rateoverlop过滤掉了c值8,9,10,11,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31。重叠社团比例numoverlap过滤掉了c值12,13,14,15. 网络实际社团结构如图2(a)所示，其中方形、圆形分别代表一个社团。图2(c)表示本文算法对网络的划分结果，社团编号从上到下从左到右依次为1,2,3,4,5。重叠节点为51,45,41,62,9,55,20,8。节点51是社团1,3,4的重叠节点，节点9是社团1,4的重叠节点，节点45,41,62是社团3,4的重叠节点，节点20,8是社团4,5的重叠节点，节点55是社团2,5的重叠节点。若不计重叠节点社团1,3,4与实际社团1完全一致，2和5为实际社团2完全一致，则节点划分正确率为100%。

图2　Dolphin social network划分结果与熵有效性函数

2.3American college football network

最后一个数据American college football network代表美国大学生橄榄球队比赛网络[11]。该数据集包含115个节点616条边，分别表示115个球队和616场比赛。图3(a)表示社团内熵、社团间熵与熵有效性函数，熵有效性函数的非零最小值对应的聚类数为 12，过滤条件numoverlap和rateoverlap分别过滤掉了c值13,14,15,16和9。网络社团结构如图3(b)所示，其中12个联盟用不同的形状和颜色深浅加以标注，联盟编号顺序从上到下再从左到右依次为1,2,3,…,12。图3(c)表示本文算法对网络的划分结果，7个社团1,5,6,7,8,9,11包含了图6(a)中对应联盟的所有节点。重叠节点依次为:6,13,43,81,83,113.节点29,59,60,64,81,83,91,98,111被错误划分, 可求得划分精确率为106/115=92.2%。

图3　American college football network划分结果与熵有效性函数

对比分析三个网络的聚类数范围式(4)与实际社团数，熵有效性函数求得的“最佳”聚类数和结合熵有效性函数的FCM算法对各网络节点划分正确率以及执行时间，对比情况见表1。

表1　三个网络聚类数范围与实际聚类数及个别实验参数的对比

从表1中可以看出根据式(4)得到的三个网络的聚类数范围，基本包含实际社团数，说明聚类数范围式(4)具有较高准确性，且基本能够满足计算需要。熵有效性函数求得的各网络“最佳”聚类数中只有Dolphin social network与实际社团数不一致，准确度比较高，结合熵有效性函数的FCM算法对三个网络划分结果的正确率都在90%以上，表明算法具有较高有效性。从时间列可以看出，算法不会因为网络规模的递增而增长，而是与网络内部节点度数的差值和社团结构本身有关。

为了衡量熵有效性函数的优越性，将熵有效性函数与模块度函数[18]相比较。模块度函数的定义式为

(12)

式中，eii表示社团i中包含的边数占网络总边数的比例；ai表示与社团i中边相连的边数占网络总边数的比例。

由于模块度函数只适用于非重叠社团，此处利用k-means算法[19]对两种评价函数进行比较，k-means算法的目标函数为

(13)

式中，xk表示第j个集合中的第k个数据点；mj表示第j个中心点；‖xk-mj‖2表示第j个集合中所有数据点到中心点mj的欧氏距离平方和。

综观图4三个网络在k-means算法下模块度函数和熵有效性函数对比，可知，模块度函数求的得三个网络的聚类数分别为4、5和11，熵有效性函数对三个网络的聚类数分别是2、5和12。熵有效性函数准确地找到了Zachary’s karate club network和American college football network的实际社团数，而模块度函数确定的聚类数与实际社团数均不相同。

图4　三个网络在k-means算法下模块度函数和熵有效性函数对比

对结合熵有效性函数的k-means算法和结合模块度函数的k-means算法的实验性能进行了对比分析，见表2。聚类数方面，熵有效性函数求的的聚类数与实际社团数相符程度较高；节点准确率方面，结合熵有效性函数的k-means算法在Zachary’s karate network社团划分中，错误划分节点为3，节点3与两个社团的连边数都为5；时间方面来看，熵有效性函数较占优势。

表2　k-means算法下两种函数的实验性能对比

注：表中Q表示模块度函数，H表示熵有效性函数。

3结语

传统的FCM算法需要预先指定聚类数，从而影响了算法的无监督性，且不恰当的聚类数会影响聚类结果。本文提出了结合熵有效性函数的FCM算法，避免了需要根据先验知识指定聚类数的问题，接着又给出了聚类数范围和两个过滤条件，提高了算法的执行效率。将结合熵有效性函数的FCM算法应用于三个经典网络的重叠社团检测，实验结果表明，熵有效性函数能够较准确地找到“最佳”聚类数，且算法社团结构划分的精确率都在90%以上，从而验证了算法的有效性和可行性。由于聚类范围依赖于节点度数，一定程度上影响了运行时间，有待近一步改进。但从k-means算法角度看，熵有效性函数在时间方面、聚类数方面和节点准确率方面较优于模块度函数，且熵有效性函数既适用于非重叠社团又适用于重叠社团。

参考文献

[1]骆志刚,丁凡,蒋晓舟,等.复杂网络社团发现算法研究新进展[J].国防科技大学学报, 2011, 33(1) : 47-52.

[2]贾宁宁,封 筠.复杂网络的社团结构发现[J].河北省科学院学报, 2013, 30(2) : 54-57.

[3]GIRVANM,NEWMANMEJ.Communitystructureinsocialandbiologicalnetworks[J].PNatlAcadSciUSA,2002,99(12) : 7812-7826.

[4]张燕平,王杨,赵姝.应用Normal矩阵谱平分法的多社团发现[J].计算机工程与应用, 2010,46(27) : 43-45.

[5]张聪, 沈惠璋.基于谱方法的复杂网络中社团结构的模块度[J].系统工程理论与实践, 2013,33(5) : 1231-1239.

[6]VERMAD,MEILA.Acomparisonofspectralclusteringalgorithms[R].Washington:UWCSE, 2003.

[7]NEWMANMEJ.FastAlgorithmforDetectingCommunityStructureinNetworks[J].PhysRevE, 2004,69(6):066133.

[8]刘大有,金弟,何东晓,等.复杂网络社团挖据综述[J].计算机研究与发展,2013,50(10) : 2140-2153.

[9]PALLAG,DERENYII,FARKASI,etal.Uncoveringtheoverlappingcommunitystructureofcomplexnetworksinnatureandsociety[J].Nature, 2005,435(7043) : 814-818.

[10]ADAMCSEK B, PALLA G, FARKAS I, et al. CFinder:locating clique and overlapping modules in biological networks[J]. BIOINFORMATICS APPLICATIONS NOTE, 2005,00(00) : 1-2.

[11]ZHANG S, WANG R, ZHANG X. Identification of overlapping community structure in complex networks using fuzzy c-means clustering[J].Physical A, 2007,374(1):483-490.

[12]陈东辉. 基于目标函数的模糊聚类算法关键技术研究[D].西安:西安电子科技大学计算机学院,2012.

[13]孙茜雅.基于最小熵聚类的社团检测算法[J].电子科技,2012,25(3):13-16.

[14]邓小龙,王柏,吴斌,等.基于信息熵的复杂网络社团划分建模和验证[J].计算机研究与发展,2012,49(4):725-734.

[15]DUNN J C A fuzzy relative of the ISODATA process and its use in detecting compact well-separated clusters[J]. Cybernet. 1973,3(3): 32-57.

[16]BEZDEK J C.Pattern recognition with fuzzy objective function algorithms[M]. New York：Plenum Press, 1981.

[17]吕晓云,李星毅,施化吉.基于约简数据集的FCM聚类算法[J].计算机工程与设计,2010,31(18):4062-4064.

[18]NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E.2004, 69:96-113.

[19]MACQUEE J B. Some Methods for classification and Analysis of Multivariate Observations[C]//Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability. Berkeley:University of California Press, 1967:281-297.

FCM Combined with Validity Measure Function of Entropy to Identity Community Structure

Jia Ningning，Feng Jun

(School of Information Science and Technology，Shijiazhuang Tiedao University，Shijiazhuang 050043，China)

Abstract:Mining and identifying community structure in complex networks is a fundamental issue in complex network research. In view of there are often overlapping communities in complex network, an improved Fuzzy c-means(FCM) method based on validity measure function of entropy is proposed. Firstly, devise a validity measure function of entropy, and use to determine the “best” clustering number of a network. Secondly, point out a range of clustering number and two filter conditions. Finally, combine them with FCM to detect communities in Zachary's karate club network, Dolphin social network and American college football network. In order to further demonstrate the superiority of validity measure function of entropy effectiveness, combine validity measure function of entropy and modularity function with k-means method, respectively, on the three networks. Experimental results show that the validity measure function of entropy could accurately find the actual clustering number, and the improved FCM method's accuracy of clustering is above 90%.

Key words:validity measure function of entropy；clustering number range；filter condition；fuzzy c-means；community structure

中图分类号：TP393

文献标志码：A

文章编号：2095-0373(2016)01-0103-08

作者简介：贾宁宁(1989-),女,河北邯郸人,硕士研究生,研究方向:复杂网络。E-mail:ning891221@163.com

基金项目:河北省自然科学基金项目(F2013210109)

收稿日期：2014-08-29责任编辑:刘宪福

DOI:10.13319/j.cnki.sjztddxxbzrb.2016.01.19

贾宁宁，封筠.结合熵有效性函数的FCM算法识别社团结构[J].石家庄铁道大学学报:自然科学版,2016,29(1):103-110.