Untangling Hairballs - Graph Drawing - page 101

a subset of edges such that only the resulting graph, the so-called backbone,
needs to be laid out. We adopt this approach and propose a new method to trim
hairballs.
Problem formulations in graph simplification include the preservation of prop-
erties such as cuts [2], spectra [23,24], connectivity [30], collapsing substructures
into supernodes [18], and emphasizing deeply embedded connections [17,20]. As
graph invariants such as cuts are more easily affected by noise in empirical net-
works, we opt for locally defined graph simplification criteria.
Substantiated by the sociological work of Simmel [22], Nick et al. [17] define
the strength of an edge by the number of triangles it is contained in, and then
determine the degree of structural embeddedness for an edge by comparing the
ranked neighborhoods of its two vertices. The purpose is to identify edges that
are more likely to be inside of cohesive groups than between such groups. If
the initial edge strengths are uniform, the Simmelian backbone reduces to a
backbone proposed by Satuliri et al. [20]. In both methods, the backbone is
obtained by finally removing all edges with weights below a specified nodal or
network wide threshold.
These filtering techniques are related to, but not the same as graph partition-
ing. Since we want to use them for graph drawing, the difference is even greater
because maintaining connectedness becomes a crucial constraint. Otherwise, the
layout algorithm is oblivious to edges of the original graph connecting vertices
in different components of the backbone as can be inferred from Fig. 1(b). When
connected components happen to be placed far apart, these edges will run across
the drawing and produce even worse clutter.
We present an ecient preprocessing technique that allows to draw a certain
class of small-world social networks with standard layout algorithms that would
produce hairball layouts otherwise. Our main contributions are:
- a novel method to identify strong ties,
- the use of the union of all maximum spanning trees as a sparsifier that
maintains connectedness and avoids subtree-ordering ambivalence, and
- an evaluation on observed and generated networks.
We outline our overall method for drawing hairball graphs in the next section
and describe our edge embeddedness metric in Sect. 3. Different metrics are
evaluated in Sect. 4 and we conclude in Sect. 5.
2 Drawing Algorithm
The main challenges in drawing hairball graphs are their high density, low di-
ameter and noisy group structure. Therefore, our goal is to find a backbone of
the graph that retains deeply embedded edges and thus can be used to draw the
original graph, e.g., by a force-directed method [13] to reveal the actual variation
in cohesiveness.
Since most drawing methods cannot put vertices of different graph compo-
nents into a meaningful spatial relation, cf. Fig. 1(b), we need to maintain the
graph connectivity to retain the global context.