Ilicia Jordaan
ABSTRACT
Digraphs are used to model real world systems and therefore the need arises to be able to determine the similarity between two relatively large digraphs. This similarity is in terms of both the structure of the digraphs and the knowledge represented by their vertices and edges.
Two algorithms are presented which derive their basic functionality from the Levenshtein distance algorithm. The Levenshtein algorithm is used in string comparisons to determine similarity. These two algorithms, not only calculate the edit distance between two digraphs, but preserve the operations used to convert one digraph into the other.
The results of the two algorithms are discussed in terms their edit distance cost results and their execution speed. These results are contrasted with one another and with the Levenshtein distance algorithm adapted for representing digraphs. The results indicate that the two proposed algorithms are more accurate in terms of their edit distance calculations than the Levenshtein distance algorithm, but that the Levenshtein algorithm out performs them in terms of execution speed.
- G. Barla-Szabo, B. Watson, and D. Kourie. Taxonomy of directed graph representations. IEE Proceedings - Software, 151(6):257--264, 2004.Google Scholar
Cross Ref
- J. A. Bondy and U. S. R. Murty. Graph theory. Springer, 2008. Google ScholarDigital Library
- D. Deng, G. Li, J. Feng, and W.-S. Li. Top-k string similarity search with edit-distance constraints. In Data Engineering (ICDE), 2013 IEEE 29th International Conference on, pages 925--936, April 2013. Google ScholarDigital Library
- R. Diestel. Graph Theory. Springer-Verlag, 3 edition, 2005.Google Scholar
- Gale. "Graphs"World of Computer Science, 2007.Google Scholar
- X. Gao, B. Xiao, D. Tao, and X. Li. A survey of graph edit distance. Pattern Analysis and Applications, 13(1):113--129, 2010. Google ScholarDigital Library
- S. Hjelmqvist. Fast, memory efficient Levenshtein algorithm, 2012. Online: http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm. Accessed 25 August 2015.Google Scholar
- D. Koutra, A. Parikh, A. Ramdas, and J. Xiang. Algorithms for graph similarity and subgraph matching, 2011. Online: https://www.cs.cmu.edu/~jingx/docs/DBreport.pdf Accessed 25 August 2015.Google Scholar
- L. Marshall. A graph-based framework for comparing curricula. PhD thesis, University of Pretoria, South Africa, 2014.Google Scholar
- R. Myers, R. C. Wilson, and E. R. Hancock. Bayesian graph edit distance. IEEE Trans. Pattern Anal. Mach. Intell., 22(6):628--635, June 2000. Google ScholarDigital Library
- S. Tirthapura, D. Sharvit, P. Klein, and B. Kimia. Indexing based on edit-distance matching of shape graphs. In SPIE International Symposium on Voice, Video, and Data Communications, pages 25--36, 1998.Google Scholar
- L. Zager. Graph similarity and matching. Master's thesis, Massachusetts Institute of Technology, 2005.Google Scholar
Recommendations
Graph Similarity Using Tree Edit Distance
Structural, Syntactic, and Statistical Pattern RecognitionAbstractGraph similarity is the process of finding similarity between two graphs. Graph edit distance is one of the key techniques to find the similarity between two graphs. The main disadvantage of graph edit distance is that it is computationally ...
Graph Edit Distance or Graph Edit Pseudo-Distance?
Structural, Syntactic, and Statistical Pattern RecognitionAbstractGraph Edit Distance has been intensively used since its appearance in 1983. This distance is very appropriate if we want to compare a pair of attributed graphs from any domain and obtain not only a distance, but also the best correspondence ...
An Edit Distance Between Graph Correspondences
Graph-Based Representations in Pattern RecognitionAbstractThe Hamming Distance has been largely used to calculate the dissimilarity of a pair of correspondences (also known as labellings or matchings) between two structures (i.e. sets of points, strings or graphs). Although it has the advantage of being ...
Comments