Loading...
Please wait, while we are loading the content...
Similar Documents
A Generic Graph Distance Measure Based on Multivalent Matchings
| Content Provider | CiteSeerX |
|---|---|
| Author | Sorlin, Sébastien Solnon, Christine Jolion, Jean-Michel |
| Abstract | Summary. Many applications such as information retrieval and classification, involve measuring graph distance or similarity, i.e., matching graphs to identify and quantify their common features. Different kinds of graph matchings have been proposed, giving rise to different graph similarity or distance measures. Graph matchings may be univalent – when each vertex is associated with at most one vertex of the other graph – or multivalent – when each vertex is associated with a set of vertices of the other graph. Also, graph matchings may be exact – when all vertex and edge features must be preserved by the matching – or error-tolerant – when some vertex and edge features may not be preserved by the matching. The first goal of this chapter is to propose a new graph distance measure based on the search of a best matching between the vertices of two graphs, i.e., a matching minimizing vertex and edge distance functions. This distance measure is generic in the sense that it allows both univalent and multivalent matchings and it is parameterized by vertex and edge distance functions defined by the user depending on the considered application. The second goal of this chapter is to show how to use this generic measure to model and to solve classical graph matching problems such as (sub-)graph isomorphism problem, error-tolerant graph matching, and nonbijective graph matching. 1 |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Multivalent Matchings Generic Graph Distance Measure Graph Matchings Distance Measure Edge Distance Function Edge Feature Minimizing Vertex Nonbijective Graph Matching Many Application Graph Isomorphism Problem First Goal Second Goal Information Retrieval Generic Measure Graph Distance Error-tolerant Graph Matching Classical Graph New Graph Distance Measure Common Feature Different Graph Similarity |
| Content Type | Text |
| Resource Type | Article |
