计算机工程

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

一种提高遗传算法子图挖掘效率的数据结构

刘先锋 a,b,郭林沅 a,b   

  1. (湖南师范大学 a.数学与计算机科学学院; b.高性能计算与随机信息处理省部共建教育部重点实验室,长沙 410081)
  • 收稿日期:2015-10-13 出版日期:2016-11-15 发布日期:2016-11-15
  • 作者简介:刘先锋(1964—),男,教授,主研方向为数据挖掘、电子商务;郭林沅,硕士研究生。
  • 基金项目:
    湖南省教育厅科学研究基金(16C0956);湖南省重点学科建设基金。

A Data Structure for Improving Sub Graph Mining Efficiency of Genetic Algorithm

LIU Xianfeng  a,b,GUO Linyuan  a,b   

  1. (a.College of Mathematics and Computer Science; b.Key Laboratory of High Performance Computing and Stochastic Information Processing,Ministry of Education,Hunan Normal University,Changsha 410081,China)
  • Received:2015-10-13 Online:2016-11-15 Published:2016-11-15

摘要: 为提高复杂网络中遗传算法的子图挖掘效率,在邻接表的链式结构基础上加入双树状结构,作为一种新型数据结构——邻接树。该结构中原邻接表的头结点和表结点均以AVL树的方式组织,可使时间和空间复杂度分别降低到O(lb(n2))和O(n)。以多目标遗传算法为基础进行实 验,结果表明,在生物网络和社会网络等规模较大的数据集上,邻接树的挖掘性能相比邻接表和十字链表有明显提高,并且具有较好的通用性。

关键词: 邻接树, 复杂网络, 子图挖掘, 数据结构, 遗传算法

Abstract: In order to improve the sub graph mining efficiency of Genetic Algorithm(GA) in complex network,this paper designs a new data structure,which is named Adjacency Tree(AT).There is double-tree structure in AT,which is developed from the chain structure in Adjacency List(AL).It means that the head-nodes and list-nodes of original adjacency list are both organized by AVL tree.AT reduces time complexity to O(lb(n2)) and space complexity to O(n).Based on the experiment on datasets of biological networks and social networks with Multi-objective Genetic Algorithm(MOGA),experimental result shows that AT achieves better mining performance compared with the AL and Orthogonal List(OL) in large datasets,and it also has better generality.

Key words: Adjacency Tree(AT), complex network, sub graph mining, data structure, Genetic Algorithm(GA)

中图分类号: