检索
E-mail
RSS
作者投稿和查稿 主编审稿 专家审稿 编委审稿 远程编辑

计算机工程 ›› 2012, Vol. 38 ›› Issue (18): 50-52.doi: 10.3969/j.issn.1000-3428.2012.18.013

• 软件技术与数据库 • 上一篇    下一篇

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

黄 云1,2，洪佳明2，覃遵跃1,2   

  1. (1. 吉首大学软件学院，湖南 张家界 427000；2. 中山大学信息科学与技术学院，广州 510006)
  • 收稿日期:2011-11-17 修回日期:2012-01-11 出版日期:2012-09-20 发布日期:2012-09-18
  • 作者简介:黄 云(1976－)，男，讲师、博士研究生，主研方向：数据挖掘；洪佳明，博士研究生；覃遵跃，副教授、博士研究生

Research of Approximate Subgraph Matching in Large Scale Network

HUANG Yun 1,2, HONG Jia-ming 2, QIN Zun-yue 1,2   

  1. (1. School of Software, Jishou University, Zhangjiajie 427000, China; 2. School of Information Science and Technology, Sun Yat-Sen University, Guangzhou 510006, China)
  • Received:2011-11-17 Revised:2012-01-11 Online:2012-09-20 Published:2012-09-18

PDF

2088

被引次数

6 | 1

摘要： 为降低噪声对近似子图匹配准确率的影响，提出一种改进的近似子图匹配方法。在预处理阶段，利用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

中图分类号: