Analysis of Complex Networks

6.2 Graph Edit Distance

In this section the basic notation for graphs and graph edit distance (GED) is introduced. Let L_V and L_E 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, E⊆ V × V the set of edges, μ : V → L_V the node-labeling function, and ν : E → L_E 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 ⁿ, 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 u ∈ V denotes the source node and v ∈ V 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 ...