Information Technology Reference
In-Depth Information
Step 1:
t
ₐ
t
+1; for each
v
i
=
v
r
with parent
v
k
calculate
w
i
(
t
) according to the
equation
dw
i
(
t
)
dt
w
i
(
t
)+
ˆ
i
(
t
) which models network synchronisation
dynamics. The term
ˆ
i
(
t
) is an adjustment which allows larger drawing space
for subtrees rooted at nodes with a relatively high degree.
Step 2:
For each pair of nodes
v
i
= sin(
w
k
(
t
))
−
=
v
j
, calculate the dissimilarity of their
cos(
w
j
(
t
)))
2
+(sin(
w
i
(
t
))
dynamic variables
dis
ij
(
t
)=max
{
L,
((cos(
w
i
(
t
))
−
−
sin(
w
j
(
t
)))
2
)
2
.
Step 3:
Update the coordinates of all nodes in force-directed manner. If
v
i
and
v
j
are adjacent then the force of attraction between them is
q
}
p
(
dis
ij
(
t
)); if
×
×
(
dis
ij
(
t
)) is the force of repulsion between
they are not adjacent then
−
1
them. The values of
q
1 grow with the size of the tree.
Step 4:
Scaling up the value of
L
at each iteration gradually and continuing
this process until layout gets stable (typically
≥
1and0
<p
≤
steps).
Figure 1 shows two trees drawn with our algorithm. The one in the left is one of
the example trees which is also drawn by Bannister et al. [2]. We have observed
that our algorithm achieves more even distribution of nodes within a circular
drawing area compared to other tree drawing algorithms. Our algorithm has the
same time complexity as the classical force-directed graph drawing algorithms,
i.e.
O
(
m
|
V
|
2
), where
m
is the number of iterations.
|
V
|
Fig. 1.
A tree with 70 nodes (right) and a tree with 82 nodes (left). Nodes have different
size and color depending on the distance to the root.
References
1. Arenas, A., Daz-Guilera, A., Prez-Vicente, C.J.: Synchronization reveals topological
scales in complex networks. Phys. Rev. Lett. 96(11), 114102-1-114102-4 (2006)
2. Bannister, M.J., Eppstein, D., Goodrich, M.T., Trott, L.: Force-directed graph draw-
ing using social gravity and scaling. In: Didimo, W., Patrignani, M. (eds.) GD 2012.
LNCS, vol. 7704, pp. 414-425. Springer, Heidelberg (2013)
