用于大型数据集的最快的力导向网络图引擎是什么? [英] What's the fastest force-directed network graph engine for large data sets?

问题描述

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

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.

我看过一点GraphViz的sfpd算法，但还没有测试过...

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

是否有我应该考虑的更快的替代方案?

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

提前致谢，如果您需要更具体的信息来回答，请发表评论！

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

我特别在寻找布局引擎选项之间的速度比较.基准、具体示例或只是个人经验就足够了！

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

推荐答案

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

I would have a look at OGDF, specifically http://www.ogdf.net/doku.php/tech:howto:frcl I have not used OGDF, but I do know that Fast Multipole Multilevel is a good performant algorithm and when you're dealing with the types of runtimes involved with force directed layout with the number of nodes you want, that matters a lot. Why, among other reasons, that algorithm is awesome: Fast Multipole method. The fast multipole method is a matrix multiplication approximation which reduces the O() runtime of matrix multiplication for approximation to a small degree. Ideally, you'd have code from something like this: http://mgarland.org/files/papers/layoutgpu.pdf but I can't find it anywhere; maybe a CUDA solution isn't up your alley anyways.

祝你好运.

这篇关于用于大型数据集的最快的力导向网络图引擎是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！