基于社区密度的重叠社区检测算法
Overlapping Community Detection Algorithm Based on Community Density
DOI: 10.12677/AAM.2023.126303, PDF,    国家自然科学基金支持
作者: 赵洋洋*, 刘士虎#, 胡志涛：云南民族大学，数学与计算机科学学院，云南 昆明
关键词: 社区检测；重叠社区；社区密度；单一阈值；Community Detection； Overlapping Community； Community Density； Single Threshold
摘要: 社区检测是研究复杂网络的热点话题之一，其目的是找到具有共同性质的社区成员。随着网络复杂性的增强，传统算法在时间和精度上都受到了一定的限制。基于此，本文提出一种基于社区密度的重叠社区检测方法。在该方法中，我们首先对顶点的邻居集做交集运算，在确定初始候选社区的基础上过滤掉社区密度低于阈值的社区。其次，以社区间相似性这一概念作为社区合并的判断条件，生成重叠社区。最后，我们在两类合成网络上与现有的经典算法作比较，实验结果表明本文所建立的算法是有效的。
Abstract: Community detection is one of the hot topics in the study of complex networks, the purpose is to find community members with common properties. With the increasing complexity of networks, traditional algorithms are limited in both time and accuracy. In this paper, we propose a communi-ty density-based overlapping community detection method. In this method, we first intersect the set of neighbors of the vertices and filter out the communities that are below the community densi-ty threshold to determine the initial candidate communities. Next, the concept of inter-community similarity was used as a criterion for community merging to generate overlapping communities. We finally compare the algorithm with existing classical algorithms on two types of synthetic networks and the experimental results show that the algorithm established in this paper is efficient.
文章引用：赵洋洋, 刘士虎, 胡志涛. 基于社区密度的重叠社区检测算法[J]. 应用数学进展, 2023, 12(6): 3021-3029. https://doi.org/10.12677/AAM.2023.126303

参考文献

[1] 安沈昊, 于荣欢. 复杂网络理论研究综述[J]. 计算机系统应用, 2020, 29(9): 26-31.
[2] Chen, B.L., Fan, W.W., Liu, J. and Wu, F.-X. (2014) Identifying Protein Complexes and Functional Modules—From Static PPI Networks to Dynamic PPI Networks. Briefings in Bioinformatics, 15, 177-194. [Google Scholar] [CrossRef] [PubMed]
[3] Kolpin, D., Ramos, F.M.V., Veríssimo, P.E., et al. (2015) Soft-ware-Defined Networking: A Comprehensive Survey. Proceedings of the IEEE, 103, 14-76. [Google Scholar] [CrossRef] 
[4] 张继洋, 李宁. 科学合著网络研究进展分析[J]. 情报理论与实践, 2012, 35(4): 124-128.
[5] Clauset, A., Newman, M.E.J. and Moore, C. (2004) Finding Community Structure in Very Large Networks. Physical Review E, 70, Article ID: 066111. [Google Scholar] [CrossRef] 
[6] Fortunato, S. (2010) Community Detection in Graphs. Physics Reports, 486, 75-174. [Google Scholar] [CrossRef] 
[7] Ye, F.H., Chen, C., Zheng, Z.B., Li, R.-H. and Yu, J.X. (2019) Discrete Overlapping Community Detection with Pseudo Supervision. 2019 IEEE International Conference on Data Mining (ICDM), Beijing, 8-11 November 2019, 708-717. [Google Scholar] [CrossRef] 
[8] Palla, G., Derényi, I., Farkas, I. and Vicsek, T. (2005) Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society. Nature, 435, 814-818. [Google Scholar] [CrossRef] [PubMed]
[9] Zhang, Y., Levina, E. and Zhu, J. (2020) Detecting Overlapping Communities in Networks Using Spectral Methods. SIAM Journal on Mathematics of Data Science, 2, 265-283. [Google Scholar] [CrossRef] 
[10] 李向利, 范学珍, 逯喜燕. 基于非负矩阵分解的修正模糊聚类算法[J]. 吉林大学学报(理学版), 2022, 60(6): 1416-1422.
[11] Ahn, Y.-Y., Bagrow, J. and Leh-mann, S. (2010) Link Communities Reveal Multiscale Complexity in Networks. Nature, 466, 761-764. [Google Scholar] [CrossRef] [PubMed]
[12] Feng, O.G., Shen, Y., Xu, H.L., Jiang, H.Y. and Ren, S.G. (2021) Local Fuzzy Community Detection in Networks. Recent Advances in Electrical & Electronic Engineering, 14, 122-129. [Google Scholar] [CrossRef] 
[13] Kun, G., Huang, X.T., Wu, L. and Chen, Y.Z. (2022) Local Community Detection Algorithm Based on Local Modularity Density. Applied Intelligence, 52, 1238-1253. [Google Scholar] [CrossRef] 
[14] Gregory, S. (2010) Finding Overlapping Communities in Net-works by Label Propagation. New Journal of Physics, 12, Article ID: 103018. [Google Scholar] [CrossRef] 
[15] Xie, J. and Szymanski, B.K. (2012) Towards Linear Time Overlapping Community Detection in Social Networks. In: Tan, P.-N., Chawla, S., Ho, C.K. and Bailey, J., Eds., Ad-vances in Knowledge Discovery and Data Mining. PAKDD 2012. Lecture Notes in Computer Science, Vol. 7302, Springer, Berlin, 25-36. [Google Scholar] [CrossRef] 
[16] Becker, E., Robisson, B., Chapple, C.E., Guénoche, A. and Brun, C. (2012) Multifunctional Proteins Revealed by Overlapping Clustering in Protein Interaction Network. Bioinfor-matics, 28, 84-90. [Google Scholar] [CrossRef] [PubMed]
[17] Lancichinetti, A. and Fortunato, S. (2009) Benchmarks for Test-ing Community Detection Algorithms on Directed and Weighted Graphs with Overlapping Communities. Physical Re-view E, 80, Article ID: 016118. [Google Scholar] [CrossRef] 
[18] Shen, H.W., Cheng, X.Q., Cai, K. and Hu, M.-B. (2009) Detect Overlapping and Hierarchical Community Structure in Networks. Physica A: Statistical Mechanics and Its Applications, 388, 1706-1712. [Google Scholar] [CrossRef] 
[19] Whang, J.J., Gleich, D.F. and Dhillon, I.S. (2016) Overlapping Community Detection Using Neighborhood-Inflated Seed Expansion. IEEE Transactions on Knowledge and Data En-gineering, 28, 1272-1284. [Google Scholar] [CrossRef] 
[20] Raghavan, U.N., Albert, R. and Kumara, S. (2007) Near Linear Time Algorithm To Detect Community Structures in Large-Scale Networks. Physical Review E, 76, Article ID: 036106. [Google Scholar] [CrossRef] 

为你推荐