|
|
 |
| |
|
|
|
Measuring Similarity between Graphs Based on the Levenshtein Distance |
|
|
|
PP: 169-175 |
|
|
|
Author(s) |
|
|
|
Bin Cao,
Ying Li,
Jianwei Yin,
|
|
|
|
Abstract |
|
|
| Graph data has been commonly used and widely researched both in academia and industry for many applications. And
measuring similarity between graphs (i.e., graph matching) is the essential step for graph searching, pattern recognition and machine
vision. At present, the most widely used approach to address the graph matching problem is graph edit distance (GED). However, the
computation complexity of GED is expensive and it takes unacceptable time when the graph becomes larger. Generally, graph could be
canonical labeled by some sort of strings and we use the depth-first search (DFS) code as our canonical labeling system. Based on DFS
codes, combining the Levenshtein distance (i.e., string edit distance, SED), we proposed a novel method for similarity measurement of
graphs. Processing and calculating the distance between two DFS codes, we turned the graph matching problem into string matching,
which gains great improvement on the matching performance. The experimental results prove its usefulness. |
|
|
|
|
|
|
|
