Research On Graph Similarity Judgment Method Based On Upper Bound Of Graph Edit Distance

As the development of science and technology and the popularity of computers,a lot of data are produced.In the field of network,mathematics,biology,chemistry,data play a vital role.Graph is a general data structure,more applications depend on graph data to represent.Because of the application of graph data becomes more and more extensive,its scale is rapidly increasing,and the data becomes more diversified and complicated.How to extract the effective information from the massive graph data has become the core problem of research.In recent years,we can find that there are more and more errors in the graph database,the academic community pays attention to how to do similarity search in the graph database to get hidden information.Similarity search of graphs plays an important role in promoting the development of database.Graph edit distance as a measure to determine the similarity between graphs is the most effective application in pattern recognition,computer vision,and biology.Graph edit distance as an effective method of measuring the similarity between two graphs,is the basis of imprecise graph matching.Imprecise graph matching has become one of the important researches in the field of pattern analysis,and we can find it everywhere.It has been verified that the graph edit distance calculation is an NP problem.Usually,the graph edit distance calculation can not be solved in the polynomial time,which is very complicated to calculate and wastes a lot of time.So how to avoid too much graph edit distance calculation has become an urgent problem to be solved.So,the academic community provides some algorithms to calculate the graph edit distance bounds,in order to improve the efficiency of computation.Although some graphs are separated from the boundary algorithm,and the computational complexity can be reduced and the efficiency is improved,there is still having room for optimization.The main contents of this paper are as follows:(1)A brief introduction to several algorithms related to the boundary of graph edit distance and their advantages and disadvantages.(2)Combining the existing algorithm of graph edit distance bound,two new methods are proposed,which can be used to optimize the existing algorithm of graph edit distance bound in two different situations,so as to reducing the time it takes to calculate.(3)Establish the probability-index map,use the probability-index map to find a better intermediary graph,and then provide two kinds of fast convergence method to solve the problem of similarity search,to further reduce the unnecessary graph edit distance computation,and achieve the purpose of improving efficiency.(4)Finally,the method proposed in this paper,through the real data set and artificial data set on the experimental study,analyze new methods from various aspects.The results show that these methods have good performance,and the experimental results also confirm the validity and feasibility of the similarity search using the new method proposed by us.