Measuring the similarity of labeled graphs Export

@inproceedings{citeulike:4008726, abstract = {Abstract. This paper proposes a similarity measure to compare cases represented by labeled graphs. We rst dene an expressive model of directed labeled graph, allowing multiple labels on vertices and edges. Then we dene 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. 1}, author = {Champin, Pierre A. and Solnon, Christine}, booktitle = {In Proceedings of the Fifth International Conference on Case-Based Reasoning}, citeulike-article-id = {4008726}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.6825}, citeulike-linkout-1 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.6825}, keywords = {case\_based\_reasoning, graph, similarity}, pages = {80--95}, posted-at = {2009-02-04 18:35:56}, priority = {2}, title = {Measuring the similarity of labeled graphs}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.6825}, year = {2003} }

TY - CONF ID - citeulike:4008726 L3 - citeulike-article-id:4008726 N2 - Abstract. This paper proposes a similarity measure to compare cases represented by labeled graphs. We rst dene an expressive model of directed labeled graph, allowing multiple labels on vertices and edges. Then we dene 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. 1 EP - 95 TI - Measuring the similarity of labeled graphs T2 - In Proceedings of the Fifth International Conference on Case-Based Reasoning SP - 80 KW - case_based_reasoning KW - graph KW - similarity AU - Champin, Pierre AU - Solnon, Christine PY - 2003/// UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.6825 ER -