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

李昌华,李智杰,高阳

收稿日期:2016-03-10 修回日期:2016-06-20 出版日期:2017-10-25 发布日期:2017-10-25
基金资助:
基金项目：国家自然科学基金（61373112,51578439）；陕西省自然科学基金（2016JM6078）;西安建筑科技大学人才科技基
金（RC1716）

LI Chang-hua,LI Zhi-jie,GAO Yang

(School of Information and Control Engineering,Xi’an University of Architecture and Technology,Xi’an

710055,China)

Received:2016-03-10 Revised:2016-06-20 Online:2017-10-25 Published:2017-10-25

摘要：

为了对图数据库中的结构化数据进行有效的匹配分析，提出了基于全局结构相似度以及节点位置相似度的Kuhn-Munkres算法

。首先对图数据构建全局以及节点位置矩阵，全局相似度矩阵用邻接矩阵的拉普拉斯谱特征构造，位置相似度矩阵首先使用

高斯核函数进行节点相对位置的归一化计算，再利用其谱特征构造。节点位置相似度主要描述图所有节点之间的相对位置，

弥补了全局结构相似度只刻画图整体结构的不足。最后使用Kuhn-Munkres算法进行图匹配，得到二分图的最大权匹配。实验

表明，改进的Kuhn-Munkres算法有效提高了节点之间的匹配正确率。

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

Abstract:

In order to match and analyze effectively of the structured graph in the database, we present an improved

Kuhn-Munkres algorithm based on the global similarity matrix and location similarity matrix. Firstly, we

construct a global matrix and a location matrix from graph data. The global similarity matrix is constructed

with the adjacency matrix and the Laplacian spectrum of feature structures. As for the location similarity

matrix, we use the Gaussian kernel function to perform the normalized calculation of the relative position

and construct the matrix with the spectral features. The nodes location similarity matrix describes the

relative position of all nodes in the graph, which can offset the drawback of the global similarity matrix,

which means it can only depict the overall structure of the graph. Finally, we use the Kuhn-Munkres algorithm

to do graph matching, and get the maximum weight matching in bipartite graphs. Experiments show that the

improved Kuhn-Munkres algorithm can effectively enhance matching accuracy between nodes.

Key words: Kuhn-Munkres algorithm, similarity matrix, bipartite graphs, maximum weight matching

李昌华,李智杰,高阳. 图谱和Kuhn-Munkres算法在图匹配中的应用研究[J]. 计算机工程与科学.

LI Chang-hua,LI Zhi-jie,GAO Yang.

Application of spectrum and Kuhn-Munkres

algorithm in graph matching

[J]. Computer Engineering & Science.

[1]	黄乐乐1，马慧芳1,2，李宁3，余丽1. 基于二分图划分联合聚类的协同过滤推荐算法[J]. 计算机工程与科学, 2019, 41(11): 2040-2047.
[2]	刘星，唐勇. 恶意代码的函数调用图相似性分析[J]. J4, 2014, 36(03): 481-486.
[3]	夏敬华陆宝春. 一种多因素指标下基于模糊特征表示的匹配方法[J]. J4, 1999, 21(6): 9-12.

PDF