电子学报 ›› 2014, Vol. 42 ›› Issue (4): 723-729.DOI: 10.3969/j.issn.0372-2112.2014.04.016

• 学术论文 • 上一篇    下一篇

基于贪婪优化技术的网络社区发现算法研究

冷作福   

  1. 烟台市电化教育馆, 山东烟台 264003
  • 收稿日期:2013-09-06 修回日期:2013-11-14 出版日期:2014-04-25 发布日期:2014-04-25
  • 作者简介:冷作福 男,1962年生于山东烟台,山东师范大学本科,现任烟台市教学仪器站(电化教育馆)站长(馆长),主要从事基于网络的电化教学研究. E-mail:Lengzuofu163@163.com

Community Detection in Complex Networks Based on Greedy Optimization

LENG Zuo-fu   

  1. Yantai Center for Educational Technology, Yantai, Shandong 264003, China
  • Received:2013-09-06 Revised:2013-11-14 Online:2014-04-25 Published:2014-04-25

摘要: 社区发现问题是复杂网络研究的热点问题.基于优化模块度Q函数的方法例如CNM,BGLL等是一类经典的应用广泛的网络社区发现方法.但是已有研究发现,该类方法存在分辨率的问题,即当大规模网络中存在较小社区的情况下这类方法的效果不佳.近来,针对Q函数存在的问题,有研究者证明了另一个有效的目标函数surprise不存在分辨率的问题.但是目前没有直接优化该函数的有效算法,因此,提出一种基于贪婪思想的局部优化surprise函数的社区发现算法,该方法同样不存在分辨率的问题,而且算法不需要指定社区的个数.实验结果表明该方法鲁棒性好,精度优于其它经典的方法例如CNM,BGLL和LPA.

关键词: 复杂网络, 社区发现, 模块度函数, surprise

Abstract: In social network,the important and crucial problem is community detection.Classical modularity function optimization approaches such as CNM and BGLL are widely used methods for identifying communities which are quite efficient.As we have known,modularity function (Q) suffers from its resolution limit.Recently,surprise function(S) was proposed and experimentally proved to be better than Q function.However,up to now,there is not any method which is based on direct surprise maximization.In this paper,an efficient community detection algorithm which is based on greedy surprise optimization is proposed and does not suffer from a resolution limit.The new method does not need community number K.Test results on experimental networks show that our method is robust,not sensitive to noises and has better performances.

Key words: complex network, community structure, modularity function, surprise

中图分类号: