NetworkX存在哪些可扩展性问题？

Question

我对大规模网络分析很感兴趣，这些网络有数百万个节点和数千万条边。我想做的事情包括从多种格式解析网络、找到连接的部分、检测社区，以及运行像PageRank这样的中心性测量。

我对NetworkX很感兴趣，因为它有一个很好的接口，文档也很齐全，并且多年来一直在积极开发。而且因为它是用Python写的，开发起来应该比较快。

在最近的一次演讲中（幻灯片可以在github上找到，在这里），有人提到：

与许多其他工具不同，NetworkX被设计成可以处理现代问题相关的数据规模……NetworkX中的大多数核心算法依赖于非常快速的传统代码。

演讲中还提到，NetworkX的基本算法是用C/Fortran实现的。

不过，从源代码来看，NetworkX大部分是用Python写的。我对源代码不太熟悉，但我知道NetworkX有几个例子是用numpy来进行重计算（而numpy又是用C/Fortran来做线性代数的）。例如，文件networkx/networkx/algorithms/centrality/eigenvector.py使用numpy来计算特征向量。

有没有人知道，像调用优化库numpy这样的策略在NetworkX中是否普遍，还是只有少数算法这样做？另外，还有没有人能描述一下与NetworkX相关的其他可扩展性问题？

来自NetworkX首席程序员的回复 我在NetworkX邮件列表上提出了这个问题，Aric Hagberg回复说：

NetworkX使用的数据结构适合扩展到大型问题（例如，数据结构是邻接表）。这些算法有不同的扩展特性，但你提到的一些算法是可以使用的（例如，PageRank和连接组件在边的数量上是线性复杂度）。

目前NetworkX是纯Python代码。邻接结构是用Python字典编码的，这提供了很大的灵活性，但代价是内存和计算速度。大型图会占用很多内存，最终你会用完内存。

NetworkX确实使用NumPy和SciPy来处理主要基于线性代数的算法。在这种情况下，图被表示（复制）为邻接矩阵，使用NumPy矩阵或SciPy稀疏矩阵。这些算法可以受益于在NumPy和SciPy底层使用的传统C和FORTRAN代码。

Answer 1

虽然networkX大部分是用Python写的，但这并不意味着它不能扩展，也不是说它完美无缺。使用任何技术都有利有弊。如果你在你的“机器”上投入更多的钱，你就可以获得想要的扩展性，同时还能享受到使用Python图形库的好处。

如果不想这样，还有其他解决方案（这里和这里），这些可能会占用更少的内存（可以进行基准测试看看，我认为igraph是完全用C语言支持的，所以会更省内存），但你可能会失去networkX那种Python风格的感觉。

Answer 2

这个问题虽然比较老，但我觉得值得提一下，graph-tool 的功能和 NetworkX 很相似，不过它是用 C++ 和模板实现的（使用了 Boost 图形库），所以运行速度快得多（快了整整两个数量级），而且占用的内存也少。

声明：我是 graph-tool 的作者。

Answer 3

你最大的麻烦会是内存。Python根本无法处理几千万个对象，除非你在类的实现上费点劲。很多对象占用的内存太高，一旦超过2GB，32位的代码就不行了。不过有一些解决办法，比如使用slots、数组或者NumPy。因为networkx是为了性能而写的，所以应该没问题，但如果有些地方不行，我会检查一下你的内存使用情况。

至于扩展性，算法基本上是处理图的唯一关键。如果图的算法做得不对，扩展性会变得非常糟糕，而在Python中，算法出错的概率和其他语言是一样的。