What's the fastest force-directed network graph engine for large data sets?

Question

We currently have a dynamically updated network graph with around 1,500 nodes and 2,000 edges. It's ever-growing. Our current layout engine uses Prefuse - the force directed layout in particular - and it takes about 10 minutes with a hefty server to get a nice, stable layout.

I've looked a little GraphViz's sfpd algorithm, but haven't tested it yet...

Are there faster alternatives I should look at?

• I don't care about the visual appearance of the nodes and edges - we process that separately - just putting x, y on the nodes.
• We do need to be able to tinker with the layout properties for specific parts of the graph, for instance, applying special tighter or looser springs for certain nodes.

Thanks in advance, and please comment if you need more specific information to answer!

EDIT: I'm particularly looking for speed comparisons between the layout engine options. Benchmarks, specific examples, or just personal experience would suffice!

Answer 1

I wrote a JavaScript-based graph drawing library VivaGraph.js.

It calculates layout and renders graph with 2K+ vertices, 8.5K edges in ~10-15 seconds. If you don't need rendering part it should be even faster.

Here is a video demonstrating it in action: WebGL Graph Rendering With VivaGraphJS.

Online demo is available here. WebGL is required to view the demo but is not needed to calculate graphs layouts. The library also works under node.js, thus could be used as a service.

Example of API usage (layout only):

var graph = Viva.Graph.graph(),
    layout = Viva.Graph.Layout.forceDirected(graph);

graph.addLink(1, 2);
layout.run(50); // runs 50 iterations of graph layout

// print results:
graph.forEachNode(function(node) { console.log(node.position); })

Hope this helps :)