numpy/scipy从加权边列表中构建邻接矩阵

Question

我正在阅读一个类似加权边列表/ numpy数组的东西：

0 1 1
0 2 1
1 2 1
1 0 1
2 1 4

这里有一个包含'User1','User2','Weight'三列的列表。我想使用scipy.sparse.csgraph.depth_first_tree算法执行DFS操作，需要将其转换成 N x N 矩阵的格式输入。请问如何将之前的列表转换为如下的方阵：

0 1 1
1 0 1
0 4 0

在numpy或scipy中？

感谢您的帮助。

编辑:

我一直在处理一个庞大的网络（1.5亿节点），所以我正在寻找一种内存有效的方法来完成这项任务。

- Fabio Lamanna

Answer 1

您可以使用内存高效的scipy.sparse矩阵：

import numpy as np
import scipy.sparse as sparse

arr = np.array([[0, 1, 1],
                [0, 2, 1],
                [1, 2, 1],
                [1, 0, 1],
                [2, 1, 4]])
shape = tuple(arr.max(axis=0)[:2]+1)
coo = sparse.coo_matrix((arr[:, 2], (arr[:, 0], arr[:, 1])), shape=shape,
                        dtype=arr.dtype)

print(repr(coo))
# <3x3 sparse matrix of type '<type 'numpy.int64'>'
#   with 5 stored elements in COOrdinate format>

使用 todense 可以将稀疏矩阵转换为密集的 numpy 数组：

print(coo.todense())
# [[0 1 1]
#  [1 0 1]
#  [0 4 0]]

- unutbu

---

谢谢！一切都很顺利，直到 todense()：它使脚本耗尽了内存。但是您的解决方案非常快速且内存消耗低！ - Fabio Lamanna

Answer 2

尝试以下类似的操作：

import numpy as np
import scipy.sparse as sps

A = np.array([[0, 1, 1],[0, 2, 1],[1, 2, 1],[1, 0, 1],[2, 1, 4]])
i, j, weight = A[:,0], A[:,1], A[:,2]
# find the dimension of the square matrix
dim =  max(len(set(i)), len(set(j)))

B = sps.lil_matrix((dim, dim))
for i,j,w in zip(i,j,weight):
    B[i,j] = w

print B.todense()
>>>
[[ 0.  1.  1.]
 [ 1.  0.  1.]
 [ 0.  4.  0.]]

- igavriil

---

我认为没有一个。你可以考虑使用networkx来创建和操作图形。 - igavriil

我尝试过了，但问题在于网络非常庞大：约有1.5亿个节点。NetworkX由于其规模而崩溃。您的脚本很好，但在构建B矩阵时会出现MemoryError错误。 :-( - Fabio Lamanna

如果您将B替换为一个稀疏矩阵会怎样？ - igavriil

你的意思是初始化一个稀疏的B矩阵吗？代码现在在这里崩溃：B = np.zeros((dim, dim))。但我正在一台拥有200GB RAM的机器上运行脚本，我认为np.array对内存的需求更少... - Fabio Lamanna

类似这样的代码 import scipy.sparse as sps ... B = sps.lil_matrix((dim, dim)) - igavriil