python - 使用 numpy 表示具有未知结构的(可能很大)图的有效方法？

Question

我的设置基本上如下:

• 我有一组节点(表示为整数 0, ...)。可能有数百万。

• 这些节点在没有权重的无向图中连接。

• 图的结构未知，稀疏图和稠密图都是可能的，尽管具有数百万个节点的稠密图不太可能。

• 我想尽可能多地使用 numpy 以确保与项目其他部分的兼容性。我希望我可以将图上的所有操作都实现为 numpy ufuncs。

问题是:在对图进行操作时，经常会发生寻找边以及创建和删除边的情况。我的想法是使用排序的邻接列表，但是我不太确定如何使用 numpy 数组有效地实现它。

是否有一种仅使用 numpy 数组来实现它的有效方法，或者我是否必须使用其他数据结构？

Answer 1

使用 numpy.ndarray 似乎对您的规范不可行，因为您描述了 1,000,000+ 个节点，即相应的矩阵将具有 1e12+ 个条目。

您可以使用 scipy.sparse matrices 之一根据需要分配数据。在概述中，他们描述了不同实现的优缺点。对于您的应用程序，这似乎涉及频繁创建和删除边缘，dictionary of keys实现似乎是一个不错的选择:

This is an efficient structure for constructing sparse matrices incrementally.

linked list sparse matrix可以是另一种选择，但如果插入是随机发生的，性能可能会更差。

对这些矩阵的操作大多类似于 Numpy，但不鼓励使用 numpy 函数，如文档中所述:

Despite their similarity to NumPy arrays, it is strongly discouraged to use NumPy functions directly on these matrices because NumPy may not properly convert them for computations, leading to unexpected (and incorrect) results.

因此，您需要检查 scipy 库中是否有等效函数。在 scipy.sparse.csgraph 中，有很多可用于在稀疏矩阵上执行图形操作。模块。

顺便说一句the networkx package也是处理图形的流行选择。