Information Technology Reference
In-Depth Information
Fig. 6.2
(
a
) Example of a graph containing 70 nodes and 123 edges; (
b
) Maximal set
S
1
of nodes
at distance at least 2 is shown in
red
;(
c
) Maximal set
S
2
of nodes at a distance at least 2
2
=
4is
shown in
red
;(
d
) Maximal set
S
3
of nodes at a distance at least 2
3
=
8isshownin
red
;(
e
) Maximal
set
S
4
of nodes at a distance at least 2
4
=
16 is shown in
red
(Color figure online)
Extraction Step:
The first step of the GRIP algorithm computes a
Maximal Independent Set Filtration
(MISF)
ν
of the set of vertices
V
of
G
. The filtration,
ν
,isdefinedasfollows:
ν
=
S
0
,
S
1
,...,
S
k
where
S
0
⊃
S
1
⊃ ... ⊃
S
k
⊃
0,
S
0
=
V
and
∀
i
,
0
<
i
≤
k
,
S
i
is a
maximal subset of
S
i
+
1
such that for all pairs of vertices
u
v
of
S
i
, the graph distance
between
u
and
v
is greater or equal to 2
i
. The idea is to extract the nodes at a distance
of at least 2 to represent the whole graph, then to extract the nodes at a distance of
at least 4 to represent the nodes at a distance of 2, and so on until the set of elected
nodes contains at most 3 nodes as shown in Fig.
6.2
. This process makes it possible
to compute sets of elected nodes that are well-distributed in the network.
,
Drawing Step:
During the second step of the GRIP algorithm (
Gajer & Kobourov
,
2002
;
Gajer
et al.
,
2004
), the process first places nodes of
S
k
and then each filtration set
S
k
−
1
,
S
0
. For each level, the placement is split into two phases: an
“intelligent” initial placement (i.e., nodes are placed closed to their final positions),
and then a refinement phase that uses a force-directed algorithm (either the Kamada-
Kawai (
1989
) or the Fruchterman-Reingold (
1991
) algorithm).
s
k
−
2
,...,
Intelligent Initial Placement:
For the smallest set
S
k
, the authors consider that
S
k
contains exactly 3 nodes. (If this
is not the case, then the nodes of
S
k
−
1
are included in
S
k
). Let
u
1
,
u
2
and
u
3
be the
three nodes of
S
k
, which are laid out on a triangle as follows:
dist
R
(
u
1
,
u
2
)=
dist
G
(
u
1
,
u
2
)
dist
R
(
u
1
,
u
3
)=
dist
G
(
u
1
,
u
3
)
dist
R
(
u
2
,
u
3
)=
dist
G
(
u
2
,
u
3
)
where
dist
R
(
u
,
v
)
is the Euclidean distance between
u
and
v
and
dist
G
(
u
,
v
)
is the
theoretical graph distance between them.
Search WWH ::
Custom Search