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

Question

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

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

有更快的替代方案吗我应该看什么？

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

预先感谢，如果您需要更具体的信息来回答，请评论！

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

Answer 1

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

它计算布局并在大约 10-15 秒内渲染具有 2K+ 顶点、8.5K 边的图形。如果您不需要渲染部分，它应该会更快。

以下是演示其实际操作的视频：使用 VivaGraphJS 进行 WebGL 图形渲染。

在线演示可在此处获取。观看演示需要 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，但我确实知道快速多极多级是一种性能良好的算法，当您处理涉及力导向布局的运行时类型以及所需的节点数量时，这非常重要。
除其他原因外，为什么该算法很棒：快速多极子方法。快速多极方法是一种矩阵乘法近似，它可以在较小程度上减少矩阵乘法近似的 O() 运行时间。理想情况下，您应该拥有如下代码： http://mgarland.org/files/papers /layoutgpu.pdf 但我在任何地方都找不到它；也许 CUDA 解决方案无论如何都不适合你。

祝你好运。

Answer 3

Gephi Toolkit 可能正是您所需要的：一些布局速度非常快，但质量很好：http://gephi.org/ toolkit/

30 秒到 2 分钟足以布局这样的图表，具体取决于您的机器。
您可以使用 ForAtlas 布局或 Yifan Hu 多级布局。

对于非常大的图（+50K 节点和 500K 链接），OpenOrd 布局将

Answer 4

在商业场景中，您可能还想查看 yFiles 图形布局和可视化库系列。

甚至它的 JavaScript 版本 也可以使用不同的排列样式对数千个节点和边进行布局。 “有机”布局样式是强制导向布局算法的一种实现，本质上类似于 Neo4j 浏览器应用程序中使用的算法。但是还有更多可用的布局算法可以为某些类型的图形结构和图表提供更好的可视化效果。根据问题的设置和结构，某些算法只需几秒钟，而更复杂的实现也可能使您的 JavaScript 引擎崩溃。截至目前，基于 Java 和 .net 的变体的性能仍然要好一些，但 JavaScript 引擎正在迎头赶上。

您可以在 这个在线演示中使用这些算法和设置。

^{免责声明：我为 yWorks 工作，该公司是这些库的创建者，但我并不代表我的雇主。}

Answer 5

我会看一下 http://neo4j.org/ 它的开源代码，这对您的情况有益，这样您就可以根据您的需求进行定制。 github 帐户可以在此处找到。