Matching Algorithm Research Based On Graph Edit Distance

Graph edit distance is a kind of flexible and effective method, in the related fieldsof pattern recognition and it has many uses, however, unlike exact graph matchingmethods, the edit distance allows every node of a graph to be matched to every node ofanother graph. This flexibility makes graph edit distance particularly appropriate fornoisy data, but on the other hand increases the computational complexity in contrast tosimpler graph matching models. The time and space complexity of graph edit distanceis exponential in the number of nodes of the two involved graphs. This means that forlarge graphs the computation of edit distance is intractable.In this article, an optimization algorithm on EGED algorithm is constructed,which uses the greedy algorithm plus consideration of complexity pruning was pruningthe search tree the EGED algorithm, while using Euclidean distance to constrain thecost function. Respectively, in the experimental section of improved EGED algorithmand AGED algorithm and EGED three algorithms classification accuracy and therunning time of the algorithm performance tests by experimental observation, you candeclare the two major findings, First, based on EGED algorithm improved algorithmcompared to EGED algorithm and AGED algorithm significantly improved algorithmrunning time and reduce the operation cost of the edit so that it makes the similaritymeasure between the graphs is more effective and accurate, Second, the optimizationalgorithm based on EGED algorithm classification accuracy than EGED algorithm andAGED algorithm with satisfactory results。...