Paper Info
Title
Investigation of incremental hybrid genetic algorithm with subgraph isomorphism problem
Abstract
Graph pattern matching is a key problem in many applications which data is represented in the form of a graph, and this problem is generally defined as a subgraph isomorphism. In this paper, we analyze an incremental hybrid genetic algorithm for the subgraph isomorphism problem considering various design issues to improve the performance of the algorithm. An incremental hybrid genetic algorithm was previously suggested to solve the subgraph isomorphism problem and have shown good performance. It decomposes the problem into a sequence of consecutive subproblems which has an optimal substructure. Each subproblem is solved by the hybrid genetic algorithm and the solutions obtained are extended to be applied to the next subproblem as initial solutions. We examine a wide range of schemes that determine the overall performance of the incremental process and make a number of experiments to verify the effectiveness of each scheme with the synthetic dataset of random graphs. We show that the performance of incremental approach can be significantly improved compared to the previous representative studies by applying appropriate schemes found by the experiments. In addition, we also investigate the effect of different genetic parameters and identify the scalability of our method by conducting experiments using real world dataset with large-sized graphs.
Year
DOI
Venue
2019
10.1016/j.swevo.2019.05.004
Swarm and Evolutionary Computation
Keywords
Field
DocType
Incremental genetic algorithm,Hybrid genetic algorithm,Subgraph isomorphism problem
Graph,Graph pattern matching,Optimal substructure,Random graph,Computer science,Algorithm,Subgraph isomorphism problem,Genetic algorithm,Scalability
Journal
Volume
ISSN
Citations 
49
2210-6502
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Hyukgeun Choi172.00
Jinhyun Kim201.35
Yourim Yoon318517.18
Byung-Ro Moon484458.71