Information Technology Reference
In-Depth Information
transcription graph. This fact assures that the algorithm will actually stop for
any input because if it is not possible to reach the end vertex from a segment by
a sequence of segments with a weight less then
l
considering the already minimal
length of a path, the whole branch is removed from the transcription graph.
When the process finishes the resulting transcription graph represents either
a network of all paths initiated in the start vertex and terminated in the end
vertex with a length lower or equal to the predefined
l
and some paths longer
than
l
due to the nature of the graph segmentation. All that with respect to the
paths that are in the indexed graph. If there are no paths shorter than
l
between
the start and end vertex the resulting transcription graph will have only two
vertices and no edges.
The more detailed insight into the transcription graph principles and its tran-
scription strategies, that is beyond the scope of this chapter can be found in [6].
10.5
Experimental Evaluation
In this section we present and discuss the results gained by the indexing struc-
ture and its search algorithm introduced in this chapter. As a testing data we
have used generated synthetic data which's properties are described later in this
section.
As follows, the set of experiments performed took as a testing data generated
graphs having sizes growing from 5,000 to 30,000 vertices and from 10,000 to
60,000 edges. The graphs were generated iteratively using a small core graph in
the first step. In each iteration a smaller graph was enlarged by randomly adding
edges between newly added vertices or between a new vertex and an old vertex
with a random direction. The probability of where the edge was placed was equal
to the proportion of the number of vertices in the smaller graph to the number
of vertices in the newly built graph. In the rest of this chapter we will refer to
these graphs as G5000, G10000, G20000 and G30000 with respect to the number
of vertices contained in the testing graph. The vertex degree distribution of the
testing graphs is illustrated in Figures 10.6, 10.7, 10.8 and 10.9.
This way we gained graphs with different sizes and having the property that
the smaller graph is always a subgraph of any of the larger graphs. This property
is very important when we evaluate the experiments that compare the search
1400
1400
1000
inDegree
outDegree
degree
900
1200
1200
800
1000
1000
700
600
800
800
500
600
600
400
400
400
300
200
200
200
100
0
0
0
0
2
4
6
8
10
12
0
2
4
6
8
10
0
2
4
6
8
10 12 14 16 18
indegree
outdegree
total degree
Fig. 10.6.
Vertex degree distribution in the synthetic graph G5000
