摘要
传统遗传算法应用于社区挖掘时初始种群划分精确度不高,且容易降低算法整体搜索性能。为此,提出一种改进的遗传算法,并将其引入到社区挖掘研究中。结合结构相似度与轮盘赌选择法,使染色体的每个基因趋向于选择结构相似度较大的邻居节点,提高初始种群的社区划分质量并加速算法收敛速度。实验结果表明,在人工基准网络中,该算法的初始种群划分精确度和模块度比传统遗传算法平均提高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.
作者
郭旭超
王鲁
郝霞
孙晓勇
孙博
GUO Xuchao;GUO Xuchao;HAO Xia;SUN Xiaoyong;SUN Bo(College of Information Science and Engineering,Shandong Agricultural University,Taian,Shandong 271018,China;College of Information and Electrical Engineering,China Agricultural University,Beijing 100083,China)
出处
《计算机工程》
CAS
CSCD
北大核心
2019年第1期159-164,共6页
Computer Engineering
基金
国家自然科学基金重大研究计划(91746104)
山东农业大学重点培育学科(计算机科学与技术)建设项目
关键词
复杂网络
社区挖掘
遗传算法
结构相似度
轮盘赌选择法
complex network
community mining
Genetic Algorithm(GA)
structural similarity
roulette selection method
