Information Technology Reference
In-Depth Information
Thereafter, each of the segments can be represented by its path type adja-
cency matrix. A path type adjacency matrix is a modification of a usual ad-
jacency matrix known from graph theory. It is designed to represent a graph
in a path oriented way. It stores paths in its fields instead of just amounts of
those paths. Initially, in each field path type matrix contains a path consist-
ing of a single edge whenever there is an edge between two vertices in the
graph. The convenience it presents over the usual adjacency matrix is that
after the transitive closure of the path type matrix is computed - the fields
contain not just an amount of paths lying between any two vertices, but also
the paths themselves. Naturally, the mathematical operations on numbers +
and
are replaced by the respective operations on paths - set union and
concatenation.
Using the graph segmentation one large graph (
G
) can be transformed into a
smaller simplified graph (
SG
(
G
)) by identifying certain number of segments and
collapsing them into single vertices. The size of the segment by which we mean
a number of vertices in the segment can be easily controlled. If the transformed
graph is still too big to be described by its path type matrix the whole procedure
can be repeatedly applied again taking as an input the already simplified graph.
Thus we can acquire a multilevel indexing structure where each vertex represents
a graph on the lower level.
Hence, the creation of the
ρ
-index accompanies a graph segmentation fol-
lowed by a computation of the path type matrix for each segment. This step
is repeated until we get a graph that we areabletodescribebyitspathtype
adjacency matrix. A size of segments may vary on every particular level. There-
fore the maximal sizes of the segments at each level form the parameter set-
tings of the
ρ
-index. Examples of the parameter settings for
ρ
-index creation
are discussed in Section 10.5. The visual outline of the indexing structure is in
Figure 10.3.
∗
Level 3
Level 2
Level 1
one vertex
graph segment
(cluster of vertices)
Level 0
Indexed graph G
Fig. 10.3.
Structure outline of the
ρ
-index
