基于改进遗传算法的社区挖掘研究

Study of Community Mining Based on Improved Genetic Algorithm

传统遗传算法应用于社区挖掘时初始种群划分精确度不高,且容易降低算法整体搜索性能。为此,提出一种改进的遗传算法,并将其引入到社区挖掘研究中。结合结构相似度与轮盘赌选择法,使染色体的每个基因趋向于选择结构相似度较大的邻居节点,提高初始种群的社区划分质量并加速算法收敛速度。实验结果表明,在人工基准网络中,该算法的初始种群划分精确度和模块度比传统遗传算法平均提高18%和12%,整体划分精确度比FEC和FN算法平均提高24. 02%和22. 01%,在真实世界网络中,社区划分精确度均优于FN、FEC和LPA算法,从而验证该算法具有较好的社团挖掘性能。

The partition accuracy of the initial population which is generated by the community mining based on traditional Genetic Algorithm(GA)tends to be low,which can easily lead to the poor overall search performance.To solve this problem,an improved GA is proposed and introduced into community mining study.In the algorithm,the structural similarity and the roulette wheel selection method are adopted so that each gene of chromosomes tends to choose the neighbor node with a larger structure similarity.In this way,the community partitioning quality of the initial population is improved and the convergence rate of this algorithm is accelerated.Experimental results show that in the artificial benchmark network,the partition accuracy and modularity of the initial population generated by the propose algorithm are generally increased by 18%and 12%,compared with the traditional GAs,and the overall partition accuracy of that is averagely increased by 24.02%and 22.01%compared with that of FEC and FN algorithms.In the real world network,the accuracy of community parition of the proposed algorithm is also much better than those of FN,FEC and LPA algorithms.It is verified that the algorithm has better community mining performance.