No Hairball – The Graph Drawing Experiment

→ QUICKLINK TO THE EXPERIMENT

Many graph drawings look like a hairball.

The larger a network is, the harder it is to visualize it.  Most graph drawing algorithms produce a giant “hairball”, in which nodes and edges are hopelessly mixed up, leaving no way to discern any structure whatsoever. Here is an example:

out_layout

This is from one of my own papers (WWW 2009), so I should know what I am talking about. Nowadays, I wouldn’t put such a picture in paper, let alone on the first page as I did then.  Many papers however, still contain such graphics.

Can we learn anything from this drawing?  No.  There are no communities visible.  No clustering is apparent.  I cannot even tell whether the graph is bipartite.  In fact, I cannot even estimate the size of the graph from this picture.

So, why do we keep putting hairballs in our papers?  Maybe, because they give us the illusion of insight into a complex network.  Yes, we would like to understand whether a graph displays clustering, bipartivity, assortativity, dissortativity, skewed degree distributions, and a myriad of other interesting properties that complex networks can have. What better way to visualise these features, than by drawing the graph?  Isn’t every visualisation also a drawing?

No, visualisations are not necessarily drawings.  We don’t need to draw a graph in order to visualise it.  In fact, the mere fact that we try to draw the entirety of a network in a small space is what leads to the hairball problem to begin with: Hundred of thousands, millions or even more nodes and edges are crammed into the space of only a few centimetres.  It is no wonder we don’t see anything in a hairball graph:  Each node and each edge gets allocated a space on the order of a micrometre or less – much too small to even be shown on computer displays or printed on paper, let alone seen by the human eye.

What then, can we do to avoid hairballs?  Several ideas have been tried:

  • Show only a subset of the network.  This is called sampling.  In its simplest incarnation, choose a random subset of the nodes, to get a subgraph of the real graph of manageable size.  Then, draw that subgraph.
  • Aggregate nearby nodes into single nodes.  This is called coalescing, and also produces smaller graphs, which are then drawn with the usual methods.
  • Allow the user to zoom in, using interactive software.  This is nice, but doesn’t give any more insight into the overall properties of the network.

These methods are all suited to particular use cases.  But for visualising overall properties of a graph, these methods fail.  What do these methods all have in common?  They assume that to visualise a graph, you have to draw the graph.  The question thus becomes, Can we go further?  Can we visualise a graph without drawing it?  Almost.

In the experiment we are performing, we don’t draw the graph to be visualised.  Instead, we draw another graph – a much smaller one – which is representative of our graph.  In fact, we throw away all nodes and edges of the input.  Only graph statistics such as the assortativity, the bipartivity, and others are kept, and a completely new graph is created, specifically for visualisation.  Most graph/network researchers now think, How can I see individual nodes and edges of the graph?  The answer is that you can’t; that is the point of the method.  We sacrifice local information in graph in order to make global properties more apparent.

The method is in development, and a paper is upcoming, but not public yet.

We are now performing an experiment to find out how to do this graph visualisation optimally:

TAKE PART IN THE EXPERIMENT

This is an interactive experiment that will ask you to look at graphs, and to answer yes/no questions. In fact, you only have to click on graphs to answer.  However:  You must be knowledgeable in graphs and networks to participate.

This will help our research.  If you want to keep in touch with the results of the experiments, write to <pkumar@uni-koblenz.de>.

If you’re interested in graph visualisation, check out the KONECT project; it has lots of graph visualisation methods based on matrix decompositions.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s