计算机科学 ›› 2021, Vol. 48 ›› Issue (9): 244-250.doi: 10.11896/jsjkx.201100010
陈湘涛, 赵美杰, 杨梅
CHEN Xiang-tao, ZHAO Mei-jie, YANG Mei
摘要: 局部社区发现算法通常选取种子节点进行社区发现,针对现有重叠社区发现算法中种子节点选取时有效性不足的问题,提出了一种基于子图结构的局部社区发现算法(Subgragh Structure Based Overlapping Community Detection,SUSBOCD)。该算法提出了一种新的节点重要性度量指标,不仅考虑了节点的邻居数量,同时也考虑了邻居间的链接紧密程度。首先,选取未被访问且重要性最大的节点以及与其最为相似的邻居节点,将该两个节点及其公共邻居节点合并形成一个初始种子子图,该过程迭代运行直到所有节点均被访问;其次,根据种子子图的邻域信息进行相似度判断,若相似则进行合并,从而形成初始社区结构,持续扩展该过程直到所有种子子图均被访问;最后,对社区进行优化处理,若存在未分配社区的节点,则将其加入到最相似的初始社区,再合并重叠度较高的初始社区结构。在人工数据集和真实数据集上,对所提算法进行实验验证,实验结果表明,与其他重叠社区发现算法相比,SUSBOCD算法在ONMI,EQ和Omega这3个评价指标上均有所提升,即该算法能有效地提高重叠社区的划分质量。
中图分类号:
[1]NEWMAN M E J.The structure of scientific collaboration networks[J].Proceedings of the National Academy of Sciences,2001,98(2):404-409. [2]NEWMAN M E J.The structure and function of complex networks[J].SIAM Review,2003,45(2):167-256. [3]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. [4]LANCICHINETTI A,FORTUNATO S,KERTÉSZ J.Detec-tingthe overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):033015. [5]CHEN Q,WU T T,FANG M.Detecting local community structures in complex networks based on local degree central nodes[J].Physica A:Statistical Mechanics and its Applications,2013,392(3):529-537. [6]LI Y,HE J,WU Y X.Overlapping Community Discovery Me-thod Based on Greedy Expansion of Seed Nodes[J].Journal of Chinese Computer Systems,2019,40(5):1115-1119. [7]WANG X,LIU G,LI J,et al.Locating structural centers:A density-based clustering method for community detection[J].PloS one,2017,12(1):e0169355. [8]WANG X,LIU G,LI J.Overlapping community detection based on structural centrality in complex networks[J].IEEE Access,2017,5:25258-25269. [9]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496. [10]YU Z Y,CHEN J J,GUO K.Overlapping Community Detection Based on Influence and Seeds Extension[J].Acta Electronica Sinica,2019,47(1):153-160. [11]ZHANG X,WANG C,SU Y,et al.A fast overlapping community detection algorithm based on weak cliques for large-scale networks[J].IEEE Transactions on Computational Social Systems,2017,4(4):218-230. [12]GREGORY S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):2011-2024. [13]PALLA G,IMRE D,ILLÉS F,et al.Uncovering the overlapping community structure of complex networks in nature and society[J].Nature,2005,435(7043):814-818. [14]COSCIA M,ROSSETTI G,GIANNOTTI F,et al.DEMON:a Local-First Discovery Method for Overlapping Communities [C]//Proceeding of ACM SIGKDD International Conference on Knowledge Discovery & Data Mining.2012:615-623. [15]CHEN X,LI J.Overlapping Community Detection by Node-Weighting[C]//Proceedings of the 2nd International Confe-rence on Compute and Data Analysis,ICCDA.2018:70-74. |
[1] | 宁懿昕, 谢辉, 姜火文. 图神经网络社区发现研究综述 Survey of Graph Neural Network in Community Detection 计算机科学, 2021, 48(11A): 11-16. https://doi.org/10.11896/jsjkx.210500151 |
[2] | 薛磊, 唐旭清. 基于中心团的重叠社区检测算法 Algorithm for Detecting Overlapping Communities Based on Centered Cliques 计算机科学, 2020, 47(8): 157-163. https://doi.org/10.11896/jsjkx.200300034 |
[3] | 张琴, 陈红梅, 封云飞. 一种基于粗糙集和密度峰值的重叠社区发现方法 Overlapping Community Detection Method Based on Rough Sets and Density Peaks 计算机科学, 2020, 47(5): 72-78. https://doi.org/10.11896/jsjkx.190400160 |
[4] | 张琴, 陈红梅, 封云飞. 基于粗糙集和距离动态模型的重叠社区发现方法 Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model 计算机科学, 2020, 47(10): 75-82. https://doi.org/10.11896/jsjkx.190800002 |
[5] | 刘春, 张国良. 一种基于重叠社区发现的软件特征提取方法 Software Feature Extraction Method Based on Overlapping Community Detection 计算机科学, 2019, 46(12): 201-207. https://doi.org/10.11896/jsjkx.181001856 |
[6] | 张忠正,李建武. 一种基于局部拓展的并行重叠社区发现算法 Parallelizable Overlapping Community Detection Algorithm Based on Local Expansion 计算机科学, 2016, 43(9): 61-65. https://doi.org/10.11896/j.issn.1002-137X.2016.09.011 |
|