计算机科学 ›› 2020, Vol. 47 ›› Issue (2): 58-64.doi: 10.11896/jsjkx.181202433
杨旭华,沈敏
YANG Xu-hua,SHEN Min
摘要： 社区的发现和分析是复杂网络结构和功能研究中的一个热点。目前广泛应用的社区划分算法存在时间复杂度过高、社区核心数量无法准确量化、划分精度不高等问题。文中提出了一种基于特征向量局部相似性的社区检测算法ELSC。该算法首先计算网络中每个节点的特征向量中心性,在此基础上提出了特征向量局部相似性(ELS)和特征向量吸引性(EA)指标。ELS指标表示节点之间的相似性,用来形成初始社区,在同一个社区内部节点之间的相似性较高,在不同社区节点之间的相似性较低;EA指标同时考虑了局部相似性和特征向量中心性的占比,表示节点之间的吸引性,用来优化初始社区,并在此基础上完成网络的社区划分。该算法由最值确定节点,避免了节点数量阈值不确定的问题。在7个真实网络上将所提算法与6种知名算法的模块度和标准化互信息两个指标进行综合比较,结果表明,该算法具有良好的准确性,并且具有较低的时间复杂度。
中图分类号:
| [1]NEWMAN M E J,CLAUSET A.Structure and inference in annotated networks [J].Nature Communications,2016,7:11863. [2]HU F,WANG M Z,WANG Y R,et al.An algorithm J-SC of detecting communities in complex networks [J].Physics Letters A,2017,381(42):3604-3612. [3]HU F,LIU Y H.A new algorithm CNM-Centrality of detecting communities based on node centrality [J].Physics A,2016,446:138-151. [4]WANG T,YIUN L Y,WANG X X.A community detection method based on local similarity and degree clustering information [J].Physics A,2018,490:1344-1354. [5]CHEN L G,WANG Y R,HUANG X M,et al.SA-SOM algorithm for detecting communities in complex networks [J].Phy-sics Letters B,2017,31(29):1750262. [6]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks [J].Physical Review E,2004,70:066111. [7]ZHANG X K,REN J,SONG C,et al.Label propagation algorithm for community detection based on node importance and label influence [J].Physics Letters A,2017,381:2691-2698. [8]LI Y F,JIA C Y,YU J.A parameter-free community detection method based on centrality and dispersion of nodes in complex networks [J].Physics A,2015,438:321-334. [9]YUTAKA I.SUEMATSU L,YUTA K.A Framework for Fast Community Extraction of Large-Scale Networks [J].ACM,2008,978:1215-1216. [10]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al. Fast unfolding of communities in large networks [J].Journal of Statistical Mechanics,2008,2008:p10008. [11]BARBE R M J,CLARK J W.Detecting network communities by propagating labels under constraints [J].Physical Review E,2009,80:026129. [12]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:036106. [13]ŠUBELJ L,BAJEC M.Ubiquitousness of link-density and link-pattern communities in real-world networks [J].The European Physical Journal B,2012,85:1-11. [14]JIN H,WANG S,LI C.Community detection in complex net-works by density-based clustering [J].Physics A,2013,392(19):4606-4618. [15]GONG M,LIU J.Novel heuristic density-based method for community detection in networks [J].Physics A,2014,403:71-84. [16]ZHOU H.Distance,dissimilarity index,and network community structure [J].Physical Review E,2003,67(6):061901. [17]ROSVALL M,BERGSTROM C T.Maps of random walks on complex networks reveal community structure [J].PNAS,2008,105(4):1118-1123. [18]MACQUEEN J B.Some methods for classification and analysis of multivariate observations in:Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and Probability [J].American Mathematical Society,1967(66):281-297. [19]JIANG Y W,JIA C V,YU J.An efficient community detection method based on rank centrality [J].Physics A,2013,392:2182-2194. [20]XU H T,WU H,FANG X J,et al.Finding Key Stations of Hangzhou Public Bicycle System by an Improved K-Means Algorithm [J].Journal of Mechanics of Materials and Structures,2012,209:925-929. [21]FENDER A,EMAD N,PETITION S.Parallel Jaccard and Related Graph Clustering Techniques [J].ACM ISBN,2017,978:4503-5125. [22]EUSTACE J.Community detection using local neighborhood in complex networks [J].Physics A,2015,436:665-677. [23]BAGROW J P,BOLLT E M.Local method for detecting communities [J].Physical Review E,2005,72 (4):046108. [24]CLAUSET A.Finding local community structure in networks [J].Physical Review E,2005,72(2):026132. [25]HUANG J,SUN H,LIU Y,et al.Towards online multiresolution community detection in large-scale networks [J].PLOS ONE,2011,6(8):e23829. [26]GLEISER P M,DANON L.Community structure in Jazz[J].Advances in Complex Systems,2003,6:565-573. [27]LANCICHINETTI A,FORTUNATO S,RADIHHI F.Benchmark graphs for testing community detection algorithms [J].Physical Review E,2008,78:046110. [28]HU Q C,ZHANG Y,XING C X.Research on Maximization Method of Social Network Influence Based on Overlapping Community Division [J].Computer Science,2018,45(6):32-35. [29]REN X L,LV L Y.Review of ranking nodes in complex networks [J].Chinese Science Bulletin,2014,9(13):1175-1197. [30]ZHANG D,LI X H,LIU H,et al.Service-Oriented Network Node Importance Ranking Method in SDN Network[J].Chinese Journal of Computers,2018,41(11):2624-2636. [31]QIAO S J,HAN N,ZHANG K F,et al.Overlapping community detection algorithm in complex network big data[J].Journal of Software,2017,28(3):631-647. [32]DAI D B,TANG C L,XIONG W.Sequence clustering algorithm based on global and local similarity [J].Journal of Software,2010,21(4):702-717. |
| [1] | 蒲实, 赵卫东. 一种面向动态科研网络的社区检测算法 Community Detection Algorithm for Dynamic Academic Network 计算机科学, 2022, 49(1): 89-94. https://doi.org/10.11896/jsjkx.210100023 |
| [2] | 薛磊, 唐旭清. 基于中心团的重叠社区检测算法 Algorithm for Detecting Overlapping Communities Based on Centered Cliques 计算机科学, 2020, 47(8): 157-163. https://doi.org/10.11896/jsjkx.200300034 |
| [3] | 陈伯伦,陈崚,邹盛荣,徐秀莲. 基于矩阵分解的二分网络社区挖掘算法 Detecting Community Structure in Bipartite Networks Based on Matrix Factorization 计算机科学, 2014, 41(2): 55-58. |
|
||
首页