Application of spectrum and Kuhn-Munkres
algorithm in graph matching

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

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

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

Application of spectrum and Kuhn-Munkres

algorithm in graph matching

[J]. Computer Engineering & Science.

[1]	GUO Ying-jiang，XU Wei-hong，CHEN Yuan-tao，WEN Ze-lin. A novel Gk-prototypes clustering algorithm [J]. Computer Engineering & Science, 2019, 41(09): 1693-1699.
[2]	LIU Hanqiang，ZHANG Qing. An interval fuzzy spectral clustering algorithm for image segmentation [J]. Computer Engineering & Science, 2018, 40(09): 1611-1616.

PDF