关键词: 子图匹配, 社区结构, 优化

Abstract: Subgraph matching is an important research problem in graph data query processing technology. In view of the inefficiency of the existing subgraph matching algorithms and the lack of general optimization methods, this paper proposes a community structure based subgraph matching optimization method (CSO). This paper first proposes two kinds of optimization strategies, namely analyzing the information of the pattern graph to reduce the amount of calculation and pruning in the process of subgraph matching with community structure information, then puts forward the CSO subgraph matching optimization method based on the structure of communities according to these strategies and analyzes it theoretically. Experimental results conducted on both real-world and synthetic data sets show CSO can accelerate subgraph matching algorithms effectively. Experimental results conducted on data sets with different sizes confirm the good scalability of CSO.

Key words: subgraph matching, community structure, optimization