基于改进Louvain算法的社区检测及核心节点发现研究

doi:10.3969/j.issn.1671-1122.2025.12.009

摘要/Abstract

摘要：

在社区检测背景下，文章提出一种基于改进Louvain算法的社区检测方法，并通过构建综合评分模型结合多个中心性指标对社区中的核心节点进行了深入挖掘。改进后的算法通过合并冗余边和优化节点划分，显著提升了社区检测的精度和效率。在综合评分模型的权重选取上，文章引入粒子群算法以降低搜索复杂度，从而进一步提高了模型在核心节点识别中的性能。文章利用多个数据集网络验证了所提方法的有效性，实验结果显示，改进后的Louvain算法在复杂网络中具有更好的社区结构识别能力。同时，通过比较不同中心性指标的核心节点识别效果，发现综合评分模型结合粒子群优化算法在信息传播和节点重要性评估上具有明显优势。这一研究成果为社区检测和核心节点识别提供了有效的技术手段，并具备进一步扩展到更大规模网络的潜力。

关键词: 社区检测, 核心节点, Louvain, 粒子群

Abstract:

In the context of community detection, this paper proposed a community detection method based on the improved Louvain algorithm, and conducted in-depth mining of core nodes in the community by constructing a comprehensive scoring model combined with multiple centrality indicators. The improved algorithm significantly improved the accuracy and efficiency of community detection by merging redundant edges and optimizing node division. In the weight selection of the comprehensive scoring model, the particle swarm algorithm was introduced to reduce the search complexity, thereby further improving the model’s performance in core node identification. In the experiment, this paper used multiple data set networks to verify the effectiveness of this method. The results show that the improved Louvain algorithm has better community structure identification capabilities in complex networks. At the same time, by comparing the core node identification effects of different centrality indicators, it was found that the comprehensive scoring model combined with the particle swarm optimization algorithm has obvious advantages in information dissemination and node importance assessment. This research result provides an effective technical means for community detection and core node identification, and has the potential to be further expanded to larger-scale networks.

Key words: community detection, core node, Louvain, particle swarm

中图分类号:

TP309

刘大禾, 修佳鹏, 杨正球. 基于改进Louvain算法的社区检测及核心节点发现研究[J]. 信息网络安全, 2025, 25(12): 1936-1947.

LIU Dahe, XIU Jiapeng, YANG Zhengqiu. Research on Community Detection and Core Node Discovery Based on Improved Louvain Algorithm[J]. Netinfo Security, 2025, 25(12): 1936-1947.

图/表 9

表1

表2

表3

图1

图2

表4

图3

图4

图5

参考文献 35

[1]	CHRISTENSEN A P, GARRIDO L E, GUERRA-PENA K, et al. Comparing Community Detection Algorithms in Psychometric Networks: A Monte Carlo Simulation[J]. Behavior Research Methods, 2023, 56(3): 1485-1505. doi: 10.3758/s13428-023-02106-4 pmid: 37326769
[2]	YANG Yu, LONG Yong, GUI Linbin, et al. Based on Spectral Clustering Dynamic Community Discovery Algorithm Research in Temporal Network[C]// IEEE. 2023 International Conference on Pattern Recognition, Machine Vision and Intelligent Algorithms (PRMVIA). New York: IEEE, 2023: 132-136.
[3]	WANG Hongwei, LESKOVEC J. Unifying Graph Convolutional Neural Networks and Label Propagation[EB/OL]. (2020-02-17)[2024-12-08]. http://arxiv.org/abs/2002.06755.
[4]	KANKHAM S, HOU Jianren. Community Notes vs. Related Articles: Assessing Real-World Integrated Counter-Rumor Features in Response to Different Rumor Types on Social Media[J]. International Journal of Human-Computer Interaction, 2024: 103-110.
[5]	CHEN Zhiyuan, HOU Bingxu, YANG Xuan, et al. Industry Community and Core Industry Detection Based on Electricity Consumption Data[C]// IEEE. 2021 IEEE 5th Conference on Energy Internet and Energy System Integration (EI2). New York: IEEE, 2021: 3031-3035.
[6]	LI Shiling, LUO Jie, XU Jiaming. Study on Regional Traffic Sub-Area Division Based on Improved Louvain Algorithm and Correlation Degree[C]// IEEE. 2022 China Automation Congress (CAC). New York: IEEE, 2022: 3522-3527.
[7]	XIAO Bo, XU Chenyue, LI Shengguang, et al. A Weakly Supervised Abnormal Behavior Detection Method with Multi-Scale Features[J]. Journal of Chinese Computer Systems, 2024, 45(10): 1474-1481.
	肖波, 许辰月, 李胜广, 等. 融合多尺度特征的弱监督异常行为检测方法[J]. 小型微型计算机系统, 2025, 45 (10): 1474-1481.
[8]	NADIA L, DOUNIA L, AHMED D E M. Enhancing Vaccination Strategy Effectiveness in Epidemic Networks: Exploring a New Centrality Measure and Community Detection Methods[C]// IEEE. 2023 10th International Conference on Wireless Networks and Mobile Communications (WINCOM). New York: IEEE, 2023: 1-6.
[9]	RAHU L, SRIVASTAVA S, KUMAR P. Comparative Study of Clustering Approaches in Rumor Source Localization Algorithm in Social Networks[C]// IEEE. 2020 International Conference on Electronics and Sustainable Communication Systems (ICESC). New York: IEEE, 2020: 835-843.
[10]	DEVI K, TRIPATHI R. Information Diffusion within a Limited Budget Using Node Centralities and Community Detection[C]// IEEE. 2020 21st Asia-Pacific Network Operations and Management Symposium (APNOMS). New York: IEEE, 2020: 197-202.
[11]	MADHULIK A, SABHARWAL S, KAUR P. Identification of Efficient Central Nodes Using Centrality Measures within Community Structures[C]// IEEE. 2024 2nd International Conference on Disruptive Technologies (ICDT). New York: IEEE, 2024: 1062-1067.
[12]	JIN Di, YU Zhizhi, JIAO Pengfei, et al. A Survey of Community Detection Approaches: From Statistical Modeling to Deep Learning[J]. IEEE Transactions on Knowledge and Data Engineering, 2021, 35(2): 1149-1170.
[13]	WANG Jingwei, LIU Chuan, ZHAO Yukai, et al. Graph Convolutional Network Aided Inverse Graph Partitioning for Resource Allocation[J]. IEEE Transactions on Industrial Informatics, 2024, 20(3): 3082-3091. doi: 10.1109/TII.2023.3302328 URL
[14]	PARK M, FENG D W, DIGRA S, et al. Improved Community Detection Using Stochastic Block Models[EB/OL]. (2024-08-20)[2024-12-08]. http://arxiv.org/abs/2408.10464.
[15]	JIA Hongjie, DING Shifei, XU Xinzheng, et al. The Latest Research Progress on Spectral Clustering[J]. Neural Computing and Applications, 2014, 24(7): 1477-1486. doi: 10.1007/s00521-013-1439-2 URL
[16]	LU Xiaoyan, CROSS B, SZYMANSKI B K. Asymptotic Resolution Bounds of Generalized Modularity and Multi-Scale Community Detection[J]. Information Sciences, 2020, 525: 54-66. doi: 10.1016/j.ins.2020.03.082 URL
[17]	BHATTACHARJEE P, MITRA P. A Survey of Density Based Clustering Algorithms[J]. Frontiers of Computer Science, 2021, 15(1): 704-723.
[18]	QU Song, DU Yuqing, ZHU Mu, et al. Dynamic Community Detection Based on Evolutionary DeepWalk[J]. Applied Sciences, 2022, 12(22): 11464-11475. doi: 10.3390/app122211464 URL
[19]	CAI Zihao, GU Zhaodong, HE Kejing. A Self-Adaptive Density-Based Clustering Algorithm for Varying Densities Datasets with Strong Disturbance Factor[J]. Data & Knowledge Engineering, 2024, 153: 1023-1045.
[20]	SU Xing, XUE Shan, LIU Fanzhen, et al. A Comprehensive Survey on Community Detection with Deep Learning[J]. IEEE Transactions on Neural Networks and Learning Systems, 2024, 35(4): 4682-4702. doi: 10.1109/TNNLS.2021.3137396 URL
[21]	JI Xiaopeng, LI Yan, WEN Peng. Jumping Knowledge Based Spatial-Temporal Graph Convolutional Networks for Automatic Sleep Stage Classification[J]. IEEE Transactions on Neural Systems and Rehabilitation Engineering, 2022, 30: 1464-1472. doi: 10.1109/TNSRE.2022.3176004 URL
[22]	FU Xinyu, ZHANG Jiani, MENG Ziqiao, et al. MAGNN: Metapath Aggregated Graph Neural Network for Heterogeneous Graph Embedding[C]// ACM. The Web Conference 2020. New York: ACM, 2020: 2331-2341.
[23]	WANG Jia, CAO Jiannong, LI Wei, et al. CANE: Community-Aware Network Embedding via Adversarial Training[J]. Knowledge and Information Systems, 2021, 63(2): 411-438. doi: 10.1007/s10115-020-01521-9
[24]	SALHA-GALVAN G, LUTZEYER J F, DASOULAS G, et al. Modularity-Aware Graph Autoencoders for Joint Community Detection and Link Prediction[J]. Neural Networks, 2022, 153: 474-495. doi: 10.1016/j.neunet.2022.06.021 URL
[25]	FANG Hao, WANG Qu, HU Qicong, et al. MNTD: An Efficient Dynamic Community Detector Based on Nonnegative Tensor Decomposition[EB/OL]. (2024-07-26)[2024-12-08]. http://arxiv.org/abs/2407.18849.
[26]	SAHU S, KOTHAPALLI K, BANERJEE D S. Shared-Memory Parallel Dynamic Louvain Algorithm for Community Detection[C]// IEEE. 2024 IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW). New York: IEEE, 2024: 1204-1205.
[27]	GHOSH S, HALAPPANAVAR M, TUMEO A, et al. Distributed Louvain Algorithm for Graph Community Detection[C]// IEEE. 2018 IEEE International Parallel and Distributed Processing Symposium (IPDPS). New York: IEEE, 2018: 885-895.
[28]	ABBAS E A, NAWAF H N. Improving Louvain Algorithm by Leveraging Cliques for Community Detection[C]// IEEE. 2020 International Conference on Computer Science and Software Engineering (CSASE). New York: IEEE, 2020: 244-248.
[29]	KUMAR R, GURUGUBELLI S, CHEPURI S P. Identifying Core-Periphery Structures Using Graph Neural Networks[C]// IEEE. 2022 56th Asilomar Conference on Signals, Systems, and Computers. New York: IEEE, 2022: 251-255.
[30]	ZHANG Xiaolong, LUO Wenhua. Implementing Federated Learning Intrusion Detection Using Dynamic Clipping Differential Privacy[J]. Journal of Chinese Computer Systems, 2024, 45(6): 1474-1481.
	张晓龙, 罗文华. 利用动态裁剪差分隐私实现联邦学习入侵检测[J]. 小型微型计算机系统, 2024, 45(6): 1474-1481.
[31]	LIANG Zhichao, TONG Boan, LIU Hui, et al. Finding Key Nodes on Terrorist Networks through K-Shell Based on Structural Hole[C]// IEEE. 2021 2nd International Seminar on Artificial Intelligence, Networking and Information Technology (AINIT). New York: IEEE, 2021: 33-37.
[32]	AMSHI A T, SHUJian, LIULinlan. Most Powerful Node Identification in Complex Network Using a Multiperspective Approach[C]// IEEE. 2019 IEEE 5th International Conference on Computer and Communications (ICCC). New York: IEEE, 2019: 1461-1468.
[33]	WAN Liangtian, ZHANG Mingyue, LI Xiaona, et al. Identification of Important Nodes in Multilayer Heterogeneous Networks Incorporating Multirelational Information[J]. IEEE Transactions on Computational Social Systems, 2022, 9(6): 1715-1724. doi: 10.1109/TCSS.2022.3161305 URL
[34]	LI Yiwei, LI Wei. Key Node Recognition Algorithm Based on Improved K-Shell Entropy[C]// IEEE. 2024 IEEE 6th Advanced Information Management, Communicates, Electronic and Automation Control Conference (IMCEC). New York: IEEE, 2024: 916-920.
[35]	MEGHANATHAN N. Canonical Correlation Analysis of Neighborhood-Based Centrality Metrics vs. Shortest Path-Based Centrality Metrics[C]// IEEE. 2023 Congress in Computer Science, Computer Engineering, & Applied Computing (CSCE). New York: IEEE, 2023: 1433-1438.

数据集	节点数/个	边数/条	描述
Karate	34	78	俱乐部成员间的友谊关系
Dolphins	62	159	海豚的社交互动
Polbooks	105	441	政治书籍的共同购买关系
Football	115	613	大学橄榄球队的比赛
Email	1133	5351	电子邮件网络
Facebook	4039	88234	脸书中的社交圈
Twitter	81306	1768149	推特中的社交圈

数据集	GN	LV	DFL	KM	CL	IL
Karate	0.3520	0.4345	0.4435	0.3898	0.4632	0.4673
Dolphins	0.5059	0.5188	0.5383	0.4772	0.5123	0.5197
Polbooks	0.5073	0.5267	0.5211	0.5046	0.5269	0.5252
Football	0.5394	0.6044	0.6039	0.5552	0.6099	0.6112
Email	0.4328	0.5327	0.5201	0.4698	0.5567	0.6011
Facebook	0.7829	0.8349	0.8451	0.8138	0.8328	0.8531
Twitter	0.7923	0.8068	0.8101	0.8011	0.8145	0.8201

数据集	节点数 /个	原始边数/条	合并后边数/条	边减少比	LV 时间 /s	IL时间 /s
Karate	34	78	50	35.89%	0.0123	0.0095
Dolphins	62	159	98	38.49%	0.0241	0.0178
Polbooks	105	441	301	31.75%	0.0453	0.0367
Football	115	613	412	32.87%	0.0512	0.0431
Email	1133	5351	17436	31.76%	0.7851	0.6157
Facebook	4039	88234	60123	31.83%	2.9453	2.0148
Twitter	81306	1768149	1205720	31.81%	315.2345	208.4356

数据集	节点	TR	BC	K-shell	PR	TPN
Karate	Top-1	0.0808	0.0825	0.0814	0.0924	0.0803
	Top-3	0.0742	0.0738	0.0731	0.0731	0.0731
	Top-5	0.0689	0.0672	0.0672	0.0675	0.0675
Dolphins	Top-1	0.0933	0.0936	0.0932	0.0931	0.0928
	Top-3	0.0929	0.0927	0.0918	0.0923	0.0916
	Top-5	0.0911	0.0907	0.0902	0.0910	0.0899
Polbooks	Top-1	0.0497	0.0478	0.0451	0.0448	0.0440
	Top-3	0.0484	0.0453	0.0426	0.0435	0.0433
	Top-5	0.0471	0.0424	0.0415	0.0421	0.0410