大型网络中近似子图匹配研究  

Research of Approximate Subgraph Matching in Large Scale Network

作　　者：黄云[1,2] 洪佳明[2] 覃遵跃[1,2] 

机构地区：[1]吉首大学软件学院,湖南张家界427000 [2]中山大学信息科学与技术学院,广州510006

出　　处：《计算机工程》2012年第18期50-52,56,共4页Computer Engineering

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

关 键 词：近似匹配 K-近邻 标签权重 顶点匹配度 生成树匹配 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]