子图匹配是图论里的一个重要研究内容,目前,它已应用于社交网络分析、蛋白质相互作用网络的功能推测等诸多领域。候选匹配集初始化时,由于许多孤立的无效节点被包含在该集合中,在后续步骤中需要对这些节点进行过滤和判断,算法效率较低,因此随着网络规模的增大,算法的可扩展性较弱。除此之外,当查询图的规模增大时,常见的子图匹配算法不能在有效时间内得到合理的匹配结果。针对上述问题,本文对子图匹配算法进行了改进,具体工作如下:(1)针对子图匹配算法在大规模的目标图上的扩展性较弱的问题,本文提出了基于节点影响力的子图匹配算法(Inf SMatch,Influence-based Subgraph Match)。考虑到候选匹配集合中存在孤立节点的问题,本文提出通过考虑节点的全局和局部结构特征信息来计算查询图上所有节点的影响力,选择影响力最大的作为中心节点,此举能够大大减少初始候选集合中孤立的无效节点的数量。为了使得每个候选匹配区域尽可能的小,本文利用宽度优先搜索对子区域进行扩展,针对该扩展过程,我们还提出了更详尽的过滤策略对候选匹配集合进行进一步剪枝。除此之外,在验证阶段本文通过考虑节点的重要性以及节点间的连接性来确定节点的验证顺序。实验表明本文提出的方法比其他常见的算法效率更高。(2)针对查询图较大时子图匹配效率较低的问题,本文在InfSMatch算法的基础上提出了基于查询图分解的子图匹配改进算法QDSMatch(Query Decomposition Based Subgraph Match),并基于Spark并行计算框架对该算法进行了实现。为了减少连接开销,本文利用社区划分算法将查询图划分成多个查询子图,分别对每个查询子图进行操作,对查询结果进行连接得到同构子图。在对每个查询子图进行匹配时,本文通过计算每个查询子图的平均度数以及查询子图之间的连接性,确定了查询子图的匹配顺序。除此之外,本文还提出了一个新的过滤策略,有助于减少候选集合的数量。同时,本文利用Spark框架对QDSMatch算法进行了并行化处理。实验结果证明,最优CPU核数与查询图大小相关;与其他并行化子图匹配算法相比,QDSMatch算法更加高效。