Measuring the Similarity of Labeled Graphs
Measuring the Similarity of Labeled Graphs
复制标题
DOI：
10.1007/3-540-45006-8_9
复制
发表时间：
2003-06
期刊：
影响因子：
--
通讯作者：
Pierre-Antoine Champin;Christine Solnon
中科院分区：
文献类型：
--
作者：
Pierre-Antoine Champin;Christine Solnon
本文提出了一种相似性度量来比较由标记图表示的情况。我们首先定义有向标记图的表达模型，允许顶点和边上有多个标签。然后我们将相似性问题定义为最佳映射的搜索，其中映射是图的顶点之间的对应关系。我们方法的关键点是这种映射不必是单价的，因此图中的一个顶点可以与另一个图中的多个顶点相关联。另一个关键点是映射的质量由通用函数决定，可以调整通用函数以实现领域相关的知识。我们讨论了与这个问题相关的一些计算问题，并描述了它的贪心算法。最后，我们表明我们的方法不仅提供了相似性的定量测量，而且还提供了在 CBR 适应阶段有价值的定性信息。
This paper proposes a similarity measure to compare cases represented by labeled graphs. We first define an expressive model of directed labeled graph, allowing multiple labels on vertices and edges. Then we define the similarity problem as the search of a best mapping, where a mapping is a correspondence between vertices of the graphs. A key point of our approach is that this mapping does not have to be univalent, so that a vertex in a graph may be associated with several vertices of the other graph. Another key point is that the quality of the mapping is determined by generic functions, which can be tuned in order to implement domain-dependant knowledge. We discuss some computational issues related to this problem, and we describe a greedy algorithm for it. Finally, we show that our approach provides not only a quantitative measure of the similarity, but also qualitative information which can prove valuable in the adaptation phase of CBR.