Community Detection Algorithm for Complex Networks Based on Group Density

doi:10.12068/j.issn.1005-3026.2019.02.007

Abstract

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

CLC Number:

TP393

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.

References

[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.