Analysis of Complex Networks

6.3 Computation of GED

Unlike exact graph matching methods, the edit distance for graphs allows every node of a graph to be matched to every node of another graph. This flexibility makes GED particularly appropriate for noisy data but is, on the other hand, computationally more expensive than simpler graph matching models. One can distinguish two computation paradigms for GED, viz. optimal and approximate or suboptimal GED algorithms. The former approach always finds a solution that represents the minimum cost edit path between two given graphs. Consequently, the time and space complexity of optimal GED is exponential in the number of nodes of the two involved graphs. That is, for large graphs the computation of edit distance is intractable. The latter computation paradigm addresses the GED problem by only ensuring to find a local minimum of the matching costs. Often this minimum is not very far from the global one, but this property cannot be guaranteed. If such an approximation of the edit distance is acceptable in a certain application, then the subopotimality can be traded for a shorter, usually polynomial, matching time [13].

6.3.1 Optimal Algorithms

The computation of the exact edit distance is usually carried out by means of a tree search algorithm that explores the space of all possible mappings of the nodes and edges of the first graph to the nodes and edges of the second graph. A widely used method is based on the A* algorithm [24], which is a best-first search algorithm. ...