计算机科学 ›› 2022, Vol. 49 ›› Issue (12): 170-177.doi: 10.11896/jsjkx.211000025
段小虎1, 曹付元1,2
DUAN Xiao-hu1, CAO Fu-yuan1,2
摘要： 为了有效地发现复杂网络中的重叠社区结构,引入了密度峰值聚类算法,但将此算法应用于社区发现还存在如何度量节点间距离、如何产生重叠划分结果等问题。为此提出了一种基于节点局部相似性的两阶段密度峰值重叠社区发现方法(Node Local Similarity Based Two-stage Density Peaks Algorithm for Overlapping Community Detection,LSDPC)。该方法结合大度节点有利指标和连接贡献度定义了一种新的节点局部相似性指标,首先通过节点局部相似性度量节点距离;然后通过节点的局部密度和最小距离计算节点中心值,利用切比雪夫不等式筛选出社区中心节点;最后经过初次划分与重叠划分两阶段得到最终的重叠社区划分结果。在真实网络数据集与合成网络数据集上的实验结果表明,所提算法可以有效发现重叠社区结构,且结果优于其他对比算法。
中图分类号:
| [1]HAN N,QIAO S J,YUAN C A,et al.A Fast Parallel Community Detection Algorithm for Mobile Social Networks[J].Journal of Chongqing University of Technology (Natural Science),2020,34(1):94-102. [2]FORTUNATO S,HRIC D.Community detection in networks:a user guide[J].Physics Reports,2016,659:1-44. [3]ZHAO W J,ZHANG F B,LIU J L.Review on Community Detection in Complex Networks [J].Computer Science,2020,47(2):10-20. [4]RODRIGUEZ A,LAIO A.Clustering by fast search and find of density peaks[J].Science,2014,344(6191):1492-1496. [5]RAVASE E,SOMERA A L,MONGRU D A,et al.Hierarchical organization of modularity in metabolic networks[J].Science,2002,297(5586):1553-1555. [6]DING J J,CHEN Z T,HE X X,et al.Clustering by finding density peaks based on Chebyshev's inequality[C]//Proceedings of the 2016 35th Chinese Control Conference.IEEE,2016:7169-7172. [7]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. [8]GREGORY S.Finding overlapping communities in networks by label propagation[J].New Journal of Physics,2010,12(10):2011-2024. [9]XIE J,SZYMANSKI B K,LIU X.SLPA:Uncovering overlap-ping communities in social networks via a speaker-listener intera-ction dynamic process[C]//Proceedings of the 2011 IEEE 11th International Conference on Data Mining Workshops.IEEE,2011:344-349. [10]LIU S C,ZHU F X,GAN L.A label-propagation-probability-based algorithm for overlapping community detection[J].Chinese Journal of Computers,2016,39(4):717-729. [11]LANCICHINETTI A,FORTUNATO S,KERTÉSZ J.Detec-ting the overlapping and hierarchical community structure in complex networks[J].New Journal of Physics,2009,11(3):1-18. [12]YU Z Y,CHEN J J,GUO K,et al.Overlapping community detection based on influence and seeds extension[J].Chinese Journal of Electronics,2019,47(1):153-160. [13]COSCIA M,ROSSETTI G,GIANNOTTI F,et al.DEMON:a local-first discovery method for overlapping communities[C]//Proceedings of the18th ACM SIGKDD International Confe-rence on Knowledge Discovery and Data Mining.ACM,2012:615-623. [14]AHN Y Y,BAGROW J,LEHMANN S.Link communities reveal multiscale complexity in networks[J].Nature,2010,466(7307):761-764. [15]PAN L,JIN J,WANG C J,et al.Detecting Link Communities Based on Local Information in Social Networks[J].Chinese Journal of Electronics,2012,40(11):2255-2263. [16]HUANG L,WANG G,WANG Y,et al.A link density clustering algorithm based on automatically selecting density peaks for overlapping community detection[J].International Journal of Modern Physics B,2016,30(24):1650167. [17]HUANG L,LI Y,WANG G S,et al.Community detectionmethod based on vertex distance and clustering of density peaks[J].Journal of Jilin University (Engineering and Technology Edition),2016,46(6):2042-2051. [18]DING J J,HE X X,YUAN J Q,et al.Community detection by propagating the label of center[J].Physica A:Statistical Mechanics and Its Applications,2018,503:675-686. [19]BAI X Y,YANG P L,SHI X H.An overlapping communitydetection algorithm based on density peaks[J].Neurocompu-ting,2017,226:7-15. [20]XU M L,LI Y H,LI R X,et al.EADP:An extended adaptive density peaks clustering for overlapping community detection in social networks[J].Neurocomputing,2019,337(2019):287-302. [21]FENG Y F,CHEN H M.Topological structure based density peak algorithm for overlapping community detection[J].Computer Science,2019,46(10):39-48. [22]WANG X F,LI X,CHEN G R.Network science:an introduction[M].Beijing:Higher Education Press,2012. [23]SHAO J M,HAN Z C,YANG Q L,et al.Community detection based on distance dynamics[C]//Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.ACM,2015:1075-1084. [24]LÜ L Y.Link prediction on complex networks[J].Journal ofUniversity of Electronic Science and Technology of China,2010,39(5):651-661. [25]XIE J Y,GAO H C,XIE W X,et al.Robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors[J].Information Sciences,2016,354:19-40. [26]NEWMAN M.Network data [EB/OL].http://www.personal.umich.edu/~mejn/netdata/. [27]KUNEGIS J.KONECT:the Koblenz network collection[C]//Proceedings of the 22nd International Conference on World Wide Web.ACM,2013:1343-1350. [28]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms [J].Physical Review E,2008,78(4):046110. [29]FORTUNATO S.LFR benchmark graphs [EB/OL].https://www.santofortunato.net/resources. [30]NICOSIA V,MANGIONI G,CARCHIOLO V,et al.Extending the definition of modularity to directed graphs with overlapping communities[J].Journal of Statistical Mechanics:Theory and Experiment,2009,2009(3):3024-3046. |
| [1] | 毛森林, 夏镇, 耿新宇, 陈剑辉, 蒋宏霞. 基于密度敏感距离和模糊划分的改进FCM算法 FCM Algorithm Based on Density Sensitive Distance and Fuzzy Partition 计算机科学, 2022, 49(6A): 285-290. https://doi.org/10.11896/jsjkx.210700042 |
| [2] | 杨旭华, 王磊, 叶蕾, 张端, 周艳波, 龙海霞. 基于节点相似性和网络嵌入的复杂网络社区发现算法 Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding 计算机科学, 2022, 49(3): 121-128. https://doi.org/10.11896/jsjkx.210200009 |
| [3] | 郑文萍, 王宁, 杨贵. 一种基于局部路径信息的重叠社区发现算法 Overlapping Community Detection Algorithm Based on Local Path Information 计算机科学, 2022, 49(12): 155-162. https://doi.org/10.11896/jsjkx.220500190 |
| [4] | 戴小路, 汪廷华, 周慧颖. 基于加权马氏距离的模糊多核支持向量机 Fuzzy Multiple Kernel Support Vector Machine Based on Weighted Mahalanobis Distance 计算机科学, 2022, 49(11A): 210800216-5. https://doi.org/10.11896/jsjkx.210800216 |
| [5] | 陈湘涛, 赵美杰, 杨梅. 基于子图结构的局部社区发现算法 Overlapping Community Detection Algorithm Based on Subgraph Structure 计算机科学, 2021, 48(9): 244-250. https://doi.org/10.11896/jsjkx.201100010 |
| [6] | 汤鑫瑶, 张正军, 储杰, 严涛. 基于自然最近邻的密度峰值聚类算法 Density Peaks Clustering Algorithm Based on Natural Nearest Neighbor 计算机科学, 2021, 48(3): 151-157. https://doi.org/10.11896/jsjkx.200100112 |
| [7] | 宁懿昕, 谢辉, 姜火文. 图神经网络社区发现研究综述 Survey of Graph Neural Network in Community Detection 计算机科学, 2021, 48(11A): 11-16. https://doi.org/10.11896/jsjkx.210500151 |
| [8] | 王卫东, 徐金慧, 张志峰, 杨习贝. 基于密度峰值聚类的高斯混合模型算法 Gaussian Mixture Models Algorithm Based on Density Peaks Clustering 计算机科学, 2021, 48(10): 191-196. https://doi.org/10.11896/jsjkx.200800191 |
| [9] | 张煜, 陆亿红, 黄德才. 基于密度峰值的加权犹豫模糊聚类算法 Weighted Hesitant Fuzzy Clustering Based on Density Peaks 计算机科学, 2021, 48(1): 145-151. https://doi.org/10.11896/jsjkx.200400043 |
| [10] | 张琴, 陈红梅, 封云飞. 一种基于粗糙集和密度峰值的重叠社区发现方法 Overlapping Community Detection Method Based on Rough Sets and Density Peaks 计算机科学, 2020, 47(5): 72-78. https://doi.org/10.11896/jsjkx.190400160 |
| [11] | 陈俊芬,张明,赵佳成. 复杂高维数据的密度峰值快速搜索聚类算法 Clustering Algorithm by Fast Search and Find of Density Peaks for Complex High-dimensional Data 计算机科学, 2020, 47(3): 79-86. https://doi.org/10.11896/jsjkx.190400123 |
| [12] | 张琴, 陈红梅, 封云飞. 基于粗糙集和距离动态模型的重叠社区发现方法 Overlapping Community Detection Method Based on Rough Sets and Distance Dynamic Model 计算机科学, 2020, 47(10): 75-82. https://doi.org/10.11896/jsjkx.190800002 |
| [13] | 李晓光, 邵超. 基于网格数据中心的密度峰值聚类算法 Density Peak Clustering Algorithm Based on Grid Data Center 计算机科学, 2019, 46(6A): 457-460. |
| [14] | 刘春, 张国良. 一种基于重叠社区发现的软件特征提取方法 Software Feature Extraction Method Based on Overlapping Community Detection 计算机科学, 2019, 46(12): 201-207. https://doi.org/10.11896/jsjkx.181001856 |
| [15] | 封云飞, 陈红梅. 基于拓扑结构的密度峰值重叠社区发现算法 Topological Structure Based Density Peak Algorithm for Overlapping Community Detection 计算机科学, 2019, 46(10): 39-48. https://doi.org/10.11896/jsjkx.180901644 |
|
||
首页