Complex Networks Community Structure Division Algorithm Based on Multi-gene Families Encoding
Complex Networks Community Structure Division Algorithm Based on Multi-gene Families Encoding
复制标题
DOI：
10.4304/jcp.8.12.3021-3026
复制
发表时间：
2013-01
期刊：
影响因子：
--
通讯作者：
Shuzhi Li;Xianmin Wang
中科院分区：
文献类型：
--
作者：
Shuzhi Li;Xianmin Wang
针对传统进化算法划分复杂网络社区时存在搜索精度低、计算时间复杂度高、易陷入局部最优解等问题，提出了一种基于多基因家族的社区结构划分算法（MGF）.该算法首先根据基因表达式编程（GEP）中MGF的编码特点，将网络实体和社区类型分别编码为两个不同的多基因家族，然后通过映射函数将两个多基因家族的关系隐式编码为一个染色体。同时，将精英迁移策略应用于整个遗传阶段，即基因选择、交叉、求逆、限制排列等，加快了收敛速度，防止了早熟现象。研究表明，该算法比传统的进化算法更有效、更准确地解决了社区划分问题。
The traditional evolutionary algorithms dividing the complex networks community have some inevitable deficiencies such as low searching accuracy, high computing time complexity, local optimal solution and so on. To address this issue, this paper proposes a novel community structure partition algorithm based on multi-gene families (MGF). First, this algorithm respectively encodes the network entities and the community types into two different multi-gene families according to the MGF’s encoding characteristics in gene expression programming (GEP), and then implicitly encodes the relationship of the two multi-gene families into a chromosome through a mapping function. Meanwhile, the elite migration strategy is applied to the whole genetic stage , that is, gene selection, crossover, inversion, restricted permutation and so on, which could speed up the convergence rate and prevent the premature phenomenon. The study shows that the algorithm proposed is more effective and accurate to solve the community division problem than the traditional evolutionary algorithms.