Information Technology Reference
In-Depth Information
Tabl e 6. 1
Comparison of computation times based on our networks in seconds
AT 2000
AT 2004
US migration
Daily migrations
# nodes / # edges
1,525 / 16,434
1,767 / 19,353
1,716 / 9,775
1,181 / 10,829
GEM (s)
251.1
384.9
291.5
105.8
GRIP (s)
1.5
2.2
1.1
1.3
v
2
and
v
3
be
the three closest and already placed neighbors of
u
. The authors lay out
u
at the
barycenter of
v
1
,
For every other level
i
,0
≤
i
<
k
,let
u
be a vertex of
S
i
,and
v
1
,
v
2
and
v
3
that is evaluated from the graph distances between
u
and
the three neighbors.
Refinement:
To refine the placement, the authors use force-directed algorithms. For each level
i
,
1
k
, they use the well-known Kamada-Kawai algorithm (
1989
). This algorithm
takes into account the graph distances in the computation of the forces. And, for
the last filtering set
S
0
, computing all graph distances would take too much time
and/or memory space, so they apply the Fruchtermann and Reingold algorithm
(
1991
), which uses only Euclidean distances (see Sect.
6.2.1
). To further improve the
computation time, the forces applied to a vertex
v
of
S
i
include only the interactions
between
v
and its closest neighbors in
S
i
.
≤
i
<
6.2.3
Results Comparison
In this section, we compare two well-known force-directed approaches in terms of
their computation time and drawing quality.
Tab le
6.1
shows the computation times obtained with GRIP (
Gajer & Kobourov
,
2002
;
Gajer et al.
,
2004
)andGEM(
Frick et al.
,
1995
), a fast force-directed
algorithm and a classical force-directed algorithm, respectively. These networks are
2000 and 2004 international air interconnections, US migrations and French daily
migrations. Using GRIP improves the computation times by a factor of more than
100. This approach handles large networks (in this example, up to more than 1,500
nodes and 25,000 edges). The gap between the force-directed and fast force-directed
approaches is even wider when drawing networks containing hundreds of thousands
of elements.
Figure
6.3
shows drawings of 2004 international air interconnections and French
daily migrations networks by GEM (
Frick et al.
,
1995
)andGRIP(
Gajer &
Kobourov
,
2002
;
Gajer et al.
,
2004
). When looking carefully at these results, one
can see that the drawings obtained with GEM emphasize more information than
Search WWH ::
Custom Search