图匹配作为图计算中一种基本操作,是图数据处理领域中一项重要的研究内容,在生物学、信息学、社会学等重点领域均得到广泛的研究与应用。近年来,许多国内外学者对图匹配方法进行了广泛的研究。这些研究主要可以分为三类问题:(1)在静态图中查询静态子图;(2)在动态图中查询静态子图;(3)在动态图中查询动态子图。本文的研究内容属于第三类问题。在现有的研究动态图中查询动态子图的工作中,存在两点主要问题:(1)很多方法都是用一组快照来表示一个动态图,从而丢失了事件的时间关联信息。(2)返回过多的匹配结果,使用户难以在结果图中快速找到真正需要的内容。本文将动态图的定义改进为时态图并给出了时态图中具有时间约束的图匹配问题的定义。在时态图中,每一条边在特定的时间段内存在,比快照图显示出更多的关联信息。同时,本文改进了动态图匹配的形式化定义,增加了两种时间约束来过滤匹配的结果。基于上述改进,本文给出了两个解决方案。(1)基于点映射的图匹配方案TCGPM-V。该方案包含四个步骤:点映射、构建图、穷举时态图、验证时态图。(2)为提高查询效率,给出了基于边映射的图匹配方案TCGPM-E。该方案包含六个步骤:选择中心边、计算查询图半径、计算映射边集、分解数据图、边映射、穷举和验证时态图。本文在Contact、Social Pattern、SEQ、Patents等多个真实数据集上对上述方法进行了评测,同时与Ullman、VF2、Graph QL等现有方法进行了比较。实验结果表明时态图中具有时间约束的图匹配方法所得到结果的有效性明显提高。使用剪枝策略后的方法具有较高的查询效率。