图数据是大数据时代中十分重要的角色,其在各种场景中有着十分广泛的应用,如社交网络、蛋白质交互网络、合作关系网络等。本文主要研究的是图数据上的模式挖掘,研究目的是实现从图数据中挖掘频繁近似子图。目前在频繁子图挖掘领域的工作已经有很多,然而已有的工作要么没有考虑子图与其出现的相似程度,要么在考虑相似程度时忽略了候选子图大小对相似程度的影响。然而,根据人的感知,不同大小的图应具有不同程度的容错性,类似的,子图的大小对计算子图与其出现的相似程度也会有十分重要的影响。因此,本文设计了子图大小相关的频繁近似子图挖掘策略,提出了一种新的、快速的频繁近似子图挖掘算法。算法不仅在计算子图的频繁程度时考虑与子图的近似出现,同时在计算子图与其出现的相似程度时,考虑子图的大小对近似程度的影响。首先,对于候选频繁近似子图的生成,本文设计了一种不遗漏的遍历方式,遍历给定单图的全部子图。为了提高遍历的效率,降低候选频繁近似子图的数量,对频繁近似子图的大小上限进行了估算,并利用大小上限过滤遍历中的子图,对遍历过程进行剪枝。实验证明了子图的上限对遍历效率具有提升效果。其次,为提高算法效率,本文归纳出对于所有的频繁近似子图,其支持度符合“局部反单调性”,且在文中给出了证明。并利用该性质,设计了对候选频繁近似子图进行剪枝的策略,降低了需要进行近似匹配的候选子图的数量。实验证明,该性质对可以显著提升算法效率。再次,对于候选频繁近似子图的近似子图生成,本文设计了基于点和边的删除策略的近似子图生成算法。并通过理论证明,仅通过统计该算法产生的近似子图在给定图中的匹配,并计算这些匹配的支持度,可以得到与统计候选频繁近似子图的所有近似匹配相同的支持度。接着,通过与已有算法的实验对比,证明本文算法在效率上具有明显优势,同时,通过简单案例说明,本文算法能发现传统频繁子图挖掘算法无法发现的频繁子图,进一步表明在挖掘频繁子图时考虑近似关系,与子图大小对近似程度的影响的必要性。最后,修改本文算法,提出了针对频繁闭合近似子图和频繁极大近似子图的挖掘算法,提高了本文研究的完整性,扩展了算法应用场景,并通过实验证明了两种算法的有效性。