27
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ It would help if you stated what you already tried. Did you give Graphviz a shot? $\endgroup$
    – Wolfgang Bangerth
    Commented Sep 19, 2012 at 3:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Ketcheson
    Commented Sep 19, 2012 at 6:40
  • $\begingroup$ Im giving Graphviz a shot right now, it looks a bit more promising, but I dont think it allows for interaction $\endgroup$
    – madmaze
    Commented Sep 19, 2012 at 14:54
  • 2
    $\begingroup$ 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). $\endgroup$
    – Jack Poulson
    Commented Sep 20, 2012 at 0:07
  • 1
    $\begingroup$ have you looked into visit? $\endgroup$
    – pyCthon
    Commented Sep 25, 2012 at 4:41

6 Answers 6

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Jack Poulson
    Commented Sep 22, 2012 at 21:16
  • $\begingroup$ 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. $\endgroup$
    – Geoff Oxberry
    Commented Sep 22, 2012 at 22:42
  • 3
    $\begingroup$ @JackPoulson - cough $\endgroup$
    – Aron Ahmadia
    Commented Sep 25, 2012 at 10:20
  • $\begingroup$ @GeoffOxberry - see link above $\endgroup$
    – Aron Ahmadia
    Commented Sep 25, 2012 at 10:20
  • 1
    $\begingroup$ @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. $\endgroup$
    – Aron Ahmadia
    Commented Sep 25, 2012 at 22:04
7
$\begingroup$

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

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @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. $\endgroup$
    – Aron Ahmadia
    Commented Oct 21, 2012 at 20:00
5
$\begingroup$

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.
Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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

[1] http://tulip.labri.fr/TulipDrupal/

Improve this answer
$\endgroup$

Your Answer

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

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