Community Detection Algorithm Base on Node and Edge Analysis
Gao Guangliang1(),Li Yazhou2,Yuan Ming1,Wang Qun1
1Department of Computer Information and Cyber Security, Jiangsu Police Institute, Nanjing 210031, China 2Department of Public Security Big Data, Department of Public Security of Jiangsu Province, Nanjing 210036, China
[Objective] This paper analyzes the importance of network nodes and edges, aiming to improve the performance of community detection algorithms based on objective function optimization. [Methods] First, we measured the importance of nodes based on the triangular structure and constructed a core network by deleting some nodes. Second, we measured the importance of edges based on the triangular structure. Then, we optimized the algorithm with the weighted modularity metric from a local perspective to detect communities in the core network. Finally, we extended these communities to obtain the actual community structure of the original network. [Results] We examined the proposed algorithm on a series of synthetic networks and four real-world network datasets. Our new algorithm’s F1 value was 19.85% higher than the baseline models. It yielded better results on dense networks. [Limitations] The proposed algorithm needs a user-specified parameter. [Conclusions] The proposed algorithm could effectively identify the non-overlapping and overlapping network communities.
高光亮, 李亚洲, 袁明, 王群. 融入节点和边缘重要性分析的社区发现算法*[J]. 数据分析与知识发现, 2023, 7(11): 114-124.
Gao Guangliang, Li Yazhou, Yuan Ming, Wang Qun. Community Detection Algorithm Base on Node and Edge Analysis. Data Analysis and Knowledge Discovery, 2023, 7(11): 114-124.
(Li Chengzan, Li Jianhui, Wang Xuezhi, et al. Research on Data Recommendation Based on Community Detection of Citation Network[J]. Journal of the China Society for Scientific and Technical Information, 2021, 40(8): 879-886.)
(Jin Zhiwei, Zhou Daishu. The Characteristics of Government Investment Fund Financing Network: City Distribution, Network Relationship and Community Discovery[J]. Science & Technology Progress and Policy, 2022, 39(5): 40-49.)
(Long Hao, Zhang Shukui, Zhang Li. Community Detection Algorithm Based on Social Relationship in Crowd Sensing Network[J]. Computer Engineering and Applications, 2020, 56(15): 179-184.)
doi: 10.3778/j.issn.1002-8331.1906-0194
(Duan Xiangyu, Yuan Guan, Meng Fanrong. Dynamic Community Detection: A Survey[J]. Journal of Frontiers of Computer Science and Technology, 2021, 15(4): 612-630.)
doi: 10.3778/j.issn.1673-9418.2008023
(Zhang Xin, Liu Bingquan, Wang Xiaolong. Research on Community Detection Methods in Complex Network[J]. Computer Engineering and Applications, 2015, 51(24): 1-7.)
(Zhang Haitao, Zhou Honglei, Zhang Xinrui, et al. Research Progress in Community Detection of Online Social Networks[J]. Library and Information Service, 2020, 64(9): 142-152.)
doi: 10.13266/j.issn.0252-3116.2020.09.016
[9]
Blondel V D, Guillaume J L, Lambiotte R, et al. Fast Unfolding of Communities in Large Networks[J]. Journal of Statistical Mechanics: Theory and Experiment, 2008(10): Article No. P10008.
Li Dong, Cheng Mingquan, Xu Yang, et al. Optimal Community Detection Method Based on Average Mutual Information[J]. Scientia Sinica (Informationis), 2019, 49(5): 613-629.)
(Yang Xuhua, Wang Lei, Ye Lei, et al. Complex Network Community Detection Algorithm Based on Node Similarity and Network Embedding[J]. Computer Science, 2022, 49(3): 121-128.)
doi: 10.11896/jsjkx.210200009
[12]
Lancichinetti A, Radicchi F, Ramasco J J, et al. Finding Statistically Significant Communities in Networks[J]. PLoS One, 2011, 6(4): Article No. e18961.
(Lin Sui, Chen Shishuang, Jiang Wenchao, et al. Overlapping Community Discovery Algorithm Based on Three-Level Neighbor Node Influence[J]. Computer Engineering and Design, 2022, 43(7): 1924-1929.)
[15]
Yang J, Leskovec J. Overlapping Community Detection at Scale: A Nonnegative Matrix Factorization Approach[C]// Proceedings of the 6th ACM International Conference on Web Search and Data Mining. ACM, 2013: 587-596.
[16]
Rezvani M, Liang W F, Liu C F, et al. Efficient Detection of Overlapping Communities Using Asymmetric Triangle Cuts[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(11): 2093-2105.
[17]
Fortunato S, Barthélemy M. Resolution Limit in Community Detection[J]. PNAS, 2007, 104(1): 36-41.
doi: 10.1073/pnas.0605965104
pmid: 17190818
[18]
Tasgin M, Bingol H O. Community Detection Using Preference Networks[J]. Physica A: Statistical Mechanics and Its Applications, 2018, 495: 126-136.
doi: 10.1016/j.physa.2017.12.060
[19]
Gao G L, Wu Z A, Zhang L, et al. Community Detection via Local Learning Based on Generalized Metric with Neighboring Regularization[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2022, 52(1): 498-510.
doi: 10.1109/TSMC.2020.3003019
[20]
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(3): Article No. 036106.
[21]
Wu Z A, Gao G L, Bu Z, et al. SIMPLE: A Simplifying-Ensembling Framework for Parallel Community Detection from Large Networks[J]. Cluster Computing, 2016, 19(1): 211-221.
doi: 10.1007/s10586-015-0504-2
[22]
Newman M E J. Modularity and Community Structure in Networks[J]. PNAS, 2006, 103(23): 8577-8582.
doi: 10.1073/pnas.0601602103
pmid: 16723398
[23]
Chakraborty T, Dalmia A, Mukherjee A, et al. Metrics for Community Analysis: A Survey[J]. ACM Computing Surveys, 2018, 50(4): 1-37.
[24]
Berry J W, Hendrickson B, LaViolette R A, et al. Tolerating the Community Detection Resolution Limit with Edge Weighting[J]. Physical Review E, 2011, 83(5): Article No. 056119.
[25]
Lancichinetti A, Fortunato S. Benchmarks for Testing Community Detection Algorithms on Directed and Weighted Graphs with Overlapping Communities[J]. Physical Review E, Statistical, Nonlinear, and Soft Matter Physics, 2009, 80(1 Pt 2): Article No. 016118.
