<p>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</p>

<ul>
<li><p>realtime visualization of large dataset</p></li>
<li><p>visualizing a very large graph (not nec realtime)</p></li>
</ul>

<p>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).</p>

<p>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</p>

<p>[1] <a href="http://www2.research.att.com/~yifanhu/PUB/lowrank_sm.pdf">Drawing Large Graphs by Low-Rank Stress Majorization</a> Khoury, Hu et al</p>

<p>[2] <a href="http://www2.research.att.com/~yifanhu/PUB/edge_bundling.pdf">Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs</a> Gansner, Hu et al</p>

<p>[3] <a href="http://www2.research.att.com/~yifanhu/PUB/ch16.pdf">Algorithms for Visualizing Large Networks</a> by Hu</p>

<p>[4] <a href="http://www2.research.att.com/~yifanhu/PUB/graph_draw_small.pdf">Efficient and High Quality Force Directed Graph Drawing</a> by Hu</p>

<p>[5] <a href="http://graphics.stanford.edu/papers/munzner_thesis/">Interactive Visualization of Large Graphs and Networks</a> by Munzer</p>

<p>[6] <a href="http://91-641.wiki.uml.edu/file/view/zame+-+Interactive+Large-Scale+Graph+Visualization.pdf">ZAME: Interactive Large-Scale Graph Visualization</a> Elmqvist et al</p>

<p>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</p>

<p>[7] <a href="http://www.nih.gov/news/health/mar2012/nimh-29.htm">NIH brain wiring study by Wedeen et al</a></p>

<p>[8] <a href="http://www.msnbc.msn.com/id/46897519/ns/technology_and_science-science/t/spectacular-brain-images-reveal-surprisingly-simple-structure/">Spectacular brain images reveal surprisingly simple structure</a></p>

CC BY-SA 3.0
2012-07-05T15:23:32.607Z
2012-07-05T15:23:32.607Z
vzn
<p>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</p>

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

<p>Very large graph drawing I have found are as follows</p>

<ul>
<li><a href="http://www2.research.att.com/~yifanhu/GALLERY/GRAPHS/" rel="nofollow">http://www2.research.att.com/~yifanhu/GALLERY/GRAPHS/</a></li>
</ul>

<p>Below is a sketch of an algorithm I thought up.</p>

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

<ol>
<li>Take a graph layout algorithm (a force directed layout algorithm)</li>
<li>Create a window of locality using a graph metric that you define</li>
<li>Draw everything in an epsilon of that graph metric.</li>
<li>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})</li>
</ol>

<p>--Begin amended algorithm--</p>

<p>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.</p>

CC BY-SA 3.0
2012-07-02T14:41:14.547Z
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.
vzn
CC BY-SA 3.0
2012-07-02T14:44:55.337Z
see also [incremental drawing of large graphs](http://cstheory.stackexchange.com/questions/7660/incremental-drawing-of-large-graphs)
vzn
CC BY-SA 3.0
2012-07-03T00:51:34.140Z
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?
Huck Bennett
CC BY-SA 3.0
2012-07-03T12:35:21.750Z
@HuckBennett Okay, I rewrote the question to address your points.
Joshua Herman
<reference-request><graph-theory><cg.comp-geom><graph-drawing>
An algorithm to efficiently draw a extremely large graph in real time
Joshua Herman
# An algorithm to efficiently draw a extremely large graph in real time

(Asked by: username_0 on 2012-06-30)

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

* <http://www2.research.att.com/~yifanhu/GALLERY/GRAPHS/>

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.

**Tags:** reference-request, graph-theory, cg.comp-geom, graph-drawing
> **Comments:**
> **username_1**: 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.  
> **username_1**: see also [incremental drawing of large graphs](http://cstheory.stackexchange.com/questions/7660/incremental-drawing-of-large-graphs)  
> **username_2**: 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?  
> **username_0**: @HuckBennett Okay, I rewrote the question to address your points.  

---

## 1 answers

### Answer by username_1 on 2012-07-05. Score: 6 | Accepted answer

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](http://www2.research.att.com/~yifanhu/PUB/lowrank_sm.pdf) Khoury, Hu et al

[2] [Multilevel Agglomerative Edge Bundling for Visualizing Large Graphs](http://www2.research.att.com/~yifanhu/PUB/edge_bundling.pdf) Gansner, Hu et al

[3] [Algorithms for Visualizing Large Networks](http://www2.research.att.com/~yifanhu/PUB/ch16.pdf) by Hu

[4] [Efficient and High Quality Force Directed Graph Drawing](http://www2.research.att.com/~yifanhu/PUB/graph_draw_small.pdf) by Hu

[5] [Interactive Visualization of Large Graphs and Networks](http://graphics.stanford.edu/papers/munzner_thesis/) by Munzer

[6] [ZAME: Interactive Large-Scale Graph Visualization](http://91-641.wiki.uml.edu/file/view/zame+-+Interactive+Large-Scale+Graph+Visualization.pdf) 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](http://www.nih.gov/news/health/mar2012/nimh-29.htm)

[8] [Spectacular brain images reveal surprisingly simple structure](http://www.msnbc.msn.com/id/46897519/ns/technology_and_science-science/t/spectacular-brain-images-reveal-surprisingly-simple-structure/)


---

