Analysis of Complex Networks

6.6 Summary and Conclusions

Graphs, which can be seen as the most general data structure in computer science, are used for object representation in the present chapter. As a basic dissimilarity measure for graphs, the concept of edit distance is applied. The edit distance of graphs is a powerful and flexible concept that has found various applications. A serious drawback is, however, the exponential complexity of GED computation. Hence using optimal, or exact, algorithms restricts the applicability of the edit distance to graphs of rather small size.

In the current chapter a suboptimal approach to GED computation is introduced (BP) that is based on Munkres' algorithm for solving the assignment problem. The proposed solution allows for the insertion, deletion, and substitution of both nodes and edges, but considers these edit operations in a rather independent fashion from each other. Therefore, while Munkres' algorithm returns the optimal solution to the assignment problem, BP yields only a suboptimal, or approximate, solution to the GED problem. However, the time complexity is only cubic in the number of nodes of the two underlying graphs. In the experimental section, optimal and approximative edit distance is computed on different graph data sets. The first finding of our work is that, although Beam, which is another suboptimal algorithm developed previously, achieves remarkable speedups compared to the exact method, BP is still much faster. Furthermore, the new approach makes ...