Untangling Hairballs - Graph Drawing - page 100

Untangling Hairballs
From 3 to 14 Degrees of Separation
Arlind Nocaj, Mark Ortmann, and Ulrik Brandes
Computer & Information Science, University of Konstanz, Germany
Abstract. Small-world graphs have characteristically low average dis-
tance and thus cause force-directed methods to generate drawings that
look like hairballs. This is by design as the inherent objective of these
methods is a globally uniform edge length or, more generally, accurate
distance representation. The problem arises in graphs of high density
or high conductance, and in the presence of high-degree vertices, all of
which tend to pull vertices together and thus clutter variation in local
density.
We here propose a method to draw online social networks, a spe-
cial class of hairball graphs. The method is based on a spanning sub-
graph that is sparse but connected and consists of strong ties holding
together communities. To identify these ties we propose a novel measure
of embeddedness. It is based on a weighted accumulation of triangles in
quadrangles and can be determined eciently. An evaluation on empir-
ical and generated networks indicates that our approach improves upon
previous methods using other edge indices. Although primarily designed
to achieve more informative drawings, our spanning subgraph may also
serve as a sparsifier that trims a hairball graph before the application of
a clustering algorithm.
1 Introduction
Online social networks such as Facebook friendship graphs are an amalgamation
of a variety of social relations. The existence of a friendship tie might be due
to shared interests, spatial proximity, kinship, or professional relations to name
but a few. When such a multitude of relations is conflated in the same network,
any two nodes are likely to be connected via at most a few links - thus leading
to a small world effect [21]. Visualizations of these graphs using standard layout
methods such as force-directed placement produce drawings in which variation
in local structure is hidden in a densely-looking, overlap-ridden hairball .An
example is given in Fig. 1(a).
Various approaches to reduce the clutter in drawings of small worlds and other
hairball graphs have been proposed [12], most notably edge bundling [10], edge
lensing [11], modified layout algorithms or representations [1,7,29], and graph
simplification [2,17,18,20,23,30]. The idea of graph simplification is to identify
We gratefully acknowledge financial support from DFG under grants GRK 1042 and
Br 2158/6-1. The proposed method is available in visone.