12

I love to visualize huge graphs (this is a hobby: http://anvaka.github.io/pm/ ). One problem however that keeps me awake at night, is data overload in such graphs.

If I render all connections inside a graph, I get hairball of mess:

edge mess

The mess can be reduced, if I render only those connections whose link is shorter than X pixels:

limit edge length

This works for smaller graphs (less than 200k nodes), but fails on larger graphs (with more than 1,000k nodes) nodes themselves overload the graph and look like white noise:

github graph

(you can see last graph here: Github Followers)

I'm somewhat desperate at this point, and asking very generic question: What would you recommend to use to avoid data overload with large graphs?

  • 1
    are farther away lines rendered softer/thinner? why does the white noise effect worry you -- it communicates the current state fairly well -- so what do you want the graphic to communicate instead? – jlarson Jan 18 '16 at 19:51
  • I think you need to decide what is essential to the user of the visualization, and optimize for that. As @jlarson says, if you're interested in showing connections and there are a bajillion connections, then white noise is what you get. If you show a lot of data as a lot of data, it will be overload. Somehow you have to abstract - show less data (zoom) or combine connections. Example: Galaxies are a kind of abstraction in the universe (they are groups of stars). By showing only galaxies, the complexity could be reduced. Is the visualization of galaxies useful? – Fuhrmanator Jan 19 '16 at 14:28
  • 1
    There are A LOT of papers on this topic. Just put 'Graph visualisation' in scholar.google.com. But you can't push an elephant through a key hole, and in the case of the brain you can't make the key hole any bigger. So you need to make the elephant smaller, slicing it, and communicate the best slices, while possibly using progressive disclosure. – Izhaki Jan 19 '16 at 22:32
  • 1
    I'm pretty sure no one is going to use your interface to meaningfully consume data... That being said; your work is amazing. Change nothing. – Azorce Jan 20 '16 at 15:36
  • Re-sell the same visualisation by naming it Data Fireworks! ;) On a more serious note - you have to figure out the intent of this viz, whether it is to convey the overall picture (which is doing fairly well), or is it to convey the granularities. – Amit Jain Jan 22 '16 at 11:41
6

Oooh, pretty.

Yeah, well, hairballs (this kind of huge graphs you have shown) are pretty much useless because unreadable. Genomicists and bioinformaticians have discovered this early in the days because their datasets are big enough to demonstrate the issue.

And no, adding 3D will not help the cause.

The solution for hairballs are hive plots.

enter image description here

Also look at Mike Bostock's guide on building Hive Plots in D3.

3

Your choices beyond the existing pan/zooming on the display could be to introduce a local focus+context lens around the mouse pointer, to unclutter/expand the current area of interest. However with the size of datasets you're mentioning you might need to consider aggregating and/or filtering on the data itself - a million node graph on a million-pixel display isn't going to look anything but cluttered

Aggregate nodes if they have a inherent hierarchical structure (or you can generate such a structure over them) to make a clustered graph, this can be a recursive clustering with nodes shown at several layers of clustering (for a real-world example think local cluster -> galaxy -> constellations -> individual start, you get the idea) - this will naturally aggregate links too

Filter nodes - by degree (no of links) or centrality measures to only see the important nodes or by type if they have one. Filter links by certain properties as you've done in your example (often the 'long' ones are the interesting ones - though be aware distance in the 2d representation is an approximation of the distance in data space)

Making these interactive would be best, but with the size of the graphs you mention the computations may well not be instant...

Have a look at what packages like Gephi do for ideas of node and link filters/measures

2

Disclaimer: Very random ideas from a non-specialist

What would you recommend to use to avoid data overload with large graphs?

I would look at successful visualizations of large graphs.

Here's a few:

Other things I think:

  • the force-based layout makes sense with a narrow ration of links/nodes IMHO, I would explore word2net-like spatialization for such a large dataset
    • to avoid the hairball effect where every cluster mix together
    • maybe spacialize in more than 3 dimensions and allow to switch the dimensions combination (seems really janky)
  • In your github graph, there could be a React community, a ruby community,... Even the big central nodes like dhh don't show
  • Also, there are clusters but it's hard to see the central points of cluster (the guy most people follow in the cluster).
  • navigation-wise, 2D seems easier. 3D adds some value to segregate the clusters but makes the navigation harder
2

I think one needs to address the question of what is being conveyed through the graph. If you want to point to certain interesting observations, marking them, or generating separate graphs to highlight the same might be one way to catch the attention.

While such graphs look visually appealing, the process of generating insights might prove to be challenging.

Providing the user to control what is shown would help the users in having relevant visualisations.

2

As others have said, it depends on what you want to accomplish. You specifically highlight the "white noise" effect due to having so many overlapping nodes and edges in your 3D force layout, so I'll focus on that.

I recommend using a different layout. Force-directed layouts tend to have high node density toward the middle, and in 3D that means the dense mass is underneath or on top of the other nodes you are looking at, compounding the density. I believe one solution is to have a more uniform layout.

Here is one solution that uses a two-step process:

  1. Use something like Newman's fast algorithm for detecting community structures to automatically detect dense clusters of nodes. Here is a screenshot from SocialAction, which implements that algorithm: enter image description here

  2. Use a group-in-a-box layout algorithm to layout the dense node clusters, perhaps using a simple cubic treemap layout for the clusters if you want to retain the 3D aspect. Here is a comparison of a force-directed layout, a treemap group-in-a-box layout, and a force-directed group-in-a-box layout from Chaturvedi et al's paper "Group-in-a-Box meta-layouts for topological clusters and attribute-based groups: space efficient visualizations of network communities and their ties": enter image description here Note the high density in the middle of the force-directed layout, and how that is absent in the group-in-a-box layouts.

With a technique like this, nodes will be more uniformly distributed in your layout space, and nodes will tend to be close to other nodes they are connected to. This should reduce the "white noise" and "hairball" effects by reducing both node and edge visual overlap.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.