基于聚类分析的复杂网络中的社团探测

2007年3月

复杂系统与复杂性科学　

COMPLEXSYSTEMSANDCOMPLEXITYSCIENCE

Vol.4No.1Mar.

2007

文章编号:1672-3813(2007)01-0028-08

基于聚类分析的复杂网络中的社团探测

刘　婷,胡宝清

(武汉大学数学与统计学院,武汉430072)

摘要:社团结构是复杂网络中普遍存在的一种特征。本文应用改进了的谱分法将

网络的社团探测问题转换为聚类分析问题,并将Girvan和Newman提出的模块度函数概念应用到聚类分析的4类算法中进行社团结构的探测,特别提出了一种新的结合模块度的聚类遗传算法。然后用3种类型的网络实验算例验证了本文算法的有效性,并对实验结果进行了比较分析,得出本文提出的新算法在初始化敏感性和准确性方面效果较好。最后指出本文算法的进一步研究方向。

关键词:社团结构;谱分法;模块度;k2means算法;模糊c均值;聚类遗传算法;聚类神经网络中图分类号:N94;TP393文献标识码:A

DetectingCommunityinComplexNetworksUsingClusterAnalysis

LIUTing,HUBao2qing

(SchoolofMathematics&Statistics,WuhanUniversity,Wuhan430072,China)

Abstract:Communitystructureisacommonpropertythatexistsincomplexnetworks.Improvedspectralpartitionisusedinthispaperinordertotransformthecommunitiesdetectingintoclusteranalysisprob2lem.Then,modularityfunctionisappliedtofourclusteralgorithmsforcommunitystructuredetecting.Especially,anewclustergeneticalgorithmcloselycombinedwithmodularityisproposed.Wedemon2stratetheavailabilityofouralgorithmsinthreedifferentkindsofnetworkdatum.Wealsomakethecom2parisonandanalysisoftheexperimentalresultsandobtainaconclusionthattheproposednewalgorithmpresentsfitnessininitializationsensitivityandveracity.Finally,somefurtherdirectionsarepointed.Keywords:communitystructure;spectralpartition;modularity;k2meansclustering;fuzzyc2means;clustergeneticalgorithm;clusterneuralnetwork

1　引言

复杂网络的概念已经被成功地应用到多个领域,如万维网、流行病网络、科学引文和合作网络,生态系统

[1-3]

网络等等。大量的大型复杂网络都呈现一种特性———社团结构,就是指:整个网络由若干个社团构成,

[1,4]

每个社团内部的节点之间的连接相对非常紧密,但是各个社团之间的连接相对来说却比较稀疏。在大型复杂网络中自动搜寻或发现社团,具有重要的实用价值。如社会网络中的社团代表根据兴趣或背景而形成的真实的社会团体,引文网络中的社团代表针对同一主题的相关论文。发现这些网络中的社区有助于我

收稿日期:2007-01-16

基金项目:教育部高等学校骨干教师资助计划(2002-)

作者简介:刘婷(1982-),女,湖北汉川人,在读硕士研究生,研究方向为智能计算与不确定信息处理。

第4卷第1期　　刘　婷,等:基于聚类分析的复杂网络中的社团探测・29・

们更加有效地理解网络结构和分析网络特性。

[1,5,6]

网络社团结构的研究发展到现在,有两类主要的方法———社会学中的分级聚类和计算机科学中的图形分割。分级聚类是探测网络社团的传统方法,是基于各个节点间连接的相似性或强度将网络划分成各

[7]

个子群,且根据划分时是往网络中添加还是移除边可分为凝聚算法和分裂算法两类,其中应用的非常广泛的分级聚类方法是由Girvan和Newman提出的基于边介数的分裂算法(简称GN算法);图形分割的最有

[3][8]

名的是Kemighan2Lin算法和谱平分法。其中Kernighan2Lin算法是根据使社团内部及社团间的边最优化的原则对原始的网络进行分类,谱平分法是根据网络图的Laplace矩阵进行向特征向量空间的谱映射。

[9,10]

本文的方法应用了谱平分法的一种改进算法,并将GN算法中提出的模块度函数与聚类分析算法结合进行社团结构的探测。

2　算法简介

网络中的社团发现与数据的聚类分析有很多相似之处,聚类分析是属于无监督的模式识别,其方法比社团发现更多样有效,因此把聚类分析应用到网络中就可以发现社团。应用聚类分析来探测网络的社团结构分为两个大的步骤:第一步是如何将原问题转化为聚类问题,即要把网络中节点间的联系在特征向量空间中表述出来,谱平分法正好可以实现这一转化,本文应用了传统谱平分法的一种改进算法———Capocci算[11]法;第二步是对转化后的数据进行聚类并将聚类结果还原为相应的社团结构,这一步是本文研究的重点所在,此前方法在这一步中只是单纯的解决聚类问题,本文提出了一种在聚类过程中结合了网络结构特征的聚类遗传算法,即用社团结构的模块度来控制进化过程,同时与常用的聚类方法进行了实验比较,显示出此方法的效果良好。这里为了紧密联系原始网络结构,采用GN的模块度函数作为聚类效能的度量标准。本文实践了4类有效且应用得比较广泛的聚类分析算法,包括k2means算法(KM)、改进了的fcm算法(简称

[12]

IFCM)、聚类神经网络(CNN),以及聚类遗传算法(CG)。这里的CG算法按选取的适应度函数分为两种,适应度函数设为聚类分析中的目标函数时简称OCG算法,设为模块度函数时就是本文提出的新算法简称MCG算法。

2.1　Capocci算法

传统谱平分法

[13-15]

基于Laplace矩阵L=D-W,其中D为网络的度矩阵,W=(wij)为网络的连接权矩

[16]

阵,wij表示连接节点i和j的边的权值。谱平分法的理论可以证明,L的特征值中不为零的特征值所对应的特征向量的各元素中,同一个社团内的节点对应的元素是近似相等的,当网络很明显地分成两个社团时此算法快速有效,否则就未必有效。因此其缺点是每次只能将网络平分。

为了探测任意社团数的网络社团结构,Capocci等人在求取矩阵特征向量问题上提出将它转化为优化问

-1[8,11]

(这里称为Capocci算法)。引入最优化的题来求解,由此提出了基于标准矩阵N=DW的谱平分算法

n12

(xi-xj)wij,其中n为网络节点数,xi表示为各个节点定义的一个变量,而且向量x满目标函数z(x)=62i,j=1足约束条件

i,j=1

6

n

xixjmij=1,其中mij是一个已知对称矩阵M的元素。函数z对所有满足约束条件的x的驻点为

(D-W)x=μMx,其中D=(dij),dij=δij

-1

k=1

6

n

μ)x,wik,μ是一个拉格朗日系数。当M=D时,DWx=(1-2

-1

这对应于标准矩阵N=DW;而当M=I时,有(D-W)x=μx,这对应于Laplace矩阵L=D-W。Capocci

等人证明了对于一个社团结构比较明显的网络,假设社团数目为k,则矩阵N的前k-1个第一非平凡特征值

[11]

所对应的特征向量中,同一个社团内的节点相应的元素非常接近。因此,可以用这k-1个特征向量作为聚类的数据,进行聚类分析后再转化为对应的节点就可以得到相应的社团了。此算法的应用在很多实践中得

[17]

到了很好的效果,由此本文方法中第一步采用Capocci算法进行数据转化。2.2　模块度函数的应用

有很多发现社团的算法都是在给定社团数的情况下进行社团的探测,但在不知道社团数目的情况下就

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学・30・2007年3月

无法评论得出的社团结构是否有效准———模块度

[1,9,19]

[18]

。为了解决这个问题,Newman等人引进了一个衡量网络划分质量的标

。对于具有n个节点的无向网络G(V,E,W),其中V为节点集,E为边集,W=(wij)n×n为

权矩阵。对此网络得出的某个k社团划分Pk,其对应的模块度定义为

M(Pk)=

)=其中,A(V′,V″

c=1

6

k

A(Vc,Vc)

-A(V,V)

A(Vc,V)A(V,V)2(1)

i∈V′,j∈V″

6

wij。这样,A(Vc,Vc)表示在社团c中所有边的权重和,A(Vc,V)表示所有与社团c中

的节点有连线的边的权重和,A(V,V)表示整个网络中边的权重和。基于这样的定义,当网络的k社团结构越明显,则M(Pk)值越大,可以用M(Pk)作为衡量得出的社团结构有效度的标准。

在本文中,模块度不仅衡量得出的社团结构有效度,而且应用到其中一些聚类算法中作为优化迭代的一个指标值。模块度是以不同的方式与这4类聚类算法结合的,在KM、CNN、OCG算法中,模块度仅作为在得出的社团结构中搜寻最佳社团数的依据;在IFCM算法中,模块度的作用不仅表现在搜寻最佳社团数,且在设定聚类数下与目标函数值结合作为迭代的终止条件;特别是在本文提出的MCG算法中,模块度在作为搜寻最佳社团数依据的同时,更重要的是作为遗传算法中最为关键的适应度函数来控制算法的进化过程。2.3　基于聚类分析的社团探测算法流程[9]

对于某复杂网络G(V,E,W),给定一个社团数目的最大值kmax和最小值kmin(最大值一般设为节点数的1/3,最小值一般设为2,也可根据实际经验来取得),进行以下步骤:

1)由连接权矩阵W得出网络的度矩阵D=(di)n×n,其中D为对角矩阵,di为第i个节点的度,n为节

点数。注意,这里考虑的均为无向网络。

2)对满足kmin≤k≤kmax的k,用Capocci方法将寻找k社团问题转化为数据的k聚类问题。具体就是计

-1n×1

算N=DW的前k-1个非平凡特征向量e1,e2,…,ek-1(ei∈R,i=1,…,k-1)组成矩阵E。由E的行向

量x1,…,xn(xi∈R)得到n个的数据向量形式的待聚类样本。

3)用聚类分析方法对上面得到的数据进行k聚类,这里分别可以用KM、IFCM、CNN、CG来聚类。本文中的聚类算法均采用Matlab语言编译。其中,KM算法是常用的聚类算法,它是基于距离聚类中心最近法则为标准对个体进行分类;FCM是一种基于对目标函数优化的模糊聚类方法。这里的IFCM是对FCM的改进之处在于将由FCM算法得到的模糊隶属度矩阵转化为硬聚类隶属度矩阵(这里不同于ZhangShihua等人在文献[17]中所用的在模糊隶属度矩阵中设定阈值找到有重叠部分的社团的方法,而是通过搜索个体对于各个社团的最大隶属度得到独立社团结构),而且针对此处聚类的最终目的是探测最高模块度的社团结构,将FCM算法中的目标函数值与模块度函数值的倒数之和作为算法的终止条件,以此来控制优化过程。此处的CNN算法可进行无监督学习的分类,因此适用于此处的社团发现

[6,12]

[20]

[20,21]

1×k

采用竞争型神经

网络模型,这种网络模型模拟生物神经网络中神经元之间的兴奋、抑止与竞争机制进行网络的学习与训练,

。

本文中提出的CG算法是对聚类中心进行进化迭代,其算法流程图见图1,算法要点如下:

()

(1)随机初始化代表聚类中心的种群P0,这里设种群的规模为m,再采用二进制对m个个体进行编码,组成基因琏。

(2)在进化过程的每一代中,最关键的是计算种群中各个体的适应度f。这里的OCG算法是传统基于

目标函数的聚类遗传算法

[10]

,即对目标函数f进行优化迭代,此处目标函数见流程图中公式(3);在MCG算

法中,由于适应度值函数选取为模块度函数,因此是对相应的模块度函数进行优化迭代,每进化一代时都需要首先将种群中个体解码为聚类中心,然后将根据聚类中心得出的聚类还原为相应的社团结构,最后计算其模块度值作为适应度值。

(3)根据适应度对种群中的个体进行交叉变异,逐步淘汰适应度低的个体得出全局最佳聚类中心。特别在MCG算法中是要得到对应模块度最高的聚类中心,这与我们想得到模块度最高的社团结构的目的是一

第4卷第1期　　刘　婷,等:基于聚类分析的复杂网络中的社团探测・31・

致的,而且这样直接用模块度值来控制进化过程可以有效减小将网络转化为特征向量时数据的失真。

(4)本文中CG算法的终止条件为e=fmax-fmin<ε。

4)寻找模块度函数值最大的聚类数k,根据聚类结果还原为对应的社团结构。

图1　CG算法(包括OCG和MCG算法)流程图

3　实验结果

在本文中只给出了3个不同的实验例子,分别为计算机生成的有社团结构的复杂网络、2000年美国大学美式足球赛网络和《红楼梦》家族关系网络,并用本文提出的算法获得了较好的社团分类。3.1　计算机生成的有社团结构的复杂网络

为了验证本文方法的有效性,我们根据网络社团结构的定义编写了一个Matlab程序生成具有社团结构的复杂网络,并用参数控制此网络社团结构的明显程度,同时这个明显程度用模块度来衡量。这里给出2个不同模块度值网络的实验算例。

第一个算例为一个100节点的网络,具有5个大小分别为10,15,20,25,30的社团,模块度为016060,记为网络(a)。具体试验结果见表1,注意表中的次数为得到最优解的平均运行次数,时间为预设社团数下Step2和Step3所用近似时间,准确率为对比预设社团结构的准确率(下同)。

另一个是社团结构不太明显的算例,预设一个90节点的网络,具有4个大小分别为15,20,25,30的社团,模块度为014108,实验对比结果见表2。

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学・32・

表1　网络(a)(模块度为0.6060)实验结果

次数

KMIFCMCNN

823

OCGMCG

11

2007年3月

时间

2seconds3seconds20seconds7minutes3minutes

准确率

100%99%100%100%100%

模块度

0.60600.59460.60600.60600.6060

　　CG

表2　网络(b)(模块度为0.4108)实验结果

次数

KMIFCMCNN

1233OCGMCG

11

时间

2seconds3seconds25seconds10minutes4minutes

准确率

95.6%96.7%100.0%96.7%100.0%

模块度0.35030.38890.41080.38890.4108

　　CG3.2　2000年美国大学美式足球赛网络

这个实际网络是由Girvan和Newman观察得到的,网络图见图2。网络中的点代表了不同的足球队,连边则表示端点所代表的两队进行过常规赛。这些球队结成了一个具有社团结构的网络,它们被分为12个联盟会,联盟会内的球队进行比赛的概率比不同联盟会的球队大。Girvan&Newman用基于边介数的分裂算

[19]

法(GN算法)对此网络进行了社团结构的探寻。表3是用结合了模块度函数的聚类分析算法得到的实验结果。

图2　2000年美国大学美式足球赛网络图

表3　2000年美国大学美式足球赛网络社团发现实验对比结果

次数

KMIFCMCNNMCG

312041

时间

4seconds6seconds40seconds7minutes

准确率

85.2%82.6%91.3%86.1%

模块度

0.48950.43790.48690.4683

第4卷第1期　　刘　婷,等:基于聚类分析的复杂网络中的社团探测・33・

　　图中用115个点表示115个美国大学足球队,连线表示两队进行过常规赛。可以看到,除了点36,42,

80,82和90所表示的球队社团结构不够明显以外,其他的11个社团可明显看出,社团内连线都较社团间连线密集。3.3　《红楼梦》家族关系网络社会网络大部分都具有社团结构,根据不同的属性可以分为不同性质的社团,这里我们从大家都熟悉的名著《红楼梦》中选取主要人物以家族关系为依据生成了一个社会网络。

网络中的点代表小说中的人物(本例中只给出主要人物点67个),连线表示亲属关系(这里只考虑诸如父母、姐妹兄弟、夫妻等主要亲属关系),并根据亲属关系的亲近程度设定关系权重。这里我们给出基于MCG算法得到的社团结构图,见图3(得出5个家族社团包括宁国府、荣国府、王府、贾府和薛府,分别用不同颜色的矩形框表示)。

[19]

图3　基于MCG算法得到的社团结构图

可以从图3看到,基于MCG算法得出的结果比较准确,只有几个点的归属有异议,例如王夫人属于荣国府和王府都是合理。因为这些人物可能与多个家族的关系都非常密切,这在社会网络中是常见的。为了解决这种矛盾,这里应用ZhangShihua在参考文献[17]中所提出的探测模糊社团结构的方法,用基于IFCM算法得出了如图4所示模糊社团结构图

[22]

。

黑框内为社团网络图,连线表示社团间的重叠部分

图4　基于IFCM算法得到的模糊社团结构图

　　　　　　　　　　　　　　　　　　　　复杂系统与复杂性科学・34・2007年3月

4　分析比较的结论

我们主要从初始化敏感度、准确率和运算耗时3个方面来比较和分析这些算法。通过对前面3种不同类型的网络进行基于聚类分析的社团探测,实验结果反映出:KM算法具有快速易行的优点,但对社团结构不是很明显的网络其探测效果不稳定,对初始化最为敏感;IFCM算法也具有简单易行的特点,探测小社团数目的网络社团准确率较高且能扩展到模糊社团探测,但是由于本质上是一种局部搜索算法,容易陷入局部最优解,因此同样对于初始化比较敏感,且不适用于社团数目较大的网络;CNN虽然对于初始化和运算速度都较为适中,但对数据的预处理和训练步长都需要经过反复调试以达到最佳效果。

特别的,CG算法是一种基于自然选择和群体遗传机理的搜索算法,在每一代同时搜索参数空间的不同区域,然后把注意力集中到解空间期望值最高的部分,从而使找到全局最优解的可能性大大增加,因此对初始化不敏感,而且无需建模和复杂的运算。实验结果同样表明CG算法对初始化最不敏感,这样使得CG算法的可靠性比其他3种算法要好,尤其是本文提出的结合了模块度的MCG算法,不仅保持了对初始化不敏感的优点,而且直接用模块度控制进化过程保证了较高的准确率,同时相比传统聚类遗传算法OCG算法,在收敛速度上有很大的提高,耗时也比OCG少。图5　对网络(a)使用OCG与MCG算法的进化过程中e=fmax-fmin变化曲线对比图

这里给出对网络(a)使用OCG与MCG算法的进化过程中e=fmax-fmin变化曲线对比图,见图5,从图中可明显看出用模块度作为适应度时收敛速度比用目标函数作为适应度时快。虽然MCG相比OCG在耗时上有很大提高,但与前面3类算法相比仍然比较耗时,需要在运行速度上做更多的改进,例如引入并行算法提高运算速度或改进交叉变异机制以提高收敛速度来进行大型网络的社团探测。因此需根据不同的网络规模和特征进行算法的选择。

5　结语

本文的创新之处在于3个方面:1)提出了在聚类过程中结合模块度函数的MCG算法,不仅保持了遗传算法的优点,而且直接用模块度控制遗传聚类算法的进化过程保证了算法的准确性,有效减小将网络转化到

特征向量空间时数据的失真,同时用此方法成功地探测了本文给出的3类网络的社团结构;2)用常见的4种不同类型的聚类算法同时进行了实验对比,而且把本文提出的结合模块度的聚类遗传算法与传统聚类遗传算法进行了比较,并对实验结果给出了分析总结;3)采用了3种典型网络实验,特别是《红楼梦》家族关系网络的提出,用MCG算法得到了非常合理的社团结构,并用FCM算法成功进行了模糊社团结构的探测。从比较和分析中得到一些启示,可以将各种算法的优势加以结合开发出一种在初始化敏感度、准确率和运算耗时

第4卷第1期　　刘　婷,等:基于聚类分析的复杂网络中的社团探测・35・

3方面都能表现良好的算法,并扩展到探测模糊社团,这都是今后要进一步深入研究的方向。

参考文献:

[1]NewmanMEJ,GirvanM.Findingandevaluatingcommunitystructureinnetworks[J].PhysRevE,2004,69(2):026113.[2]HolmeP,HussM,JeongH.Subnetworkhierarchiesofbiochemicalpathways[J].Bioinformatics,2003,19(4):532-538.[3]汪小帆,李翔,陈关荣.复杂网络理论及其应用[M].北京.清华大学出版社,2006.162-198.

[4]DuchJ,ArenasA.Communitydetectionincomplexnetworksusingextremeoptimization[J].PhysRevE,2005,72:027104.[5]ClausetA,NewmanMEJ,MooreC.Findingcommunitystructureinverylargenetworks[J].PhysRevE,2004,70(6):

066111.

[6]BezdekJC,BoggavarapuS,HallLO,etal.Geneticalgorithmguidedclustering[J].FUZZ2IEEE’94,1994:34-39.[7]NewmanMEJ.Fastalgorithmfordetectingcommunitystructureinnetworks[J].PhysRevE,2004,69(6):066133.[8]PothenA,SimonH,LiouK2P.Partitioningsparsematriceswitheigenvectorsofgraphs[J].SIAMJMatrixAnalAppl,1990,

11(3):430-452.

[9]WhiteS,SmythP.Aspectralclusteringapproachtofindingcommunitiesingraphs[C].NewportBeach,USA:SIAMInterna2

tionalConferenceonDataMining,2005.

[10]DonettiL,MunozMA.Detectingnetworkcommunities:anewsystematicandefficientalgorithm[J].JStatMech,2004,10:

10012.

[11]CapocciA,ServedioVDP,CaldarelliG,ColaioriF.Detectingcommunitiesinlargenetworks[J].PhysicaA,2005,352(2-4):669-676.

[12]高新波.模糊聚类分析及其应用[M].西安:西安电子科技大学出版社,2004.49-92.

[13]MoharB.TheLaplacianSpectrumofGraphs[A].AlviaY,ChartrandG,OllermannOR,etal.GraphTheory,Combinatorics,

andApplications[C].NewYork:Wiley,1991.871-898.

[14]XingEP,NgAY,JordanMI,RussellS.Distancemetriclearning,withapplicationtoclusteringwithside2information[J].

AdvancesinNeuralInformationProcessingSystems,2003,15:505-512.

[15]HighamDJ,KalnaaG,MillaK.Spectralclusteringanditsuseinbioinformatics[J].JournalofComputationalandApplied

Mathematics,2007,204:25-27.

[16]NgAY,JordanMI,WeissY.Onspectralclustering:analysisandanalgorithm[R].Berkeley:UniversityofCalifornia,

2006.

[17]ZhangSH,WangRS,ZhangXS.Identificationofoverlappingcommunitystructureincomplexnetworksusingfuzzycmeans

clustering[J].PhysicaA:StatisticalMechanicsanditsApplications,2007,374(1):483-490.[18]MuffS,RaoF,CflischA.Validationofnetworkclusterizations[J].arXiv:cond2mat,2005:0503252.

[19]GirvanM,NewmanMEJ.Communitystructureinsocialandbiologicalnetworks[J].ProcNatlAcadSci,2001,99(12):

7821-7826.

[20]周开利,康耀红.神经网络模型及其MATLAB仿真程序设计[M].北京:清华大学出版社,2005.111-128.

[21]BezdekJC.Areviewofprobabilistic,fuzzy,andneuralmodelsforpatternrecognition[J].JIntellFuzzySyst,1993,1(1):

1-25.

[22]PallaG,DerenyiI,FarkasI,etal.Uncoveringtheoverlappingcommunitystructureofcomplexnetworksinnatureandsociety

[J].Nature,2005,435(7043):814-818.