摘要： 为降低噪声对近似子图匹配准确率的影响，提出一种改进的近似子图匹配方法。在预处理阶段，利用k-近邻顶点集为数据图中的每个顶点建立标签-权重向量索引。在查询过程中，基于单个近邻标签的权重距离和所有近邻标签的整体匹配程度进行两级过滤，生成顶点候选集，采用生成树匹配和图匹配的方式确定查询图在大型网络中的位置。在真实数据集上的实验结果表明，该方法具有较高的执行效率和匹配准确率。

关键词: 近似匹配, k-近邻, 标签权重, 顶点匹配度, 生成树匹配

Abstract: Aiming at the accuracy for the impact of noise on the matching problem, this paper proposes an improved approximate subgraph matching method. In the preprocessing stage, it uses k-nearest neighbor graph for the vertices data set to establish a label-weight vector index. In the query process, it uses a single label weighting distance and the matching of the vertex’s all neighbors for two levels matching filter to generate a candidate set of vertices; then spans tree matching and graph matching query graph in the process of determining the positioning of large networks. Experimental result on real data sets shows that the algorithm runs efficiently and it has higher accuracy.

Key words: approximate matching, k-neighbor, label weight, vertex matching degree, spanning tree matching

中图分类号: 

• TP391.4