Graphics Reference
In-Depth Information
hereare basically two different approaches to making such drawings. Inthe met-
ric or embedding approach, one uses the path-length distance defined between the
vertices of the graph and tries to approximate these distances by the Euclidean dis-
tance between the points. he area of embedding graph-theoretical distances is re-
lated todistance geometry, and ithasbeen studied agreat deal recently. Inthis paper,
we adopt primarily the adjacency model, i.e., we do not emphasize graph-theoretical
distances, but we pay special attention to which vertices are adjacent and which are
not. Obviously, this is related to distance, but the emphasis is different. We use ob-
jective (loss) functions to measure the quality of the resulting embedding.
Force-directed Techniques
4.3.1
he class of graph-drawing techniques most useful for data visualization are force-
directed techniques.hisclassoftechniquesborrowsananalogyfromclassicalphysics,
with the vertices being bodies with masses that attract and repel each other due to
the presence of springs, or because the vertices have electric charges. his implies
that there are 'physical' forces pulling and pushing the vertices apart, and the opti-
mal graph layout will be one in which these forces are in equilibrium. An objective
(loss) function that captures this analogy is given next:
n
i
=
n
j
=
n
i
=
n
j
=
Q
(
X
A, B
)=
a
ij
ϕ
(
d
ij
(
X
)) −
b
ij
ψ
(
d
ij
(
X
))
(
.
)
p matrix X contains the coordinates of the n vertices in R
p
and d
ij
wherethe n
)
denotes the distances between points with coordinates x
i
and x
j
.heweightsa
ij
correspond to those in the adjacency matrix A of the graph G, while the pushing
weights B
(
X
could be derived either from the adjacency matrix or from an ex-
ternal constraint. Finally, the functions ϕ
=
b
ij
are transformations whoserole
is to impose some aesthetic considerations on the layout. For example, a convex ϕ
function will reinforce large distances by rendering them even larger and thus en-
able one to detect unique features in the data, while a concave transformation will
dampen the effect of isolated vertices. Notice that this framework can accommodate
both simple (i.e., a
ij
(ċ)
and ψ
(ċ)
) graphs. A popular force-
directed technique that employs this pull-pushframework is discussedin DiBattista
et al. (
), where the pulling is done by springs obeying Hooke's law (i.e., the force
is proportional to the difference between the distance of the vertices and the zero-
energy length of the spring), while the pushing is done by electrical forces following
an inverse square law. Variations on this physical theme are used in several other
algorithms (Fruchterman and Reingold
and references therein).
Another way of incorporating a pushing component in the above objective func-
tion is through a normalization constraint. For example, one can require that
η
,
) and weighted (i.e., a
ij
X
, and then the objective function takes the form byforming the Lagrangian:
(
)=
n
i
=
n
j
=
Q
(
X
A
)=
a
ij
ϕ
(
d
ij
(
X
)) −
λ
(
η
(
X
)−
)
(
.
)
