计算机科学与探索

作者：楼昀恺，王朝坤

单位：清华大学 软件学院，北京 100084

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

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

来源：2019年第1期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2019年第1期