基于社团密合度的复杂网络社团发现算法

doi:10.12068/j.issn.1005-3026.2019.02.007

东北大学学报:自然科学版 ›› 2019, Vol. 40 ›› Issue (2): 186-191.DOI: 10.12068/j.issn.1005-3026.2019.02.007

基于社团密合度的复杂网络社团发现算法

陈东明，王云开，黄新宇，王冬琦

(东北大学软件学院，辽宁沈阳110169)

收稿日期:2017-11-01 修回日期:2017-11-01 出版日期:2019-02-15 发布日期:2019-02-12
通讯作者: 陈东明
作者简介:陈东明(1968-)，男，安徽怀宁人，东北大学教授.
基金资助:
辽宁省自然科学基金资助项目(20170540320)；辽宁省博士启动基金资助项目(20170520358)；辽宁省教育厅科学研究项目(L20150167).

Community Detection Algorithm for Complex Networks Based on Group Density

CHEN Dong-ming， WANG Yun-kai， HUANG Xin-yu， WANG Dong-qi

School of Software， Northeastern University， Shenyang 110169， China.

Received:2017-11-01 Revised:2017-11-01 Online:2019-02-15 Published:2019-02-12
Contact: WANG Yun-kai
About author:-
Supported by:
-

摘要/Abstract

摘要： 传统的社团发现算法大多存在划分效果和复杂度相矛盾的问题，为了解决该问题，提出一种新的单社团结构评价标准——社团密合度(group density).在此基础上，设计了一种基于凝聚思想的社团发现算法，该算法通过不断融合小社团，使网络的社团结构向平均社团密合度最大的方向发展，并使用模块度检测算法的划分结果.通过与经典的GN，Fast Newman，LPA等算法对多个数据集进行实验对比，验证了本文算法在获得较好的划分效果的同时具有较低的时间复杂度.

关键词: 复杂网络, 社团结构, 社团发现, 模块度, 社团密合度

Abstract: Most of the traditional community detection algorithms cannot balance partitioning effect and complexity well. So， this paper presents a new evaluation standard of single community called group density. Based on the group density， a community detection algorithm based on agglomeration is proposed. The algorithm continues to integrate small communities， and makes the community structure of the network develop in the direction of maximizing average group density. Modularity is employed to detect the partitioning effect of the algorithm. Experimental results demonstrate that the new algorithm outperforms the traditional GN， Fast Newman， LPA algorithms in multiple data sets， which shows that the algorithm proposed has better partitioning effect and lower time complexity.

Key words: complex network, community structure, community detection, modularity, group density

中图分类号:

TP393

陈东明，王云开，黄新宇，王冬琦. 基于社团密合度的复杂网络社团发现算法[J]. 东北大学学报:自然科学版, 2019, 40(2): 186-191.

CHEN Dong-ming， WANG Yun-kai， HUANG Xin-yu， WANG Dong-qi. Community Detection Algorithm for Complex Networks Based on Group Density[J]. Journal of Northeastern University Natural Science, 2019, 40(2): 186-191.

参考文献

[1]Newman M E J.The structure and function of complex networks［J］.SIAM Review，2003，45(2):167-256.
[2]Girvan M，Newman M E J.Community structure in social and biological networks［J］.Proceedings of the National Academy of Sciences，2002，99(12):7821-7826.
[3]Newman M E J.Fast algorithm for detecting community structure in networks［J］.Physical Review E，2004，69(6):066133.
[4]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):036106.
[5]Newman M E J，Clauset A.Structure and inference in annotated networks［J/OL］.Nature Communications，2016:11863［2017-10-08］.https://www.nature.com/articles/ncomms11863.
[6]Palla G，Dernyi I，Farkas I，et al.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature，2005，435(7043):814 -818.
[7]Evans T S，Lambiotte R.Line graphs，link partitions，and overlapping communities［J］.Physical Review E，2009，80(1):016105.
[8]Radicchi F，Castellano C，Cecconi F，et al.Defining and identifying communities in networks［J］.Proceedings of the National Academy of Sciences of the United States of America，2004，101(9):2658-2663.
[9]Li Z，Zhang S，Wang R S，et al.Quantitative function for community detection［J］.Physical Review E，2008，77(3):036109.
[10]Sun P G.Community detection by fuzzy clustering［J］.Physica A:Statistical Mechanics & Its Applications，2015，419:408-416.
[11]韩忠明，谭旭升，陈炎，等.NCSS:一种快速有效的复杂网络社团划分算法［J］.中国科学:信息科学， 2016，46(4):431-444.(Han Zhong-ming，Tan Xu-sheng，Chen Yan，et al.NCSS:an effective and efficient complex network community detection algorithm［J］.Scientia Sinica Informationis，2016，46(4):431-444.)
[12]刘世超，朱福喜，甘琳.基于标签传播概率的重叠社区发现算法［J］.计算机学报，2016，39(4):717-729.(Liu Shi-chao，Zhu Fu-xi，Gan Lin.A label-propagation-probability-based algorithm for overlapping community detection［J］.Chinese Journal of Computers，2016，39(4):717-729.)
[13]乔少杰，韩楠，张凯峰，等.复杂网络大数据中重叠社区检测算法［J］.软件学报，2017，28(3):631-647.(Qiao Shao-jie，Han Nan，Zhang Kai-feng，et al.Algorithm for detecting overlapping communities from complex network big data［J］.Journal of Software，2017，28(3):631-647.)
[14]王莉，程学旗.在线社会网络的动态社区发现及演化［J］.计算机学报，2015，38(2):219-237.(Wang Li，Cheng Xue-qi.Dynamic community in online social networks［J］.Chinese Journal of Computers，2015，38(2):219-237.)
[15]牛新征，司伟钰，佘堃.基于进化聚类的动态网络社团发现［J］.软件学报，2017，28(7):1773-1789.(Niu Xin-zheng，Si Wei-yu，She Kun.Evolutionary community detection in dynamic networks［J］.Journal of Software，2017，28(7):1773-1789.)
[16]Zachary W W.An information flow model for conflict and fission in small groups［J］.Journal of Anthropological Research，1977，33(4):452-473.
[17]Lusseau D，Schneider K，Boisseau O J，et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations［J］.Behavioral Ecology and Sociobiology，2003，54(4):396-405.
[18]Gong M，Fu B，Jiao L，et al.Memetic algorithm for community detection in networks［J］. Physical Review E，2011，84(5):056101.
[19]Knuth D E.The Stanford GraphBase:a platform for combinatorial computing ［M］.New York:ACM，1993:41-43.

基于社团密合度的复杂网络社团发现算法

Community Detection Algorithm for Complex Networks Based on Group Density

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	孔芝，孙琦，寇晓宇，王立夫. 基于属性信息和结构特性的网络节点重要度研究[J]. 东北大学学报（自然科学版）, 2022, 43(5): 625-631.
[2]	王翘秀，王宏，胡佛，化成城. 基于脑区社团结构的恐高程度识别模型[J]. 东北大学学报（自然科学版）, 2021, 42(3): 381-388.
[3]	王立夫，李欢，赵国涛. 基于节点最大剩余容量的改进负荷再分配策略[J]. 东北大学学报:自然科学版, 2020, 41(9): 1223-1230.
[4]	李延双，庄新田，王健，张伟平. 极端行情下中国股市社团结构及系统性风险分析[J]. 东北大学学报:自然科学版, 2020, 41(10): 1500-1508.
[5]	陈东明，严燕斌，黄新宇，王冬琦. 基于二分网络社团划分的推荐算法[J]. 东北大学学报:自然科学版, 2018, 39(8): 1103-1107.
[6]	赵海，李雄峰，朱宏博，王彬. 基于分形维数特征的肺结节形状建模[J]. 东北大学学报:自然科学版, 2018, 39(11): 1545-1551.
[7]	徐艳杰，任涛，齐义. 基于时空影响域的加权地震网络拓扑特性分析[J]. 东北大学学报:自然科学版, 2018, 39(11): 1551-1555.
[8]	黄新宇，陈东明，任涛. 多关系网络社团发现算法[J]. 东北大学学报:自然科学版, 2018, 39(10): 1375-1379.
[9]	何璇，王卢阳，赵海，刘晓. 地震数据关系网络的空间尺度[J]. 东北大学学报:自然科学版, 2018, 39(10): 1385-1389.
[10]	徐久强，宋佳，何璇，赵海. 基于OFC的仿真地震序列网络化特征对比分析[J]. 东北大学学报:自然科学版, 2017, 38(2): 205-209.
[11]	李婕，王兴伟，郭静，于超. 面向移动通信网络的局部扩张群组构造方法[J]. 东北大学学报:自然科学版, 2017, 38(12): 1691-1696.
[12]	李鹤群，徐久强，王进法，赵海. Internet分形特征研究[J]. 东北大学学报:自然科学版, 2016, 37(12): 1691-1695.
[13]	赵海，窦圣昶，蔡巍，陈星池. 脉搏波的复杂网络分析[J]. 东北大学学报:自然科学版, 2016, 37(12): 1696-1699.
[14]	王进法，赵海，刘晓，李鹤群. 基于空间影响域的虫害关系网络构造与分析[J]. 东北大学学报:自然科学版, 2016, 37(12): 1700-1704.
[15]	黄博南，李玉帅，孙秋野，张化光. 电网与灾害交互影响对电网关键环节辨识的影响[J]. 东北大学学报:自然科学版, 2016, 37(10): 1369-1373.