Research On Approximate Graph Matching Algorithm Based On Cost Matrix

Graph matching is a process to measure the similarity between two graphs.It has been widely used in many fields such as pattern recognition,social networking,and medicine.In recent decades,research scholars have proposed a large number of algorithms to solve the graph matching problem.Among them,graph editing distance has been paid more and more attention as the most commonly used method to solve graph matching problems.At present,the research on the editing distance problem of graphs is mainly divided into approximate graph editing distance and precise graph editing distance.This paper studies the matching algorithm based on approximate graph editing distance.First of all,introduces the basic knowledge related to the graph,as well as the related concepts of the graph editing distance,and briefly introduces the related algorithms and implementation process.Secondly,the problem of the lack of precision in the construction process of SFBP(Square Fast Bipartite)cost matrix is analyzed,and a new cost matrix is proposed.By calculating the sum of the addition and deletion of any two nodes in the target graph and the source graph,it is replaced with the corresponding node in the SFBP cost matrix to obtain a new cost matrix.Thirdly,the graph matching algorithm based on the new cost matrix is improved and the RC-Greedy algorithm is proposed.In the process of using the greedy strategy to select the distribution node,the existing algorithm considers the size of the node from the perspective of the cost matrix,and does not consider the size of the node in its column,and there is a problem of lack of precision.By obtaining the sub-optimal distribution nodes from the perspective of the column,the number of comparison nodes is increased,and the allocation situation is considered more comprehensively,thereby obtaining a better distribution result.Finally,compares the improved cost matrix and algorithm based on the chemical data set and artificial data set of GREYC's laboratory.