计算机科学 ›› 2020, Vol. 47 ›› Issue (8): 157-163.doi: 10.11896/jsjkx.200300034
薛磊, 唐旭清
XUE Lei, TANG Xu-qing
摘要： 社区检测已经成为了了解复杂网络结构和网络动态的一个重要途径。针对传统的节点聚类和链接聚类在发现重叠社区方面存在的两种固有缺陷, 即参数依赖和结果不稳定, 文中提出了一种基于中心团的局部扩展改进算法CLEM, 用于检测重叠社区。该算法通过选取中心团为核心种子, 并在种子扩展过程中惩罚被多次删除的节点, 改善所得结果的稳定性;通过选取不依赖参数的适应度函数, 改进其迭代计算过程, 避免了适应度函数的参数限制, 并降低了计算复杂度。在合成网络和现实网络上测试的结果表明, 与已有算法相比, 所提算法在计算时间和准确度上均有很好的表现。
中图分类号:
| [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, DAZ-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] | 陈湘涛, 赵美杰, 杨梅. 基于子图结构的局部社区发现算法 Overlapping Community Detection Algorithm Based on Subgraph Structure 计算机科学, 2021, 48(9): 244-250. https://doi.org/10.11896/jsjkx.201100010 |
| [2] | 王杰, 梁吉业, 赵兴旺, 郑文萍. 一种基于同配性的重叠蛋白质复合体检测算法 Overlapping Protein Complexes Detection Algorithm Based on Assortativity in PPI Networks 计算机科学, 2019, 46(2): 294-300. https://doi.org/10.11896/j.issn.1002-137X.2019.02.045 |
|
||
首页