O'Reilly logo

Analysis of Complex Networks by Frank Emmert-Streib, Matthias Dehmer

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

6.2 Graph Edit Distance

In this section the basic notation for graphs and graph edit distance (GED) is introduced. Let LV and LE be a finite or infinite set of labels for nodes and edges, respectively.

Definition 6.1 A graph g is a four-tuple g = (V, E, μ, ν), where V is the finite set of nodes, EV × V the set of edges, μ : VLV the node-labeling function, and ν : ELE the edge-labeling function.

This definition allows us to handle arbitrary graphs with unconstrained labeling functions. For example, the labels can be given by the set of integers, the vector space imagesn, or aset of symbolic labels L = {α, β, γ,...}. Moreover, unlabeled graphs are obtained as a special case by assigning the same label l to all nodes and edges. Edges are given by pairs of nodes (u, v), where uV denotes the source node and vV the target node of a directed edge. Undirected graphs can be modeled by inserting a reverse edge (v, u) ∈ E for each edge (u, v) ∈ E with v(u, v) = v(v, u).

Graph matching refers to the task of evaluating the similarity of graphs. There are two major versions of this task: exact and error-tolerant graph matching. The aim of exact graph matching is to determine whether two graphs or parts of them are identical in terms of structure and labels. Compared to vectors, where the determination of identical parts is trivial, exact matching of graphs is substantially more difficult ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required