对于大型数据集,最快的力导向网络图引擎是什么？

Question

我们目前有一个动态更新的网络图,大约有1,500个节点和2,000个边.它在不断发展.我们当前的布局引擎使用Prefuse - 特别是力导向布局 - 使用大量服务器需要大约10分钟才能获得漂亮,稳定的布局.

我看了一下GraphViz的sfpd算法,但还没测试过......

我应该看一下更快的替代方案吗？

• 我不关心节点和边缘的视觉外观 - 我们单独处理 - 只是放在x, y节点上.
• 我们需要能够修改图形特定部分的布局属性,例如,为某些节点应用特殊的更紧密或更松散的弹簧.

在此先感谢,如果您需要更具体的信息,请发表评论!

编辑:我特别希望布局引擎选项之间的速度比较.基准,具体的例子,或仅仅是个人经验就足够了!

Answer 1

我写了一个基于JavaScript的图形绘图库VivaGraph.js.

它计算布局并使用2K +顶点渲染图形,在~10-15秒内渲染8.5K边缘.如果你不需要渲染部分,它应该更快.

这是一个视频演示它的实际效果:使用VivaGraphJS进行WebGL图形渲染.

在线演示可在此处获得.WebGL需要查看演示,但不需要计算图形布局.该库也可以在node.js下工作,因此可以用作服务.

API使用示例(仅限布局):

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); })

希望这可以帮助 :)

Answer 2

我会看一下OGDF,特别是http://www.ogdf.net/doku.php/tech:howto:frcl 我没有使用OGDF,但我知道Fast Multipole Multilevel是一个很好的高性能算法,当你正在处理与所需节点数量相关的强制定向布局所涉及的运行时类型,这很重要.除了其他原因之外,为什么算法很棒:快速多极方法.快速多极方法是矩阵乘法近似,它将矩阵乘法的O()运行时间减少到近似程度.理想情况下,你有这样的代码:http://mgarland.org/files/papers/layoutgpu.pdf但我无法在任何地方找到它; 也许CUDA解决方案无论如何都不是你的小巷.

祝好运.

Answer 3

Gephi Toolkit可能就是您所需要的:一些布局非常快且质量很好:http://gephi.org/toolkit/

30秒到2分钟足以布置这样的图表,具体取决于您的机器.您可以使用ForAtlas布局或Yifan Hu Multilevel布局.

对于非常大的图形(+ 50K节点和500K链接),OpenOrd布局将是