Information Technology Reference
In-Depth Information
and the total force exerted on node
u
is as follows:
)=
∑
(
)+
∑
v
f
total
(
u
f
att
(
u
,
v
f
re p
(
u
,
v
)+
f
gravity
(
u
)+
f
random
(
u
)
(6.11)
u
,
v
)
∈
E
∈
V
,
v
=
u
The force-directed approach determines the node positions by minimizing the
total energy of the system. However, the solution is usually sub-optimal and the
algorithm finds a local minima. Frick et al. (
1995
) added a random force in an
attempt to overcome that problem. Frick et al. also introduced a new displacement
scheme (CDV phase) in which the
δ
function is defined for each node of the
network:
δ
:
V
[
1
..
maxIterations
]
→
[
0
,
1
]
(
u
,
it Number
)
→
δ
(
u
,
it Number
)
Again, the more the algorithm has iterated, the more the nodes movements are
restricted. This function also decreases when the node rotates and/or oscillates
around a point, which allows the algorithm to converge faster.
6.2.2
Fast Force Directed Drawing
To reduce the computation times, particular nodes are extracted from the network.
These nodes must be as “central” as possible because they will represent the whole
graph. This process is repeated until the set of elected nodes is small enough to
be quickly drawn, typically several dozen nodes. This results in a hierarchy of sets
of elected nodes, from the highest set that contains only a few nodes to the lowest
set that contains all of the nodes from the original network. Let
S
0
,
S
1
,...,
S
k
be
these sets of elected nodes, then
S
0
⊃
V
. Each set of elected
nodes is then drawn in a top-down manner, i.e., from
S
k
to
S
0
, using a classical
force-directed algorithm (see Sect.
6.2.1
). To reduce the computation time, when
drawing the set
S
i
, only nodes not contained in
S
i
+
1
are taken into account so that
each node is embedded only once.
In the following section, we present a more detailed description of GRIP (
Gajer
& Kobourov
,
2002
;
Gajer, Goodrich, & Kobourov
,
2004
), one of the most popular
fast force-directed algorithm.
S
1
⊃ ...⊃
S
k
and
S
0
=
GRIP: Graph dRawing
with Intelligent Placement (
Gajer & Kobourov
,
2002
;
Gajer et al.
,
2004
):
The GRIP algorithm consists of two main steps: an extraction step and a drawing
step.
Search WWH ::
Custom Search