Graphics Reference
In-Depth Information
It then becomes clear that the constraint term in the Lagrangian corresponds to the
push component of Q
X
′
X
(ċ)
.Examplesofη
(
X
)
include η
(
X
)=
trace
(
)
or η
(
X
)=
X
′
X
det
. Other possibilities include requiring the orthonormality of the points in
the layout, such as X
′
X
(
)
I
p
or even fixing some of the Xs(Tutte,
).
Finally, this formulation allows one to incorporate into the force-directed frame-
work the metric approach of graph drawing, whereone works not with the adjacency
matrix of the graph but with a distance matrix defined on the graph G.hegoalthen
becomes to approximate graph-theoretic distances by Euclidean distances. Hence,
the goal becomes to minimize
=
n
i
=
n
j
=
Q
(
X
W
)=
w
ij
ρ
(
d
ij
(
X
))
(
.
)
where
,
ρ
(
d
ij
(
X
)) = (
η
(
δ
ij
)−
η
(
d
ij
(
X
)))
(
.
)
where W
is a set of weights. he δ
ij
correspond to path-length distances de-
finedonthegraph G,whereasthetransformation η isusually theidentity, thesquare,
or the logarithm. Obviously ρ
=
w
ij
is not increasing and does not pass through
zero; nevertheless, by expanding the square it becomes clear that it is equivalent to
minimizing Q
(
d
(
X
))
η
w
ij
.hus,
all points are pulling together, but points with large path-length distances are being
pushed apart.
Nextweexamine inmoredetail the metric or embedding approach andthepulling
under constraints model, which have proved particularly useful for drawing graphs
obtained from data.
(
X
W
)
with ϕ
(
d
)=
(
d
)
, ψ
(
d
)=
η
(
d
)
,andb
ij
=
η
(
δ
ij
)
Multidimensional Scaling
4.3.2
he metric approach previously discussed corresponds to one version of multidi-
mensional scaling (MDS). MDS is a class of techniques where a set of given dis-
tances is approximated by distances in low-dimensional Euclidean space. Formally,
let
be a set of distances. he goal is to identify the coordinates
of n points x
i
in R
p
such that the Euclidean distance d
δ
ij
, i, j
=
,...,n
(
x
i
, x
j
)
d
ij
(
X
)
is approxi-
mately equal to δ
ij
.
Asmentionedbefore,forgraph-drawingpurposes,the δ
ij
correspondtotheshort-
est path distances defined on a graph G. A discussion of MDS as a graph-drawing
technique is provided in Buja and Swayne (
), where in addition other choices
beyond Euclidean space are studied for the embedding space. he least-squares-loss
(fit) function (known in the literature as Stress) introduced in Kruskal (
) has the
form
n
i
=
n
j
=
σ
(
X
)=
w
ij
(
δ
ij
−
d
ij
(
X
))
(
.
)
