基于矩阵运算加速的改进社区发现遗传算法

doi:10.16088/j.issn.1001-6600.2023052903

摘要/Abstract

摘要： 社区发现算法是复杂网络领域的重要研究工具,然而传统的社区发现遗传算法在大规模网络下存在初始种群质量不佳和运行效率低下的问题。为此,本文提出一种基于矩阵运算加速的改进社区发现遗传算法。针对初始种群质量不佳的问题,提出一种新的初始化算子,采用闭包系数有偏向地选择节点构建高质量初始社区;针对计算效率低下的问题,基于矩阵运算重构了传统社区发现遗传算法各个算子,使得算法能使用GPU加速,提升计算效率。仿真实验结果表明,在不同规模的真实网络和LFR合成网络下,本文算法既能保证良好的划分精度,又展现出较其他主流同类算法更高的计算效率。

关键词: 复杂网络, 社区发现, 遗传算法, 矩阵运算, 模块度

Abstract: Community detection algorithms are critical research tools in the field of complex networks. However, traditional community detection genetic algorithms have the problems with poor initial population quality and low computational efficiency under large-scale networks. To address this, an improved community detection genetic algorithm based on matrix computation acceleration is proposed. To tackle the problem of subpar initial population quality, a novel initialization operator is proposed to construct high-quality initial communities using the closure coefficient with biases node selection. To address the issue of low computational efficiency, the traditional community detection genetic algorithm operators are restructured based on matrix operations, enabling the use of GPU acceleration to enhance computational efficiency. Experimental results indicate that the proposed algorithm maintains good partitioning accuracy and demonstrates higher computational efficiency than other algorithms of the same type under different scales of real networks and LFR synthetic networks.

Key words: complex network, community detection, genetic algorithm, matrix operation, modularity

中图分类号: TP18

余谦, 陈庆锋, 何乃旭, 韩宗钊, 卢家辉. 基于矩阵运算加速的改进社区发现遗传算法[J]. 广西师范大学学报（自然科学版）, 2024, 42(2): 105-119.

YU Qian, CHEN Qingfeng, HE Naixu, HAN Zongzhao, LU Jiahui. Genetic Algorithm for Community Detection Accelerated by Matrix Operations[J]. Journal of Guangxi Normal University(Natural Science Edition), 2024, 42(2): 105-119.

参考文献

[1] 乔雨露. 基于亲和传播的复杂网络社团探测方法研究[D].南宁:广西大学,2021.DOI:10.27034/d.cnki.ggxiu.2021.000715.
[2] 黄杰,武瑞梓,李均利.进化算法在复杂网络中的应用综述[J].计算机系统应用,2023,32(4):16-41. DOI:10.15888/j.cnki.csa.009037.
[3] 刘扬,郑文萍,张川,等.一种基于局部随机游走的标签传播算法[J].计算机科学,2022,49(10):103-110.DOI:10.11896/jsjkx.220400145.
[4] 曾祥宇,龙海霞,杨旭华.基于马尔可夫相似性增强和网络嵌入的社区发现[J].计算机科学,2023,50(4):56-62.DOI:10.11896/jsjkx.220100155.
[5] 杨煜,段威威.基于谱聚类的社交网络动态社区发现算法[J].计算机应用,2023,43(10):3129-3135. DOI:10.11772/j.issn.1001-9081.2022101517.
[6] 付立东,刘佳会,王秋红.基于密度峰值的标签传播社区发现算法[J].计算机应用研究,2023,40(8):2323-2328. DOI:10.19734/j.issn.1001-3695.2002.12.0796.
[7] 刘志远. 复杂网络中的社团探测研究及应用[D].济南:山东师范大学,2020.DOI:10.27280/d.cnki.gsdsu.2020.002123.
[8] JAVEDM A, YOUNIS M S, LATIF S, et al. Community detection in networks: a multidisciplinary review[J]. Journal of Network and Computer Applications, 2018, 108: 87-111.DOI: 10.1016/j.jnca.2018.02.011.
[9] BUI T N, JONES C. Finding good approximate vertex and edge partitions is NP-hard[J]. Information Processing Letters, 1992, 42(3): 153-159. DOI: 10.1016/0020-0190(92)90140-Q.
[10] GUO X C, SU J, ZHOU H, et al. Community detection based on genetic algorithm using local structural similarity[J]. IEEE Access, 2019, 7: 134583-134600.DOI: 10.1109/ACCESS.2019.2939864.
[11] 李萍,汪芬,陈祺东,等.求解多目标社区发现问题的离散化随机漂移粒子群优化算法[J].计算机应用,2021,41(3):803-811.DOI:10.11772/j.issn.1001-9081.2020060800.
[12] 顾军华,江帆,武君艳,等.基于标签传播的蚁群优化算法求解社区发现问题[J].计算机应用与软件,2019,36(6):233-242.DOI: 10.3969/j.issn.1000-386x.2019.06.043.
[13] TASGIN M, HERDAGDELEN A, BINGOL H. Community detection in complex networks using genetic algorithms[EB/OL]. (2007-11-04)[2023-05-29].https://arxiv.org/abs/0711.0491.DOI: 10.48550/arXiv.0711.0491.
[14] CHEN K Q, BI W H. A new genetic algorithm for community detection using matrix representation method[J]. Physica A: Statistical Mechanics and its Applications, 2019, 535: 122259. DOI:10.1016/j.physa.2019.122259.
[15] SAID A, ABBASI R A, MAQBOOL O, et al. CC-GA: a clustering coefficient based genetic algorithm for detecting communities in social networks[J]. Applied Soft Computing, 2018, 63: 59-70.DOI: 10.1016/j.asoc.2017.11.014.
[16] SHISHAVAN S T, GHAREHCHOPOGH F S. An improved cuckoo search optimization algorithm with genetic algorithm for community detection in complex networks[J]. Multimedia Tools and Applications, 2022, 81(18): 25205-25231. DOI: 10.1007/s11042-022-12409-x.
[17] SHAKYA H K, SINGH K, MORE Y S, et al. Opposition-based genetic algorithm for community detection in social networks[J]. Proceedings of the National Academy of Sciences, India Section A: Physical Sciences, 2022, 92(2): 251-263. DOI: 10.1007/s40010-020-00716-7.
[18] GUERRERO M, MONTOYA F G, BAÑOS R, et al. Adaptive community detection in complex networks using genetic algorithms[J]. Neurocomputing, 2017, 266: 101-113. DOI: 10.1016/j.neucom.2017.05.029.
[19] MENG X Y, DONG L Y, LI Y L, et al. A genetic algorithm using K-path initialization for community detection in complex networks[J]. Cluster Computing, 2017, 20(1): 311-320. DOI:10.1007/s10586-016-0698-y.
[20] BOUKARAM W, TURKIYYAH G, KEYES D. Hierarchical matrix operations on GPUs: matrix-vector multiplication and compression[J]. ACM Transactions on Mathematical Software, 2019, 45(1): 3. DOI:10.1145/3232850.
[21] HRICIK T, BADER D, GREEN O. Using RAPIDS AI to accelerate graph data science workflows[C]// 2020 IEEE High Performance Extreme Computing Conference (HPEC).Los Alamitos, CA: IEEE Computer Society, 2020: 1-4.DOI: 10.1109/HPEC43674.2020.9286224.
[22] PASZKE A, GROSS S, MASSA F, et al. PyTorch: an imperative style, high-performance deep learning library[EB/OL]. (2019-12-03)[2023-05-29].https://arxiv.org/abs/1912.01703. DOI: 10.48550/arXiv.1912.01703.
[23] ZHAN Z H, ZHANG J, LIN Y, et al. Matrix-based evolutionary computation[J]. IEEE Transactions on Emerging Topics in Computational Intelligence, 2022, 6(2): 315-328.DOI: 10.1109/TETCI.2020.3047410.
[24] YIN H, BENSON A R, LESKOVEC J. The local closure coefficient: a new perspective on network clustering[C]// WSDM ’19: Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining. New York, NY: Association for Computing Machinery,2019: 303-311.DOI: 10.1145/3289600.3290991.
[25] NEWMAN M E J. Modularity and community structure in networks[J]. Proceedings of the National Academy of Sciences of the United States of America, 2006, 103(23): 8577-8582. DOI:10.1073/pnas.0601602103.
[26] SHI C, YAN Z Y, WANG Y, et al. A genetic algorithm for detecting communities in large-scale complex networks[J]. Advances in Complex Systems, 2010, 13(1): 3-17. DOI:10.1142/S0219525910002463.
[27] PIZZUTI C. Evolutionary computation for community detection in networks: a review[J]. IEEE Transactions on Evolutionary Computation, 2018, 22(3): 464-483.DOI: 10.1109/TEVC.2017.2737600.
[28] MAJEED A, RAUF I. Graph theory: a comprehensive survey about graph theory applications in computer science and social networks[J]. Inventions, 2020, 5(1): 10.DOI: 10.3390/inventions5010010.
[29] 汤洋,赵达非,黄智濒,等.高性能行任务散列法GPU一般稀疏矩阵-矩阵乘法[J].北京邮电大学学报,2019,42(3):106-113.DOI:10.13190/j.jbupt.2018-252.
[30] LE GALL F. Powers of tensors and fast matrix multiplication[C]// Proceedings of the 39th International Symposium on Symbolicand Algebraic Computation. New York, NY: Association for Computing Machinery,2014: 296-303.DOI: 10.1145/2608628.2608664.
[31] DOBRAVEC T, BULIĆ P. Comparing CPU and GPU implementations of a simple matrix multiplication algorithm[J]. International Journal of Computer and Electrical Engineering, 2017, 9(2): 430-438. DOI:10.17706/IJCEE.2017.9.2.430-438.
[32] ROSSI R, AHMED N. The network data repository with interactive graph analytics and visualization[J]. Proceedings of the AAAI Conference on Artificial Intelligence, 2015, 29(1):4292-4293. DOI: 10.1609/aaai.v29i1.9277.
[33] LANCICHINETTI A, FORTUNATO S, RADICCHI F. Benchmark graphs for testing community detection algorithms[J]. Physical Review E, 2008, 78(4): 046110. DOI: 10.1103/PhysRevE.78.046110.
[34] 赵卫绩,张凤斌,刘井莲.复杂网络社区发现研究进展[J].计算机科学,2020,47(2):10-20.DOI:10.11896/jsjkx.190100214.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed