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.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. ...

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