Information Technology Reference
In-Depth Information
Ta b l e 3 .
Correlations between three aesthetics:
r
(En
,
Cr),
r
(En
,
Ang),
r
(Cr
,
Ang) stand for
the correlation coefficients
r
between the layoutenergy En,thenumber of crossings Cr,and
the average crossing angle Ang. Absolute values between 0
.
7 and 1
.
0 indicate a strong relation-
ship (highlighted), while absolute values between 0
.
3 and 0
.
7 indicates a moderate relationship.
Negative values indicate a negative correlation.
MDS
force-directed
graph
r
(En
,
Cr)
r
(En
,
Ang)
r
(Cr
,
Ang)
r
(En
,
Cr)
r
(En
,
Ang)
r
(Cr
,
Ang)
GD
0
.
64
0
.
00
0
.
26
0
.
59
−
0
.
02
−
0
.
39
Recipes
0.81
−
0
.
27
−
0
.
15
0
.
61
−
0
.
13
−
0
.
13
Trade
0.91
-0.82
-0.83
0
.
62
0
.
02
−
0
.
24
Universities
0
.
68
−
0
.
53
−
0
.
56
0
.
66
−
0
.
09
−
0
.
16
SODA
0
.
67
−
0
.
69
−
0
.
07
0
.
54
−
0
.
16
0
.
10
IPL
0.82
−
0
.
37
−
0
.
12
0.72
−
0
.
11
−
0
.
04
TA R J A N
0
.
62
−
0
.
02
−
0
.
08
0
.
54
−
0
.
10
−
0
.
04
SOCG
0
.
22
−
0
.
64
−
0
.
04
0.72
−
0
.
61
−
0
.
11
ALGO
0
.
41
−
0
.
47
0
.
15
0.78
−
0
.
64
−
0
.
28
i,j
∈
V
by
||
p
i
−
p
j
||
. The energyofthegraph layout is measured by
d
ij
)
2
,
w
ij
(
||
p
i
−
p
j
|| −
(1)
i,j∈V
where
d
ij
is the ideal distance between vertices
i
and
j
,and
w
ij
is a weight factor.
Typically an ideal distance
d
ij
is defined as the length of the shortest path in
G
between
i
and
j
. Lower stress values correspond to a better layout. We use the conventional
weighting factor of
w
ij
=
1
d
ij
.
We runthetwoalgorithms
fdp
and
neato
on 9 graphs for 1
,
000 times on each
graph. As in Section 3.2, we vary the initial layouttoproduce different drawingsof
the same graph. For each run, we measure stress, the number of edge crossings, and the
average of all crossing angles of the layout. Note that Huang et al. [14] use the minimum
crossing angle; in our dataset the minimumvalues range from 0
.
1 to 0
.
9 degrees and
so the averageangle provides a wider range. Then we consider the computed values
for each graph as three random variables and compute the pairwise Pearson correlation
coefficients; see Table 3.
The results indicate that there is a moderate positive correlation between the number
of crossings and the energy of the layoutforall9 graphs processed with the force-
directed algorithm and for 7 graphs processed with MDS. This means that there is a
tendency for low-energydrawings to have fewer number of crossings (and vice versa).
The effect is illustratedinFig. 3, where crossings and energy are calculated for the
Recipes
dataset. We note here that the force-directed algorithm
fdp
(unlike
neato
)
is not designed to reduce the energyfunction as defined by Equation (1). Yet the number
of crossings is steadily correlated with the energy. This experimental evidence partially
supports the observation of Dwyer et al. [5], who show that users prefer graph layouts
with lower stress.
