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