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

Genetic Algorithm for Community Detection Accelerated by Matrix Operations

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

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.