计算机应用 ›› 2014, Vol. 34 ›› Issue (10): 2812-2815.DOI: 10.11772/j.issn.1001-9081.2014.10.2812

• 先进计算 • 上一篇    下一篇

基于聚类粒化的社团发现算法

赵姝1,2,柯望1,2,陈洁1,2,张燕平1,2   

  1. 1. 安徽大学 计算机科学与技术学院，合肥 230601
    2. 智能计算与信号处理教育部重点实验室（安徽大学），合肥 230601
  • 收稿日期:2014-06-26 修回日期:2014-07-01 发布日期:2014-10-30 出版日期:2014-10-01
  • 通讯作者: 赵姝
  • 作者简介:赵姝（1979-），女，安徽巢湖人，副教授，博士，CCF会员，主要研究方向：智能计算；
    柯望（1991-），女，安徽凤阳人，硕士研究生，主要研究方向：智能计算；
    陈洁（1982-），女，安徽巢湖人，讲师，博士，主要研究方向：智能计算；
    张燕平（1962-），女，安徽巢湖人，教授，博士，主要研究方向：智能计算。
  • 基金资助:

    国家自然科学基金资助项目;安徽省高等学校省级自然科学研究项目

Community detection algorithm based on clustering granulation

ZHAO Shu1,2,Wang KE1,2,CHEN Jie1,2,ZHANG Yanping1,2   

  1. 1. Key Laboratory of Intelligent Computing and Signal Processing of Ministry of Education (Anhui University), Hefei Anhui 230601, China
    2. School of Computer Science and Technology, Anhui University, Hefei Anhui 230601, China;
  • Received:2014-06-26 Revised:2014-07-01 Online:2014-10-30 Published:2014-10-01
  • Contact: ZHAO Shu

PDF

摘要：

为了实现复杂网络社团发现算法的复杂度和精确度间的均衡，提出一种基于聚类粒化的社团发现算法(CGCDA)，将网络粒化获得的粒子视为一个社团，粒化结果即为对网络的社团划分。首先，将网络中的每个节点视为基本粒，通过初始粒化操作实现对网络的粒化；然后，针对获得的粒化集合中满足粒化系数的粒子进行聚类粒化操作，分层粒化直到不存在满足要求的粒子对；最后，将粒子对中的重叠节点视为孤立点，用邻居节点投票法把孤立节点归并到相应的粒子中，实现对复杂网络的社团划分。实验实现了Newman快速算法（NFA）、标号传播算法（LPA）和CGCDA。实验结果表明，CGCDA在四个基准数据集上可获得平均高于LPA 7.6%的模块度和低于NFA 96%的时间。CGCDA时间复杂度较低，获取的社团模块度较高，实现了社团发现时间和精确度的均衡，相比NFA、LPA总体性能更优。

Abstract:

To keep the trade-off of time complexity and accuracy of community detection in complex networks, Community Detection Algorithm based on Clustering Granulation (CGCDA) was proposed in this paper. The granules were regarded as communities so that the granulation for a network was actually the community partition of a network. Firstly, each node in the network was regarded as an original granule, then the granule set was obtained by the initial granulation operation. Secondly, granules in this set which satisfied granulation coefficient were merged by clustering granulation operation. The process was finished until granulation coefficient was not satisfied in the granule set. Finally, overlapping nodes among some granules were regard as isolated points, and they were merged into corresponding granules based on neighbor nodes voting algorithm to realize the community partition of complex network. Newman Fast Algorithm (NFA), Label Propagation Algorithm (LPA), CGCDA were realized on four benchmark datasets. The experimental results show that CGCDA can achieve modularity 7.6% higher than LPA and time 96% less than NFA averagely. CGCDA has lower time complexity and higher modularity. The balance between time complexity and accuracy of community detection is achieved. Compared with NFA and LPA, the whole performance of CGCDA is better.

中图分类号: 

版权所有 © 2021 四川计算机应用杂志社有限公司
蜀ICP备 05010208 号-3　新出网证(川)字026号
技术支持：北京玛格泰克科技发展有限公司
访问总数：
今日访问：