5
$\begingroup$

Are there any algorithms to draw a billion node graph or to aggregate the information? The idea would be to allow for it to be parallelized using map reduce so it could be done in realtime

I was wondering if there were any other algorithms? A google search turned up nothing.

Very large graph drawing I have found are as follows

Below is a sketch of an algorithm I thought up.

Specifically one that you can pan around and zoom? I thought of the following algorithm.

  1. Take a graph layout algorithm (a force directed layout algorithm)
  2. Create a window of locality using a graph metric that you define
  3. Draw everything in an epsilon of that graph metric.
  4. Iterate the window throughout a n-dimentional space. Where n is defined as the amount of data points you have and a tag is a $S \in $ the set of strings. (vertex, edge, $tag_{1}$, ... $tag_{n})

--Begin amended algorithm--

Step 5 is due to @vzn answer: Add a visualization of local regions. Therefore we define a region as a set of points that are "close" due to some locality measure. Pagerank is an example so you have a pagerank of 2 you are in the region.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ esp for very large graphs it may be better to utilize domain-specific aspects/features/approaches rather than a generic visualization pkg which might not pick up on those aspects. $\endgroup$
    – vzn
    Jul 2, 2012 at 14:41
  • 1
    $\begingroup$ see also incremental drawing of large graphs $\endgroup$
    – vzn
    Jul 2, 2012 at 14:44
  • 4
    $\begingroup$ Just drawing a graph (with any number of nodes) with no restrictions on quality metrics -- e.g. minimized number of edge crossings, minimized sum of edge lengths -- is trivial in an algorithmic sense: essentially all you have to do is read the input in whatever form it's given (which takes linear time). So why a billion nodes? What does panning and zooming have to do with it? $\endgroup$
    – Huck Bennett
    Jul 3, 2012 at 0:51
  • $\begingroup$ @HuckBennett Okay, I rewrote the question to address your points. $\endgroup$
    – Joshua Herman
    Jul 3, 2012 at 12:35

1 Answer 1

Reset to default
6
+50
$\begingroup$

a billion node graphs have probably not been visualized much and are right on the edge of feasibility and an active area of research. the approach would generally have to depend on the unique data characteristics to reveal the features that are relevant/key for that dataset. assuming you mean in 3d. there are at least two roughly independent hard parts of your request

  • realtime visualization of large dataset

  • visualizing a very large graph (not nec realtime)

for realtime visualization of a very large graph one could use different approaches. you mention panning and zooming. you do not mention if you want to visualize only local regions. if you want global visualization, either some kind of aggregation method or high performance backend would be required (ie large distributed system).

a reasonable approach would be developing some method of aggregating mass "nearby/related" nodes into representative groups and then visualizing the connectivity of this "super graph" instead. here are some references

[1] Drawing Large Graphs by Low-Rank Stress Majorization Khoury, Hu et al

[2] Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs Gansner, Hu et al

[3] Algorithms for Visualizing Large Networks by Hu

[4] Efficient and High Quality Force Directed Graph Drawing by Hu

[5] Interactive Visualization of Large Graphs and Networks by Munzer

[6] ZAME: Interactive Large-Scale Graph Visualization Elmqvist et al

here is a recent successful example/application/breakthrough discovery that primate brain connectivity (with about 10^10 neurons) follows a grid pattern, by Wedeen et al, based on enhanced MRI mapping/visualization

[7] NIH brain wiring study by Wedeen et al

[8] Spectacular brain images reveal surprisingly simple structure

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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