网络重叠社区发现的谱聚类集成算法  

Spectral clustering ensemble algorithm for discovering overlapping communities in social networks

作　　者：黄发良[1] 黄名选[2] 元昌安 姚志强[1] 

机构地区：[1]福建师范大学软件学院,福州350007 [2]广西教育学院科研处,南宁530023 [3]科学计算与智能信息处理广西高校重点实验室,南宁530023

出　　处：《控制与决策》2014年第4期713-718,共6页Control and Decision

基　　金：国家自然科学基金项目(61262028);教育部人文社会科学研究青年基金项目(12YJCZH074);福建省自然科学基金项目(2011J01339);广西自然科学基金项目(2012GXNSFAA053235);科学计算与智能信息处理广西高校重点实验室开放基金项目(GXSCIIP201212);福建师范大学优秀青年骨干教师培养基金项目(fjsdjk2012082);福建省教育厅科技项目(JA13077)

摘　　要：鉴于计算代价高昂的谱聚类无法满足海量网络社区发现的需求,提出一种用于网络重叠社区发现的谱聚类集成算法(SCEA).首先,利用高效的近似谱聚类(KASP)算法生成个体聚类集合;然后,引入个体聚类选择机制对个体聚类进行优选,并对优选后的个体聚类建立簇相似图;最后,进行层次软聚类,得到网络节点的软划分.实验结果表明,与代表性算法(CPM,Link,COPRA,SSDE)相比较,SCEA能够挖掘出具有更高规范化互信息(NMI)的网络重叠社区结构,且具有相对较好的鲁棒性.Considering that spectral clustering algorithms are unable to efficiently discover communities in massive networks for the high computation cost, a spectral clustering ensemble algorithm（SCEA） is proposed. Firstly, the effective KASP algorithm is used to produce clusters. Then the better clusters are chosen to construct a cluster ensemble, and the similarity graph for individual cluster is created. Finally, the resultant overlapping communities with hierarchical soft clustering are obtained. Experimental results show that, in contrast with some typical algorithms such as clique percolation method（CPM）, Link, community overlap propagation algorithm（COPRA） and sampled spectral distance embedding（SSDE）, the SCEA can discover the network communities with higher normal mutual information（NMI）, and it exhibits satisfactory robustness.

关 键 词：重叠社区发现 谱聚类 集成聚类 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]