NetworkX有哪些可扩展性问题？

我对有数百万节点和数千万条边的大型网络的网络分析感兴趣。我希望能够做许多事情，比如解析来自多种格式的网络，查找连接的组件，检测社区，以及运行像PageRank这样的中心度量。NetworkX有哪些可扩展性问题？

我被NetworkX吸引，因为它有一个很好的API，很好的文档，并且多年来一直处于积极的发展阶段。另外，因为它是在python中，它应该很快与开发。

在最近的一次演讲（幻灯片都可以在GitHub上here），有人声称：

不像许多其他工具，NX设计来处理有关问题，现代规模数据.. NX中的大多数核心算法都依赖于极快的遗留代码。

该演示文稿还指出，NetworkX的基本算法是在C/Fortran中实现的。

但是，看看源代码，它看起来像NetworkX主要是用python编写的。我对源代码并不太熟悉，但我知道有几个例子，其中NetworkX使用numpy来完成繁重的任务（反过来使用C/Fortran来完成线性代数）。例如，文件networkx/networkx/algorithms/centrality/eigenvector.py使用numpy来计算特征向量。

有没有人知道是否这种调用像numpy这样的优化库的策略在整个NetworkX中都非常流行，或者只有几种算法可以实现呢？任何人都可以描述与NetworkX相关的其他可扩展性问题吗？从NetworkX首席程序员

回复我提出的NetworkX邮件列表上的这个问题，ARIC哈格伯格回答说：

在NetworkX使用的数据结构适合扩展到大问题（例如，数据结构是一个邻接表）。算法具有不同的缩放属性，但您提到的一些可用（例如，PageRank，连接的组件，在边数量上是线性的）。

此时NetworkX是纯Python代码。使用Python字典对邻接结构进行编码，以牺牲内存和计算速度为代价提供了很大的灵活性。大型图将占用大量的内存，你最终会用完。

NetworkX确实使用NumPy和SciPy来计算基于线性代数的主要为的算法。在那种情况下，使用NumPy矩阵或稀疏矩阵将该图表表示为（复制）为邻接矩阵。这些算法可以受益于在NumPy和SciPY中引用的遗留C和FORTRAN代码。

来源

2011-11-02 conradlee

看来我目前无法亲自检查源代码。但无论如何，请考虑：80％的时间可能花费在20％的代码中。 Mercurial主要是用Python编写的，但我没有听说过一个人抱怨它的速度与Git相比，它主要是C. – delnan

是的，但我也担心内存。 networkx中的图形表示是一个python库。这是否意味着我只能将较小的图形放入内存？ – conradlee

你的大问题将是记忆。 Python只需就可以不用来处理数千万个对象，而无需在你的类实现中跳过箍筋。许多对象的内存开销太高，达到2GB，32位代码无法工作。有办法解决它 - 使用插槽，阵列或numpy。它应该是好的，因为networkx是为性能编写的，但如果有几件事情不起作用，我会检查你的内存使用情况。对于缩放，算法基本上是唯一与图形有关的事情。如果图形算法做错了，图形算法往往会有很大的扩展性，并且它们可能会像其他任何语言一样在Python中完成。

来源

2011-11-02 12:01:53 wisty

networkX主要用python编写的事实并不意味着它不可扩展，也不要求完美。总是有一个权衡。如果您在“机器”上投入更多资金，您将拥有更多的可扩展性，以及使用pythonic图库的好处。

如果不是，也有其他的解决方案，（here和here），它可以消耗较少的内存（基准看，我想的igraph完全ç支持，因此会），但你可能会错过NX的Python的感觉。

来源

2011-11-02 11:22:01 hymloth

这部分地回答了我的问题。但我也想知道，如所声称的，NetworkX的许多“核心”算法是否在C/Fortran中实现。 – conradlee

我调查了一下（当前）源代码，并且没有发现C/Fortran实现。似乎在那里的一切都是纯python ... – hymloth

谢谢你看看。请记住，如果调用numpy，那么numpy可能会使用LAPACK或其他优化的线性代数包（取决于系统配置）。我不太了解NetworkX实际使用numpy的频率（这是我的问题），但我知道一些例子。例如，在networkx/networkx/algorithms/centrality/eigenvector.py中使用numpy来查找特征向量。 – conradlee

这是一个老问题，但我认为值得一提的是graph-tool具有与NetworkX非常相似的功能，但它在C++中使用模板（使用Boost Graph Library）实现，因此速度更快（up to two orders of magnitude ）并使用更少的内存。

免责声明：我图形工具的作者。

来源

2013-05-04 22:34:15

我试过图形工具。它确实速度更快，但使用起来很难看。 API不会觉得pythonic。 –

真的......只是想和我这里的人分享我的经验。 –

@TiagoPeixoto - 您的库适合处理〜3M节点和〜10M边缘吗？我猜测存储器只是内存，对吗？ – Avision

NetworkX有哪些可扩展性问题？

回答

相关问题