Research Of Graph Matching Based On Spectrum

With the rapid development of Internet + in all field, The graph data increases exponentially. Graph matching has played an increasingly important role in data mining, retrieval and recognition. Then, it’s quite necessary to build a low complexity and high accuracy of map matching algorithm. As the main representation in mapping characteristics, the spectrum has been widely used in the graph matching. The key of graph matching method based on spectral theory is the transformation from a problem of matching into a problem of optimal matching between the nodes. By analyzing the spectra of character matrix, so as to achieve the objective of graph matching. Besides, the spectrum theory played a key role of reduction and simplified calculation in the data preprocessing, and improve the matching efficiency of large scale map data.The research use spectrum as the main theoretical tools, conducted an in-depth study and exploration on the graph matching algorithm by analyze the extraction method of spectral feature and improvement measures. The main research contents are summarized as follows:1. Designed Laplace spectrum feature matching algorithm based on correlation matrix. Optimized the features extraction method of spectrum, introduced a concept of associated degrees matrix. Node of degrees value not only has the node of directly connection relationship description, also contains the indirect node connection points of information, with the of role and connection location information, it can make full description of each node in whole figure structure. The correlation matrix of the nodes in the graph are clear hierarchical distinctions. Based on the foundation of correlation matrix, combined with the normalization of the Laplace spectrum and its characteristic vectors, using singular value decomposition algorithm to feature matching of graph data, Experiments show that the algorithm improve the efficiency of the ratio of match.2. Designed Kuhn-Munkres algorithm based on multiple similarity matrix. The algorithm take full account of the global architectural feature and location relationship between internal node. The location similar matrix between nodes can make up the shortcoming that global similar matrix cannot express the distance of each other. Then use Kuhn-Munkres algorithm to calculate the maximum bipartite matching between graphs. The algorithm figured out the weakness that local optimization solution in bipartite matching, and take full consideration global match, finally resolves the optimal global matching of bipartite matching. Experiments show that the algorithm can achieve better matching results and improves efficiency.3. Designed a probabilistic relaxation matching algorithm based on spectral features of location. The algorithm added node space position attribute on the foundation of Laplace spectrum characteristics. which can effectively distinguish the nodes by the position information among nodes that have similar connection relation. In the probabilistic relaxation matching algorithm, numbers of iterations supported the existing matching relation. The conditional probability is introduced in the node matching, After a number of iterations, resulting in the final matching probability matrix, and the better matching feature points is obtained.