The Research And Application Of The Graph Similarity Description And Matching

The graph similarity and graph matching is an important research field， in themathematics problems, chemical and biological area, data mining, network applicationand many other aspects. The World Wide Web s appearance makes mass of large-scalestatistical data, graph is the most intuitive way of presenting the relationship data structure,adopted in all kinds of research and application, large-scale graph as a form ofpresentation, has very important significance in research.Graph searching and matching algorithm is belong to the graphs isomorphismproblems, usually can’t solve the problem in a polynomial time, it is a NP completeproblems, the traditional method usually has a high spending and can’t adapt to manyproblems which has a large amount of data, and the particularity of the optimizationalgorithm can t applied in the general conditions. In order to improve the efficiency ofgraph searching and matching, this paper will put forward a kind of algorithm which setup in an iterative calculation based on the graph similarity theory. The core of thealgorithm is make an iterative computation by relevant verticals and edges similarity, thenproved the convergence of the method and give the lower bound of the algorithm s timeexpense, and change the iteration update formula to matrix form and simplify them. Thencompute the similarity description of the all vertexes and edges and improve the efficiencyby some simplified method. At last compute the similarity score between two graphs.This paper will also give an application example of software comparability research,and compute the similarity between double kinds of software based on the class diagrammatching results, through two sets of experiment of vertical and horizontal contrast, theexperimental results show the feasibility and effectiveness of the algorithm proposed inthis paper.