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

摘要： 子图匹配是图数据查询处理技术中的一个重要研究问题。针对现有子图匹配算法运行效率不高且缺乏通用优化方法的现状，提出一种基于社区结构的子图匹配算法优化方法（community structure based subgraph matching optimization method，CSO）。首先，提出两种优化策略，即解析模式图信息以减少子图匹配过程的计算量，以及利用社区结构信息在子图匹配过程中进行剪枝；然后，结合上述两种优化策略提出基于社区结构的子图匹配算法优化方法，并进行了理论分析。真实数据集和合成数据集上的大量实验结果表明，CSO方法能有效减少子图匹配算法的时间开销。同时，不同规模数据集上的实验结果验证了CSO方法良好的可扩展性。

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