Analysis of Complex Networks

6.4 Applications

The intention of this section is twofold. First, four different graph data sets are discussed in order to give an exemplary insight into how graphs can be used to model objects in certain applications. Secondly, two different approaches to graph-based object classification in conjunction with GED are discussed. First we make use of the edit distance for a direct classification by means of a nearest-neighbor classifier. The second approach uses the GED in order to transform graphs into feature vectors. The classification process is then carried out in the target vector space.

6.4.1 Graph Data Sets

In this section four different graph data sets with quite different characteristics are presented. They represent line drawings, grayscale images, HTML web sites, and molecular compounds. The graph data sets emerged in the context of the authors' recent work on graph kernels [38] and graph embedding [10, 45]. All graph data sets discussed in the present paper are publicly available or will be made available in the near future [43].

Letter Database The first graph data set involves graphs that represent distorted letter drawings. We consider the 15 capital letters of the Roman alphabet that consist of straight lines only (A, E, F, H, I, K, L, M, N, T, V, W, X, Y, Z). For each class, a prototype line drawing is manually constructed. These prototype drawings are then converted into prototype graphs by representing lines by undirected edges and ending points of lines by nodes. ...