Information Technology Reference
In-Depth Information
Algorithm 1:
Hairball Drawing Algorithm
Input
: Undirected Graph
G
=(
V,E
) and sparsification ratio
s ∈
[0
,
1].
Output
: Vertex positions
P ∈
R
|V |×
2
1
w ₐ
embeddedness weights of edges
2
sort edges by non-increasing weight
3
E
union
ₐ
UMST with respect to
w
4
E
threshold
ₐ{e ∈ E
:
w
(
e
)
≥ w
(
e
(1
−s
)
|E|
)
}
5
P ₐ
layout determined from spanning subgraph (
V,E
union
∪ E
threshold
)
Algorithm 2:
UMST: Union of all Maximum Spanning Trees
Input
: Undirected Graph
G
=(
V,E
)andedgeweights
w
:
E
ₒ
R
≥
0
.
Data
: Union-Find datastructure
Output
: Edges belonging to any MST
1
E
union
ₐ∅
2
partition edges by weight into buckets
B
1
,...,B
k
3
sort buckets by decreasing weight
4
for
i ₐ
1
to
k
do
5
M ₐ∅
foreach
e
=(
u, v
)
∈ B
i
do
6
if
find
(u)
=
find
(v)
then
M ₐ M ∪{e}
7
foreach
e
=(
u, v
)
∈ M
do
union
(
u, v
)
8
E
union
ₐ E
union
∪ M
9
Sparse connected subgraphs of edges not likely to be between cohesive groups
have been proposed, e.g., by van Ham and Wattenberg [28] (planar graphs)
and Tumminello et al. [27] (graph of bounded genus). A minimally connected
subgraph of edges with high weights is a
maximum spanning tree
(MST), and
Mantegna [14] proposed these as a backbone. Trees, however, have severe draw-
backs: firstly, they do not maintain any local variation in density and, secondly,
they introduce a subtree ordering ambiguity. While the first also means that ar-
bitrary choices must be made when edges have equal embeddedness, the second
creates a degree of freedom that is almost as bad as disconnected components.
We combine thresholding (to maintain local variation) with the union of all
maximum spanning trees (UMST; to maintain connectedness). The UMST does
not only solve the problem of tie breaks but also reduces the ordering problem
by resulting in higher connectivity (Fig. 1(b)-(d)).
The complete algorithm to compute the layout of a hairball graph is presented
in Alg. 1. Note that the UMST only contributes the (strongest) edges necessary
to connect the components that result from the thresholding process.
Kruskal's algorithm for minimum spanning trees is easily adapted to deter-
mine the union of all maximum spanning trees. Since every edge of maximum
weight that has not been processed yet could be chosen next, we batch-process
them before components are merged; cf. Algorithm 2.
