A survey of graph edit distance
A survey of graph edit distance
复制标题
图形编辑距离的调查
DOI：
10.1007/s10044-008-0141-y
复制
发表时间：
2010-02-01
影响因子：
3.9
通讯作者：
Li, Xuelong
中科院分区：
文献类型：
--
作者：
Gao, Xinbo;Xiao, Bing;Li, Xuelong
不精确图匹配一直是模式分析领域的重要研究热点之一。图编辑距离(GED)作为容错度量两两图之间相似性的重要方法，是不精确图匹配的基础。本文对GED的研究进展进行了综述，以期对现有文献进行回顾，并为GED的研究提供一些启示。由于图可以是属性的，也可以是非属性的，并且编辑操作的代价的定义是不同的，所以现有的GED算法根据这两个因素进行了分类和详细的描述。在分析了这些算法的基础上，指出了它们的局限性，并提出了进一步研究的方向。
Inexact graph matching has been one of the significant research foci in the area of pattern analysis. As an important way to measure the similarity between pairwise graphs error-tolerantly, graph edit distance (GED) is the base of inexact graph matching. The research advance of GED is surveyed in order to provide a review of the existing literatures and offer some insights into the studies of GED. Since graphs may be attributed or non-attributed and the definition of costs for edit operations is various, the existing GED algorithms are categorized according to these two factors and described in detail. After these algorithms are analyzed and their limitations are identified, several promising directions for further research are proposed.