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

doi:10.3969/j.issn.0372-2112.2014.04.016

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

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

冷作福

烟台市电化教育馆, 山东烟台 264003

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

Community Detection in Complex Networks Based on Greedy Optimization

LENG Zuo-fu

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

摘要/Abstract

摘要： 社区发现问题是复杂网络研究的热点问题.基于优化模块度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

中图分类号:

N94
TP393

冷作福. 基于贪婪优化技术的网络社区发现算法研究[J]. 电子学报, 2014, 42(4): 723-729.

LENG Zuo-fu . Community Detection in Complex Networks Based on Greedy Optimization[J]. Acta Electronica Sinica, 2014, 42(4): 723-729.

参考文献

[1] Watts D J,Strogatz S H.Collective dynamics of “small-world” networks[J].Nature,1998,393(6):440-442.

[2] Barabdsi A L,Bonabeau E.Scale-free networks[J].Scientific American,2003,288(5):60-69.

[3] Girvan M,Newman M E J.Community structure in social and biological networks[J].Proc Natl Acad Sci USA,2002,99(12):7821-7826.

[4] 杨博,刘大有,等.复杂网络聚类方法[J].软件学报,2009,20(1):54-61. Yang Bo,Liu Dayou,et al.Complex network clustering algorithms[J].Journal of Software,2009,20(1):54-61.(in Chinese)

[5] Newman M E J.Fast algorithm for detecting community structure in networks[J].Phys Rev E,2004,69(6):066133.

[6] V D Blondel,J Guillaume,R Lambiotte,E Lefebvre.Fast unfolding of communities in large networks[J].J Stat Mech,2008,(10):P10008.

[7] Fortunato S,Barthelemy M.Resolution limit in community detection[J].Proc Natl Acad Sci USA,2007,104(1):36-41.

[8] U N Raghavan,R Albert,S Kumara.Near linear time algorithm to detect community structures in large-scale networks[J].Phys Rev E,2007,76(3):036106.

[9] Rodrigo A,Ignacio M.Surprise maximization reveals the community structure of complex networks[J].Sci Rep,2013,3(1):1060.

[10] Newman M E J,Girvan M.Finding and evaluating community structure in networks[J].Phys Rev E,2004,69(2):026113.

[11] Roger Guimerà,Marta Sales-Pardo,Luís A Nunes Amaral.Modularity from fluctuations in random graphs and complex networks[J].Phys Rev E,2004,70(2):025101.

[12] J[AKo¨]rg Reichardt,Stefan Bornholdt.Partitioning and modularity of graphs with arbitrary degree distribution[J].Phys Rev E,2007,76(1):015102.

[13] A Lancichinetti,S Fortunato,F Radicchi.Benchmark graphs for testing community detection algorithms[J].Phys Rev E,2008,78(4):046110.

[14] Rodrigo Aldecoa,Ignacio Marín.Deciphering network community structure by surprise[J].PLoS ONE,2011,6(9):e24195.

[15] Leon Danon,Albert Díaz-Guilera,Jordi Duch,Alex Arenas.Comparing community structure identification[J].J Stat Mech,2005,(9):P09008.

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

Community Detection in Complex Networks Based on Greedy Optimization

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	李辉, 张建朋, 陈福才. 基于流式分析的大规模网络重叠社区发现算法[J]. 电子学报, 2022, 50(8): 1951-1958.
[2]	张磊, 刘庆, 杨尚尚, 杨海鹏, 程凡, 马海平. 基于双编码的重叠社团检测多目标优化方法[J]. 电子学报, 2021, 49(11): 2101-2107.
[3]	陈洁, 李锐, 赵姝, 张燕平. 面向图表示社区检测的新型聚类覆盖算法[J]. 电子学报, 2020, 48(9): 1680-1687.
[4]	胡钢, 高浩, 徐翔, 许丽鹏. 基于重要度传输矩阵的复杂网络节点重要性辨识方法[J]. 电子学报, 2020, 48(12): 2402-2408.
[5]	潘剑飞, 董一鸿, 陈华辉, 钱江波, 戴明洋. 基于结构紧密性的重叠社区发现算法[J]. 电子学报, 2019, 47(1): 145-152.
[6]	於志勇, 陈基杰, 郭昆, 陈羽中, 许倩. 基于影响力与种子扩展的重叠社区发现[J]. 电子学报, 2019, 47(1): 153-160.
[7]	王尔申, 王玉伟, 庞涛, 曲萍萍, 姜毅. 基于边攻击成本的复杂网络鲁棒性研究[J]. 电子学报, 2018, 46(5): 1166-1172.
[8]	何鹏, 王鹏, 李兵, 胡思文. 基于多粒度软件网络模型的软件系统演化分析[J]. 电子学报, 2018, 46(2): 257-267.
[9]	吴奇, 陈福才, 黄瑞阳, 常振超. 基于语义路径的异质网络社区发现方法[J]. 电子学报, 2016, 44(6): 1465-1471.
[10]	国琳, 左万利, 彭涛. 基于隶属度的社会化网络重叠社区发现及动态集群演化分析[J]. 电子学报, 2016, 44(3): 587-594.
[11]	刘世超, 朱福喜, 冯曦. 复杂网络的重叠社区及社区间的结构洞识别[J]. 电子学报, 2016, 44(11): 2600-2606.
[12]	国琳, 左万利. 基于兴趣图谱的用户兴趣分布分析及专家发现[J]. 电子学报, 2015, 43(8): 1561-1567.
[13]	王诗懿, 董一鸿, 李志超, 陈华辉, 钱江波. 大规模复杂网络下重叠社区的识别[J]. 电子学报, 2015, 43(8): 1575-1582.
[14]	张健沛, 邓琨, 杨静, 刘星妍. 基于边标签传播的复杂网络社区识别方法[J]. 电子学报, 2015, 43(6): 1113-1118.
[15]	潘伟丰, 李兵, 马于涛, 刘婧. 基于复杂软件网络的回归测试用例优先级排序[J]. 电子学报, 2012, 40(12): 2456-2465.