Information Technology Reference
In-Depth Information
Circular Tree Drawing by Simulating
Network Synchronisation Dynamics and Scaling
Farshad Ghassemi Toosi
and Nikola S. Nikolov
CSIS Department, University of Limerick, Ireland
{
farshad.toosi,nikola.nikolov
}
@ul.ie
Abstract.
We present an algorithm which produces circular-shape lay-
outs of trees by simulating synchronisation dynamics on the tree. Our
approach consists of evolving scalar dynamical values assigned to the
nodes. Then the dissimilarities between the values of each pair of nodes
are utilised to calculate the coordinates of the nodes by using a lower
bound on dissimilarities and scaling up the lower bound per iteration.
1 Introduction
We propose a new algorithm for tree drawing with a circular shape; nodes with
higher betweenness centrality are placed near the center of the circle and leaves
towards the periphery. A force-directed algorithm with a similar result has been
proposed by Bannister et al. [2]; it utilises a third
gravity force
in addition
to forces of attraction and repulsion between nodes. Our algorithm produces
similar results without introducing gravity, and the layouts take an exact circular
shape. We achieve this by simulating network synchronisation dynamics on the
tree according to a modified version of the Kuramoto model [1]. That is, we
evolve scalar (
dynamical
) variables assigned to the tree nodes according to a
rule that brings variables of connected nodes close to each other. We then use
the dissimilarities between pairs of dynamical values to compute the tree layout.
Our experimental results demonstrate that we are able to find tree layouts with
either no or a small number of edge crossings.
2 Algorithm
Consider tree
T
with a node set
V
rooted at node
v
r
with the highest betweenness
centrality. Let
w
i
be a dynamic variable assigned to node
v
i
∈
V
and let
w
i
(
t
)be
the value of
w
i
at time step
t
. We choose to have dynamic variables
with values in the interval [0
,
2
ˀ
), so that they can be interpreted as angular
coordinates of the nodes. The tree drawing algorithm we propose consists of the
following four steps.
∈{
0
,
1
,...
}
Step 0:
t
=
v
r
assign a random value
in the interval [0
,
2
ˀ
)to
w
i
(0); assign random
x
-and
y
-coordinates to all nodes;
set a lower bound
L
on the dissimilarity of a pair of dynamical variables.
ₐ
0; let
w
r
(
t
) = 0 for any
t
;foreach
v
i
Supported by the Irish Research Council (IRC) under project no. GOIPG/2014/938.
