图谱和Kuhn-Munkres算法在图匹配中的应用研究

摘要：

为了对图数据库中的结构化数据进行有效的匹配分析,提出了基于全局结构相似度以及节点位置相似度的Kuhn-Munkres算法.首先对图数据构建全局以及节点位置矩阵,全局相似度矩阵用邻接矩阵的拉普拉斯谱特征构造,位置相似度矩阵首先使用高斯核函数进行节点相对位置的归一化计算,再利用其谱特征构造.节点位置相似度主要描述图所有节点之间的相对位置,弥补了全局结构相似度只刻画图整体结构的不足.最后使用Kuhn-Munkres算法进行图匹配,得到二分图的最大权匹配.实验表明,改进的Kuhn-Munkres算法有效提高了节点之间的匹配正确率.

关键词：Kuhn-Munkres算法、相似度矩阵、二分图、最大权匹配

所属期刊栏目：39

分类号：TP391.4(计算技术、计算机技术)

资助基金：国家自然科学基金61373112,51578439;陕西省自然科学基金2016JM6078;西安建筑科技大学人才科技基金RC1716

在线出版日期：2018-01-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：1896-1900