Research On Graph Matching Algorithm Based On Large-scale Data

Graph matching is a hot issue studied in graph theory.The essence is to calculate the similarity of two graphs.Existing graph matching algorithms usually use a filtering-validation framework.Use effective filtering algorithm to reduce the node candidate space,and use subgraph isomorphism algorithm to find the matching set of the graph.The traditional graph matching algorithm mainly proposes an improved algorithm from the establishment of the index and the analysis of the features of the sub-graph.As the scale of data increases,the performance and efficiency of such algorithms are limited.Aiming at the matching problem of large-scale graph data sets,a new matching algorithm is proposed.First,for the problem of larger pattern graph in graph matching problem,by calculating the connectivity of the query graph,the pattern graph is decomposed into smaller pattern subgraphs,and the query graph is matched with the pattern subgraph to reduce the size of the graph.The impact.At the same time,in the process of graph decomposition,a filtering strategy is proposed according to the connectivity of the graph and the number of nodes,to obtain a set of pattern subgraphs that may have matching conditions.Secondly,the subgraph isomorphism test is an NP-complete problem,and comparison between graph structures is very time-consuming.Aiming at the problem of continuous backtracking of nodes in the isomorphic process of subgraphs,a graph coding method is proposed,which encodes query graphs and pattern subgraphs into numerical forms,and converts the comparison between structures into numerical comparisons Propose the corresponding filtering strategy.Finally,the proposed algorithm and IMAGS algorithm are implemented on real data sets and synthetic data sets,respectively.Through the comparison and analysis of the response time required for matching between the two,the performance of the proposed algorithm is verified.