The tremendous explosion of Big Data such as social network data has made it urgent to mine important information embedded in the huge graphs. One of the mining tasks is to discover the most frequent graph in a large graph. This task is equivalently to the subgraph isomorphism problem, which is to discover the subgraph of a large graph that is isomporphic to a small input graph. The subgraph isomorphism problem is inherently a NP-hard problem, thus an exact algorithm is impossible when graphs are huge, which are the cases these days. In this study, we reported the implementation of three heuristic optimization algorithms: simulated annealing (SA), (1+1) evolutionary algorithm, and genetic algorithm (GA). We applied these algorithms on randomly generated graphs for identifying the isomorphic subgraphs, and compared the performance of these three algorithms. Our experimental results have shown that GA performed better than the other two algorithms overall.
展开▼