A New Data Structure For Optimization Of Genetic Algorithm In Sub Graph Mining

Recently, most of methods of data mining in complex networks are combined with sub graph mining algorithm. For the traits of large scale data and complicated structure, it may be a good strategy of using multi-objective genetic algorithm for sub graph mining. However, there is a notable problem that large scale data may costed a lot of running time and led to low utilization efficiency of hardware. Previous solutions often focus on the algorithm itself, which is not suitable for all different kinds of complex networks.In order to solve the problem, this paper will give a new kind of data structure as a breakthrough—Adjacency Tree. Adjacency Tree is based on Adjacency List, which means that the head-nodes and list-nodes of Adjacency List are both organized by AVL tree. After that, the data structure for a graph will be more efficient in running performance. The main ideas can be described as below:1 After the organization by AVL tree, the head-node will be renamed as tree-head-node, and the list-node as tree-tail-node.2 There is one pointer in every tree-head-node pointing to the root of relevant tree organized by tree-tail-nodes.3 Corresponding information is stored in Tree-head-node from the relevant head-node, as well as tree-tail-node from list-node.4 Whenever there is insertion or deletion, there is maintenance of AVL tree balance in Adjacency Tree.This paper will analyze the feasibility of Adjacency Tree, and then prove that compared with another classical graph data structure such as Adjacency Matrix, Adjacency List and Orthogonal List, Adjacency Tree has better performance. Adjacency Tree achieves lower time complexity of O(log(n2)) and space complexity of O(n). In addition, there are two kinds of experiments: one is random graphs test of insertion, deletion, searching and modification, and the other is the running performance of multi-objective genetic algorithm. Based on the results, the better comprehensive efficiency will be analyzed and testified. At last, there will be conclusion and expectation.