作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2019, Vol. 45 ›› Issue (1): 159-164. doi: 10.19678/j.issn.1000-3428.0049128

• 人工智能及识别技术 • 上一篇    下一篇

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

郭旭超1,王鲁1,郝霞2,孙晓勇1,孙博1   

  1. 1.山东农业大学 信息科学与工程学院,山东 泰安 271018; 2.中国农业大学 信息与电气工程学院,北京 100083
  • 收稿日期:2017-10-30 出版日期:2019-01-15 发布日期:2019-01-15
  • 作者简介:郭旭超(1992—),男,硕士研究生,主研方向为遗传算法、复杂网络、数据挖掘;王鲁(通信作者),副教授、硕士;郝霞,博士研究生;孙晓勇,副教授、博士;孙博,讲师、博士
  • 基金资助:

    国家自然科学基金重大研究计划(91746104);山东农业大学重点培育学科(计算机科学与技术)建设项目

Study of Community Mining Based on Improved Genetic Algorithm

GUO Xuchao 1,WANG Lu 1,HAO Xia 2,SUN Xiaoyong 1,SUN Bo 1   

  1. 1.College of Information Science and Engineering,Shandong Agricultural University,Taian,Shandong 271018,China; 2.College of Information and Electrical Engineering,China Agricultural University,Beijing 100083,China
  • Received:2017-10-30 Online:2019-01-15 Published:2019-01-15

摘要:

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

关键词: 复杂网络, 社区挖掘, 遗传算法, 结构相似度, 轮盘赌选择法

Abstract:

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.

Key words: complex network, community mining, Genetic Algorithm(GA), structural similarity, roulette selection method

中图分类号: