Graph Similarity Computation Method Based On Path Mapping

With the development of emerging applications, the graph as a common datastructure is used to describe the information of interrelated network system in a widerange of applications and in-depth research. With the graph more and more complexand diversified, the graph approximate matching,which plays a fundamental role inthe query processing of the graph database, is becoming one of the important branchof graph data management and mining study. This thesis study for the graphapproximate matching algorithm and graph similarity searching method, andsummarize the main ideas of the advantages and disadvantages of the current methods,and proposes a improved graph similarity computation method as the basis for mapapproximate match. The main idea of the thesis includes the following:(1) According to the contribution of the similarity of the neighbor node, animproved node similarity computation method is proposed. The method extracts nodeadjacency information as structural features, and uses the feature of similaritytransitivity. The main idea is node similarity transmitted, i.e., for two similar nodes, ifsimilar relationship exists between their adjacent nodes, then the similarity of the twonodes is enhanced.(2) The combination of topology and path weights, a path-based similaritymapping method is proposed. Using the path weights and node similarity, the methodconstructs the path similarity gradient as a path mapping conditions, only to meet athreshold, a similar path mapping is builded between the two paths.(3) An efficient graph approximate matching algorithm was proposed. Usingnode similarity computation and path-based mapping to identify the best mappingfrom the query graph to the graph database, and graph pruning algorithm is used toimprove the performance of the algorithm at the same time. Finally with the extensiveexperiments, the method given by the thesis is proved to own a high matchingaccuracy, and broad application.