An algorithm to efficiently draw a extremely large graph in real time 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.


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