Computer Science ›› 2020, Vol. 47 ›› Issue (8): 157-163.doi: 10.11896/jsjkx.200300034

Previous Articles     Next Articles

Algorithm for Detecting Overlapping Communities Based on Centered Cliques

XUE Lei, TANG Xu-qing   

  1. School of Science, Jiangnan University, Wuxi, Jiangsu 214122, China
  • Online:2020-08-15 Published:2020-08-10
  • About author:XUE Lei, born in 1996, postgraduate.His main research interests include intelligent computing and bioinformatics.
    TANG Xu-qing, born in 1963, Ph.D, professor.His main research interests include intelligent computing, bioinformatics, modeling and simulation of ecological systems
  • Supported by:
    This work was supported by the National Natural Science Foundation of China(11371174).

Abstract: Community detection in complex network has become a vital way to understand its structure and dynamic characteristics.However, there are two inherent shortcomings that the parameter dependency and instability of using the traditional node clustering and link clustering to detect overlapping communities.This paper proposes an improving algorithm, that is, the local expansion method based on the centered clique(CLEM), for detecting overlapping communities.Firstly, in CLEM algorithm, the centered cliques is selected as the core seed and the nodes deleted by multiple times in the process of seed expansion are punished, so its stability of results is improved.Then, by selecting the fitness function with parameter-independent and improving its iterative calculation process, the parameter limitation of the fitness function is avoided and the computational complexity is quickly reduced.Finally, the test results on synthetic networks and real-world networks show that CLEM is good both in computing time and accuracy compared with some existing algorithms.

Key words: Centered clique, Local expansion, Overlapping community detection, Seed expansion, Community optimization

CLC Number: 

  • TP399
[1] SPORNS O, CHIALVO D R, KAISER M, et al.Organization, development and function of complex brain networks [J].Trends in Cognitive Sciences, 2004, 8(9):418-425.
[2] MEHTA R L, KELLUM J A, SHAH S V, et al.Acute Kidney Injury Network:report of an initiative to improve outcomes in acute kidney injury [J].Critical Care, 2007, 11(2):R31.
[3] NEWMAN M E J, PARK J.Statistical mechanics of networks [J].Physical Review E, 2004, 70(6):266117.
[4] NEWMAN M E J.The structure and function of complex networks [J].Siam Review, 2003, 45(2):167-256.
[5] BULLMORE E, SPORNS O.Complex brain networks:graphtheoretical analysis of structural and functional systems [J].Nature Reviews Neuroscience, 2009, 10(3):186-198.
[6] NEWMAN M E J, GIRVAN M.Modularity and communitystructure in networks [J].Proc.Natl.Acad.Sci.USA, 2006, 103(23):8577-8582.
[7] WHITE S D M, FRENK C S.Galaxy formation through hierarchical clustering [J].The Astrophysical Journal, 1991, 379(1):52-79.
[8] TANG X Q, ZHU P.Hierarchical clustering problems and analysis of fuzzy proximity relation on granular space [J].IEEE Transactions on Fuzzy Systems, 2013, 21(5):814-824.
[9] TAO H, TANG X Q.Clustering Structural Analysis on FuzzyProximity Relation [J].Computer Science, 2013, 40(1):263-267.
[10] KRZAKALA F, MOORE C, MOSSEL E, et al.Spectral redemption in clustering sparse networks [J].Proceedings of the National Academy of Sciences, 2013, 110(52):20935-20940.
[11] ZHANG X S, WANG R S, WANG Y, et al.Modularity optimization in community detection of complex networks [J].Europhysics Letters, 2009, 87(4):49901.
[12] ZHANG Q, LI H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition [J].IEEE Transactions on Evolutionary Computation, 2008, 11(6):712-731.
[13] MAITY S, RATH S K.Extended clique percolation method to detect overlapping community structure [C]∥Proceedings of the International Conference on Advances in Computing, Communications and Informatics.Washington, USA:IEEE, 2014.
[14] WEN X, CHEN W N, LIN Y, et al.A maximal clique based multiobjective evolutionary algorithm for overlapping community detection [J].IEEE Transactions on Evolutionary Computation, 2017, 22(3):363-377.
[15] NEWMAN M E J.Finding and evaluating community structure in networks [J].Physical Review E, 2004, 69(2):026113.
[16] PU S Y, WONG J, TURNER B, et al.Up-to-date catalogues of yeast protein complexes [J].NuCLEMic Acids Research, 2009, 37(3):825-831.
[17] XIE J, KELLEY S, SZYMANSKI B K.Overlapping community detection in networks:the state of the art and comparative study [J].Acm Computing Surveys, 2011, 45(4):1-35.
[18] PALLA G, DERENYI I, FARKAS I, et al.Uncovering the overlapping community structure of complex networks in nature and society [J].Nature, 2005, 435(7043):814-818.
[19] LANCICHINETTI A, FORTUNATO S, KERTéSZ J.Detecting the overlapping and hierarchical community structure in complex networks [J].New Journal of Physics, 2009, 11(3):033015.
[20] BECKERE, ROBISSON B, CHAPPLE C E, et al.Multifunctio-nal proteins revealed by overlapping clustering in protein interaction network [J].Bioinformatics, 2012, 28(1):84-90.
[21] NEPUSZ, TAMS, YU H, et al.Detecting overlapping protein complexes in protein-protein interaction networks [J].Nature Methods, 2012, 9(5):471-472.
[22] DING Z, ZHANG X, SUN D, et al.Overlapping community detection based on network decomposition [J].Scientific Reports, 2016, 6:24115.
[23] KARRER B, NEWMAN M E J.Stochastic blockmodels andcommunity structure in networks [J].Physical Review E, Statstical, Nonlinear, and Soft Matter Physics, 2010, 83(2):016107.
[24] GREGORY S.Finding overlapping communities in networks by label propagation [J].New Journal of Physics, 2010, 12(10):103018.
[25] YANG X H, SHEN M.Community detection algorithm based on local similarity of feature vectors [J].Computer Science, 2020, 47(2):58-64.
[26] EVANS T S, LAMBIOTTE R.Line graphs, link partitions, and overlapping communities [J].Physical Review E, 2009, 80(1):016105.
[27] AHN Y Y, BAGROW J P, LEHMANN S.Link communities reveal multiscale complexity in networks [J].Nature, 2010, 466:761-764.
[28] LAN H, GUISHEN W, YAN W, et al.Link Clustering with Extended Link Similarity and EQ Evaluation Division [J].PLoS ONE, 2013, 8(6):e66005.
[29] PIZZUTI C.Overlapped community detection in complex networks [C]∥Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation.New York, USA:ACM, 2009:859-866.
[30] FORTUNATO S.Community detection in graphs [J].Physics Reports, 2009, 486(3):75-174.
[31] ZHANG X, ZHANG S, WANG R, et al.Quantitative function for community detection [J].Physical Review E, 2008, 77:036109.
[32] RADICCHI F, CASTELLANO C.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.
[33] FORTUNATO S, BARTHELEMY M.Resolution limit in community detection [J].Proceedings of the National Academy of Sciences, 2007, 104(1):36-41.
[34] SHEN H, CHENG X, CAI K, et al.Detect overlapping and hierarchical community structure in networks [J].Physica A, 2009, 388(8):1706-1712.
[35] LANCICHINETTI A, FORTUNATO S, RADICCHI F.Newbenchmark in community detection [J].Physical Review E, 2008, 78(4):561-570.
[36] DANON L, DAZ-GUILERA A, DUCH J, et al.Comparingcommunity structure identification [J].Journal of Statistical Mechanics, 2005, DOI:10.1088/1742-5468/2005/09/p09008.
[37] LANCICHINETTI A, FORTUNATO S.Benchmarks for tes-ting community detection algorithms on directed and weighted graphs with overlapping communities [J].Physical Review E, 2009, 80(1):016118.
[38] NEWMAN M E J.Network Data[EB/OL].[2013-04-19].http://www-personal.umich.edu/~mejn/netdata/.
[39] ARENAS A.Data sets[EB/OL].http://deim.urv.cat/~alexandre.arenas/data/welcome.htm.
[1] ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Density Peaks [J]. Computer Science, 2020, 47(5): 72-78.
[2] ZHANG Qin, CHEN Hong-mei, FENG Yun-fei. Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model [J]. Computer Science, 2020, 47(10): 75-82.
[3] WANG Jie, LIANG Ji-ye, ZHAO Xing-wang, ZHENG Wen-ping. Overlapping Protein Complexes Detection Algorithm Based on Assortativity in PPI Networks [J]. Computer Science, 2019, 46(2): 294-300.
[4] LIU Chun, ZHANG Guo-liang. Software Feature Extraction Method Based on Overlapping Community Detection [J]. Computer Science, 2019, 46(12): 201-207.
[5] ZHANG Zhong-zheng and LI Jian-wu. Parallelizable Overlapping Community Detection Algorithm Based on Local Expansion [J]. Computer Science, 2016, 43(9): 61-65.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .