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 （复制）作为邻接矩阵 稀疏矩阵。这些算法可以受益于遗留的 C 和 在 NumPy 和 SciPY 中使用的 FORTRAN 代码。

Answer 1

你的大问题将是记忆。如果不跳过类实现中的障碍，Python 根本无法处理数千万个对象。许多对象的内存开销太高，达到 2GB，32 位代码就无法工作。有很多方法可以解决这个问题 - 使用槽、数组或 NumPy。它应该没问题，因为networkx是为了性能而编写的，但是如果有一些东西不起作用，我会检查你的内存使用情况。

至于缩放，算法基本上是图唯一重要的事情。如果图算法做错了，那么它们往往会出现非常的缩放，而在 Python 中，它们与任何其他语言一样有可能正确完成。

Answer 2

我认为 GraphScope 可以很好地解决 NetworkX 的可扩展性问题，通过提供与 NetworkX 兼容的 Python 接口，用 C++ 实现的高效分布式运行时。也就是说，用户只需要通过几行代码修改他们的NetworkX应用程序，同时实现几个数量级的性能提升。简而言之，在 GraphScope 上运行 NetworkX 应用程序具有以下优点：

用户工作量最少：要使 NetworkX 应用程序在 GraphScope 上运行，用户只需替换导入网络使用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 集群上以分布式方式运行 NeteorkX 应用程序，用户需要将 import graphscope.nx as nwtworkx 替换为。

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

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

免责声明：我是 GraphScope 的作者。

Answer 3

事实上，networkX 大部分是用 python 编写的，但这并不意味着它不可扩展，也不意味着它是完美的。总是有一个权衡。如果你在“机器”上投入更多的钱，你将拥有你想要的可扩展性以及使用 pythonic 图形库的好处。

如果没有，还有其他解决方案（此处和这里 ），这可能会消耗更少的内存（基准测试并看看，我认为 igraph 完全支持 C，所以它会），但你可能会错过 pythonic NX的感觉。

Answer 4

这是一个老问题，但我认为值得一提的是 graph-tool 具有与NetworkX，但它是使用模板在 C++ 中实现的（使用 Boost Graph Library），因此速度更快（up两个数量级）并使用内存少得多。

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