python - PageRank 计算中矩阵向量积的稀疏矩阵

Question

我正在实现一些迭代算法来计算网络图的 PageRank，但在寻找在内存中存储某些矩阵的最佳方法时遇到了一些麻烦。

我有一个 B n x n 矩阵，它表示网络图( B[i,j]=1/out Degree[j] if有一条从j到i的弧，否则为0；出度[j]是从节点j)，我将其存储为scipy.sparse.dok_matrix，因为它当然主要有0条目。问题是我必须计算许多 Px 类型的矩阵 x 向量乘积，其中

P = B + (1/n)*e*d^T

其中 e 是全 1 向量，d 是一个 bool 向量，在组件 j 中具有 1如果出度[j] > 0。基本上，e*d^T 是一种线性代数“技巧”，用于编写一个 n x n 矩阵，其列要么全部由 1 组成，要么0s，取决于d中的相应条目是1还是0。

所以我正在努力解决两件事，而不是完全独立的事情:

1. 如何在 numpy 中实现相同的“技巧”，因为 e*d.T 只是计算标量积，而我想要一个矩阵。我想这是广播和切片的一些巧妙使用，但我对 numpy 还很陌生，无法弄清楚
2. 如果我简单地按照上面的方式定义 P(假设我找到了 1 的解决方案)，我就会失去将 B 存储为稀疏矩阵所获得的内存优势，突然我需要存储 n^2 float 。无论如何，我添加到 B 的矩阵非常冗余(只有两种类型的列)，因此必须有一种比将整个矩阵存储在内存中更好的方法。有什么建议么？请记住，它必须能够轻松计算 P.dot(x)，因为 x 是任意向量

Answer 1

为了简单起见，由于 np.dot 的表达式会很庞大，让 ∙ 表示矩阵乘法，e, d 和 x 是向量，即具有形状 (n, 1)，并且在带有方括号的表达式中 * 是 python 的列表乘法。然后，根据关联性

(e∙d.T)∙x = e∙(d.T∙x) = [[d.T∙x] * n]

其中 d.T∙x 是标量，并且

P∙x = B∙x + 1/n * e∙d.T∙x = B∙x + 1/n * [[d.T∙x] * n]

为了能够进行计算，您可以仅存储向量 d。请注意，d.T∙x(如果使用数组，则等效于 np.dot(d.T, x))是向量乘积，并且相对于矩阵乘法来说是一种廉价的运算。