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

Question

我对在数百万节点和上千万边的大型网络上进行网络分析很感兴趣。我想要能够解析多种数据格式的网络，找出连通组件，检测社区，并运行类似PageRank的中心度量。

我被NetworkX所吸引，因为它有良好的API、优秀的文档，并且已经处于活跃开发状态多年。此外，由于它是用Python编写的，应该可以快速开发。

在最近的一个演示文稿中（幻灯片可在github上这里找到），声称：

“与许多其他工具不同，NX设计用于处理与现代问题相关的规模数据...大多数NX核心算法依赖于极快的旧代码。”

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

然而，查看源代码后，NetworkX似乎主要是用Python编写的。我对源代码不是太熟悉，但我知道其中一些例子，NetworkX使用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代码中受益。

- conradlee

---

目前似乎我自己检查源代码存在问题。但无论如何，请考虑：80%的时间可能花费在20%的代码上。Mercurial主要使用Python编写，但我没有听到任何人抱怨它的速度与大部分使用C的Git相比。 - user395760

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

Answer 1

这是一个老问题，但我认为值得一提的是，graph-tool 与 NetworkX 功能非常相似，但它是使用 C++ 和模板实现的（使用 Boost Graph Library），因此速度更快（高达两个数量级），内存使用也更少。

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

- Tiago Peixoto

---

我尝试了graph-tool。它确实比较快，但使用起来有点丑陋。API不太符合Python的风格。 - Robsdedude

是的，您可以轻松地使用任何笔记本电脑处理这个问题。 - Tiago Peixoto

@user1938107 这需要对库进行大量的更改，而且我甚至没有Windows机器。 - Tiago Peixoto

@user1938107 我宁愿支付你10美分来为你的计算机安装一个合适的操作系统... - Tiago Peixoto

@opt 在2019年，C++仍然比纯Python快几个数量级，所以答案是肯定的。该项目并没有被放弃。那个Github页面不是官方页面，只是一些随意的分支。网站和Gitlab页面都非常更新。 - Tiago Peixoto

Answer 2

你将遇到的主要问题是内存。Python在处理数以千万计的对象时，必须在类实现中进行很多优化才能正常工作。许多对象的内存开销太高，一旦达到2GB，32位代码就无法运行。有些方法可以解决这个问题，比如使用slots、数组或NumPy。因为networkx是为了性能而编写的，所以应该没有问题，但是如果有一些东西不起作用，我会检查你的内存使用情况。

至于扩展方面，算法基本上是图形处理中最重要的部分。如果使用不当，图算法的规模会变得非常丑陋，并且在Python中，就像在任何其他语言中一样容易出错。

- wisty

Answer 3

虽然networkX主要是用Python编写的，但这并不意味着它不可扩展，也不能保证完美。在可扩展性和完美之间总是存在权衡。如果您花更多的钱在“计算机”上，您将拥有想要的可扩展性，并获得使用Python风格的图形库的优势。

如果没有更多预算，还有其他解决方案（ 此处 和 此处 ），可能会消耗更少的内存（进行基准测试，我认为igraph完全由C支持，因此可能内存消耗更少），但您可能会错过NX的Pythonic感觉。

- hymloth

---

这在一定程度上回答了我的问题。但我还想知道NetworkX的许多“核心”算法是否真的是用C/Fortran实现的，正如所声称的那样。 - conradlee

我稍微调查了一下（当前的）源代码，发现其中没有C/Fortran实现。看起来所有东西都是纯Python... - hymloth

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

身为上述引用库之一igraph的作者，允许我加入意见。 igraph的核心使用约90％的C和10％的C++实现，我曾使用igraph处理过大约200万个节点和700万条边的图形，而且没有遇到任何问题。它有一个Python接口，因此您可以从Python中使用它，但是由于其C语言历史，Python API不像NetworkX那样优雅。例如，在igraph中，节点和边始终由整数标识（因为在C级别上处理起来更容易），您必须使用顶点/边属性将它们映射到您的实际对象。 - Tamás

@Tamás，您可以使用pickle将Python数据序列化并传递给包含序列化数据的字节缓冲区的C程序。然后，C程序可以将序列化数据传回Python进行反序列化。这样，甚至可以将字典传递给C程序。但是，C程序无法与数据进行交互。 - tedtanner

Answer 4

我认为GraphScope可以很好地解决NetworkX的可扩展性问题，它提供了与NetworkX兼容的Python接口和用C++实现的高效分布式运行时。也就是说，用户只需要修改他们的NetworkX应用程序的几行代码，就能实现数个数量级的性能提升。简而言之，在GraphScope上运行NetworkX应用程序具有以下优势：
用户工作量最小化：要使NetworkX应用程序在GraphScope上运行，用户只需将import network替换为import graphscope.nx as networkx，因为GraphScope的图操作和数据加载接口与NetworkX完全兼容。例如，要运行NetworkX中的聚类算法，用户可以编写以下代码：

import os
import network

g = networkx.read_edgelist(
     os.path.expandvars('PATH_TO_DATASET')
)

result = networkx.clustering(g)

在GraphScope上运行聚类算法，用户只需要修改一行特定的代码即可。

import os
import graphscope.nx as networkx

g = networkx.read_edgelist(
     os.path.expandvars('PATH_TO_DATASET')
)

result = networkx.clustering(g)

高性能：GraphScope的运行时采用C++实现，以提高效率。以上述聚类算法为例，在GraphScope上运行比在NetworkX上运行快29倍以上。此外，GraphScope还可以以分布式方式运行NetworkX应用程序，实现高可扩展性。要在K8s集群上以分布式方式运行NetworkX应用程序，用户需要将import graphscope.nx as networkx替换为

import graphscope
networkx = graphscope.session(num_workers=$NUM_WORKERS).nx()

关于如何在GraphScope上运行NetworkX应用程序的更多信息，请查看以NetworkX风格分析图形的GraphScope。

声明：我是GraphScope的作者。

- Lei Wang