|
|
|
| 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 |
|
|
|
|
Abstract [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.
|
|
Received: 29 September 2022
Published: 05 January 2024
|
|
|
| Fund:National Natural Science Foundation of China(92046026);Philosophy and Social Foundation of the Jiangsu Higher Education Institutions(2022SJYB0466);Natural Science Foundation of the Jiangsu Higher Education Institutions(23KJB520009) |
|
Corresponding Authors:
Gao Guangliang， ORCID： 0000-0002-8183-2559， E-mail： guangliang.gao@njust.edu.cn。
|
| [1] |
Fortunato S, Hric D. Community Detection in Networks: A User Guide[J]. Physics Reports, 2016, 659: 1-44.
doi: 10.1016/j.physrep.2016.09.002
|
| [2] |
涂存超, 杨成, 刘知远, 等. 网络表示学习综述[J]. 中国科学: 信息科学, 2017, 47(8): 980-996.
|
| [2] |
Tu Cunchao, Yang Cheng, Liu Zhiyuan, et al. Network Representation Learning: An Overview[J]. Scientia Sinica (Informationis), 2017, 47(8): 980-996.)
|
| [3] |
李成赞, 黎建辉, 王学志, 等. 基于引文网络社区发现的数据推荐研究[J]. 情报学报, 2021, 40(8): 879-886.
|
| [3] |
(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.)
|
| [4] |
靳志伟, 周代数. 政府投资基金融资网络特征:城市分布、网络关系与社区发现[J]. 科技进步与对策, 2022, 39(5): 40-49.
|
| [4] |
(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.)
|
| [5] |
龙浩, 张书奎, 张力. 群智感知网络中基于社会关系的社区发现算法[J]. 计算机工程与应用, 2020, 56(15): 179-184.
doi: 10.3778/j.issn.1002-8331.1906-0194
|
| [5] |
(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
|
| [6] |
端祥宇, 袁冠, 孟凡荣. 动态社区发现方法研究综述[J]. 计算机科学与探索, 2021, 15(4): 612-630.
doi: 10.3778/j.issn.1673-9418.2008023
|
| [6] |
(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
|
| [7] |
张鑫, 刘秉权, 王晓龙. 复杂网络中社区发现方法的研究[J]. 计算机工程与应用, 2015, 51(24): 1-7.
|
| [7] |
(Zhang Xin, Liu Bingquan, Wang Xiaolong. Research on Community Detection Methods in Complex Network[J]. Computer Engineering and Applications, 2015, 51(24): 1-7.)
|
| [8] |
张海涛, 周红磊, 张鑫蕊, 等. 在线社交网络的社区发现研究进展[J]. 图书情报工作, 2020, 64(9): 142-152.
doi: 10.13266/j.issn.0252-3116.2020.09.016
|
| [8] |
(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.
|
| [10] |
李东, 程鸣权, 徐杨, 等. 基于平均互信息的最优社区发现方法[J]. 中国科学: 信息科学, 2019, 49(5): 613-629.
|
| [10] |
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.)
|
| [11] |
杨旭华, 王磊, 叶蕾, 等. 基于节点相似性和网络嵌入的复杂网络社区发现算法[J]. 计算机科学, 2022, 49(3): 121-128.
doi: 10.11896/jsjkx.210200009
|
| [11] |
(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.
|
| [13] |
陈湘涛, 赵美杰, 杨梅. 基于子图结构的局部社区发现算法[J]. 计算机科学, 2021, 48(9): 244-250.
doi: 10.11896/jsjkx.201100010
|
| [13] |
(Chen Xiangtao, Zhao Meijie, Yang Mei. Overlapping Community Detection Algorithm Based on Subgraph Structure[J]. Computer Science, 2021, 48(9): 244-250.)
doi: 10.11896/jsjkx.201100010
|
| [14] |
林穗, 陈仕双, 姜文超, 等. 基于三级邻居影响力分析的重叠社区发现算法[J]. 计算机工程与设计, 2022, 43(7): 1924-1929.
|
| [14] |
(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.
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
