# Visualizing very large link graphs

I am looking for a tool to visualize very large directional link graphs. I currently have ~2million nodes with ~10million edges. I have tried a few different things, but most take hours to even do 100k node graphs

What I have tried:
I spent a day with gephi, but 80K nodes take about an hour to add and the application becomes mostly useless.

Any suggestions?

An interactive visualization would be a plus.

• It would help if you stated what you already tried. Did you give Graphviz a shot? – Wolfgang Bangerth Sep 19 '12 at 3:16
• Graphviz is what I would try first. No idea whether it will work with something of that size. Obviously you will need something that uses a sparse representation for the adjacency matrix, but it seems unimaginable that a software package would not. – David Ketcheson Sep 19 '12 at 6:40
• Im giving Graphviz a shot right now, it looks a bit more promising, but I dont think it allows for interaction – madmaze Sep 19 '12 at 14:54
• Have you tried interpreting the graph as a sparse matrix and visualizing it with MATLAB or Octave's 'spy' function? 10 million nonzero entries is well within the reach of moderately powerful desktops. This would also set you up for spectral bisection (finding partitions of your graph might make it easier for you to visualize it). – Jack Poulson Sep 20 '12 at 0:07
• have you looked into visit? – pyCthon Sep 25 '12 at 4:41

Graphviz should work. I believe that the images associated with the matrices in the University of Florida sparse matrix collection were visualized using sfdp, a force-directed graph visualization algorithm developed by Yifan Hu. Most of the matrices in the collection have a computational time associated with generating a corresponding visualization, so you might be able to search for matrices whose graphs have characteristics similar to the ones you wish to visualize. For instance, a graph with ~2.1 million nodes and ~3 million edges took Hu ~36000s to generate, or 10 hours. While it's not clear what hardware was used to generate the graph, it's probably a reasonable guess that a desktop or laptop was used, and the times would at least give you a rough idea of how much time rendering the graph may take. Hu's algorithm appears to be one of the state-of-the-art visualization algorithms (he published it in 2005), but not being an expert in the field, I can't speak to whether or not better algorithms exist. This algorithm is included with Graphviz as an option, and is designed to be used on large graphs such as the one you describe.

• Very neat. It looks like Barnes-Hut is being used to simulate forces between the nodes of the graph, so I would assume that a parallel FMM implementation might yield a significant speedup. On the other hand, Hu's method seems to have a multilevel structure similar to MeTiS, which tends to be hard to parallelize. – Jack Poulson Sep 22 '12 at 21:16
• Yeah, when I looked at the paper, I also thought a parallel FMM implementation might be interesting, but I wasn't sure how practical it would be, since I don't have much experience with parallel algorithms. – Geoff Oxberry Sep 22 '12 at 22:42
• @JackPoulson - cough – Aron Ahmadia Sep 25 '12 at 10:20
• @GeoffOxberry - see link above – Aron Ahmadia Sep 25 '12 at 10:20
• @JackPoulson - You'll find that the force-directed layout algorithms are pretty sensitive to the initial seeding, there was some nice work done by other groups to reformulate the problem for more aesthetic layouts. – Aron Ahmadia Sep 25 '12 at 22:04

The JavaScript InfoVis Toolkit has a neat interactive interface for annotated local views of graphs. These demos may be relevant to you:

See Graphinsight 1.2, can handle with million of nodes easily and it's interactive and in 3D.

You can also layout graphs with million of nodes and edges with high efficient algebraic methods or force directed methods. It's available in trial version for evaluation (Disclaimer: I am one of the authors of the program).

www.graphinsight.com

• @linelio - Thanks for your answer and welcome to scicomp! Please do see the rules about promotion and be sure that you clearly disclose any personal connections when making recommendations. – Aron Ahmadia Oct 21 '12 at 20:00

Here are some recommendations and links collected over time:

• For 2M nodes it is hard to recommend anything not knowing your hardware, and possibly some data reduction is in order, but taking stuff that is freely available, zGrViewer may fit your needs for visualization (requires GraphViz).
• Following @pyCthon 's idea, suggest you also have a look at VisIt for some interactivity in plotting.
• I am re-visiting the igraph package for the R statistical language, which includes neat layout algorithms (Fruchterman-Reingold and Kamada-Kawai), among others.
• Large Graph Layout library is now on SourceForge.

We've been building http://www.github.com/graphistry/pygraphistry to enable doing this from most browsers and notebooks. The idea is to use WebGL to render the big graphs (pan/zoom/etc.), and offload most of the real-time compute (layout, filter, etc.) to a GPU cloud. It's similar to Gephi or Cytoscape, but with more of a focus on big graphs and data analysis, and integrating into the web and notebooks.

You may try "Tulip" [1] , I think it can handle quite large graphs (at least I tryed it with 10K to 100K nodes and it worked well).