graph exploration and data overload

Question

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:

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

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:

(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?

Answer 1

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.

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

Answer 2

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

Answer 3

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:

• http://internet-map.net/: it's easy to see the central points and the clusters. Also easy to see individual points.
• http://www.randalolson.com/wp-content/uploads/reddit-world-map.jpg : labeling makes things easy to understand. Don't have to do it by hand, you can extract representative instance of a cluster and show it's label.
• graphistry: very clear heatmap effect + easy label exploration
• http://wiki.polyfra.me/, just nice too
• https://xkcd.com/802/: This can looks funny but it's clear and show the size of each community

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

Answer 4

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.

Answer 5

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:

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": 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.