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

doi:10.11772/j.issn.1001-9081.2014.10.2812

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

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

赵姝¹,²,柯望¹,²,陈洁¹,²,张燕平¹,²

1. 安徽大学计算机科学与技术学院，合肥 230601
2. 智能计算与信号处理教育部重点实验室（安徽大学），合肥 230601

收稿日期:2014-06-26 修回日期:2014-07-01 出版日期:2014-10-01 发布日期:2014-10-30
通讯作者: 赵姝
作者简介:赵姝（1979-），女，安徽巢湖人，副教授，博士，CCF会员，主要研究方向：智能计算；
柯望（1991-），女，安徽凤阳人，硕士研究生，主要研究方向：智能计算；
陈洁（1982-），女，安徽巢湖人，讲师，博士，主要研究方向：智能计算；
张燕平（1962-），女，安徽巢湖人，教授，博士，主要研究方向：智能计算。
基金资助:
国家自然科学基金资助项目;安徽省高等学校省级自然科学研究项目

Community detection algorithm based on clustering granulation

ZHAO Shu¹,²,Wang KE¹,²,CHEN Jie¹,²,ZHANG Yanping¹,²

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-01 Published:2014-10-30
Contact: ZHAO Shu

摘要/Abstract

摘要：

为了实现复杂网络社团发现算法的复杂度和精确度间的均衡，提出一种基于聚类粒化的社团发现算法(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.

中图分类号:

TP301

赵姝柯望陈洁张燕平. 基于聚类粒化的社团发现算法[J]. 计算机应用, 2014, 34(10): 2812-2815.

ZHAO Shu Wang KE CHEN Jie ZHANG Yanping. Community detection algorithm based on clustering granulation[J]. Journal of Computer Applications, 2014, 34(10): 2812-2815.

参考文献

［1］KERIGHAN B W, LIN S. An efficient heuristic procedure for portioning graphs ［J］. System Technical Journal, 1970,49:291-307.
［2］KLEINBERG J. Authoritative sources in a hyperlinked environment ［J］. Journal of the ACM, 1999,46(5):604-632.［3］GIRVAN M, NEWMAN M E J. Community structure in social and biological networks ［J］. Proceedings of the National Academy of Sciences of the United States of America, 2001,99(12):9821-7826.
［4］NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks ［EB/OL］. ［2014-02-03］. http://www.docin.com/p-220115056.html.
［5］NEWMAN M E J. Fast algorithm for detecting community structure in networks ［EB/OL］. ［2014-02-05］. http://www.docin.com/p-385453348.html.
［6］CLAUSET A, NEWMAN M E J, MOORE C. Finding community structure in very large networks ［EB/OL］. ［2014-02-05］. http://www.docin.com/p-87574994.html.
［7］RAGHAVAN U N, ALBERT R, KUMARA S. Near linear time algorithm to detect community structures in large-scale networks ［J］. Physical Review E, 2007,76(3):1-12.
［8］MIAO D, WANG G, LIU Q. Granular computing: past, present and future ［M］. Beijing: Science Press, 2007:46-48.(苗夺谦,王国胤,刘清.粒计算:过去、现在与展望［M］.北京:科学出版社,2007:46-48.)
［9］WANG G, ZHANG Q, HU J. Granular computing review ［J］. Journal of Intelligent Systems, 2007,6(2):8-25.(王国胤,张清华,胡军.粒计算综述［J］.智能系统学报, 2007,6(2):8-25.)
［10］MIAO D, FAN S. The calculation of knowledge granulation and its application ［J］. Journal of Systems Science and Information, 2002,22(1):48-56.(苗夺谦,范世栋.知识的粒度计算及其应用［J］.系统工程理论与实践,2002,22(1):48-56.)
［11］HANSEN P, JAUMARD B. Cluster analysis and mathematical programming ［J］. Mathematical Programming, 1997,79(1/2/3):191-215.
［12］KAUFMAN L, ROUSSEEUW P J. Agglomerative nesting (program AGNES) in finding groups in data: an introduction to cluster analysis ［M］. Hoboken: Wiley Interscience, 2005:3.
［13］DAI M, WU Z, SHAO S, et al.GSM mobile communication network optimization ［M］. Beijing: Posts and Telecom Press, 2003:4.(戴美泰,吴志忠,邵世祥，等.GSM移动通信网络优化［M］.北京:人民邮电出版社,2003:4.)
［14］HARTE L, BROMLEY B, DAVID M. Introduction to GSM: physical channels, logical channels, network functions, and operation ［M］. Fuquay Varina: Althos Publishing, 2008.
［15］WANG B, LU X, CHEN J, et al.Solving frequent points allocation of GSM using EGA ［J］. Computer Technology and Development, 2013,23(2):24-27.(王博岩,卢肖,陈洁，等.基于精英遗传算法的 GSM 网络频点优化设计［J］.计算机技术与发展,2013,23(2):24-27.)

[1]	肖智豪胡志华朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 0, (): 0-0.
[2]	赖自成, 张玉萍, 马燕. 基于门控图卷积神经网络的有机化学反应预测[J]. 计算机应用, 2021, 41(10): 3070-3074.
[3]	沙林秀，聂凡，高倩，孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 计算机应用, 0, (): 0-0.
[4]	董永峰孙跃华高立超韩鹏季海鹏. 基于改进一维卷积和双向长短期记忆神经网络的故障诊断方法[J]. 计算机应用, 0, (): 0-0.
[5]	李大海刘庆腾艾志刚王振东. 基于动态D向分割和混沌扰动的阴阳对算法[J]. 计算机应用, 0, (): 0-0.
[6]	雷鹰郑万波魏嵬夏云霓李晓波刘诚武谢洪. 基于概率性能感知演化博弈策略的混合“云+边”环境中任务卸载方法 [J]. 计算机应用, 0, (): 0-0.
[7]	乔钢柱王瑞孙超利. 基于分解的高维多目标改进进化算法[J]. 计算机应用, 0, (): 0-0.
[8]	朱诚潘旭华张勇. 基于趋化校正的哈里斯鹰优化算法[J]. 计算机应用, 0, (): 0-0.
[9]	陈俊, 何庆. 基于余弦相似度的改进蝴蝶优化算法[J]. 计算机应用, 2021, 41(9): 2668-2677.
[10]	平凡汤小春潘彦宇李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 计算机应用, 0, (): 0-0.
[11]	杨杰张名扬芮晓彬王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 0, (): 0-0.
[12]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[13]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[14]	党伟超, 李涛, 白尚旺, 高改梅, 刘春霞. 基于自注意力长短期记忆网络的Web软件系统实时剩余寿命预测方法[J]. 计算机应用, 2021, 41(8): 2346-2351.
[15]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.

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

Community detection algorithm based on clustering granulation

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics