我正在实现一些迭代算法来计算网络图的 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
组成,要么0
s,取决于d
中的相应条目是1
还是0
。
所以我正在努力解决两件事,而不是完全独立的事情:
- 如何在 numpy 中实现相同的“技巧”,因为
e*d.T
只是计算标量积,而我想要一个矩阵。我想这是广播和切片的一些巧妙使用,但我对 numpy 还很陌生,无法弄清楚 - 如果我简单地按照上面的方式定义
P
(假设我找到了 1 的解决方案),我就会失去将B
存储为稀疏矩阵所获得的内存优势,突然我需要存储n^2
float 。无论如何,我添加到 B 的矩阵非常冗余(只有两种类型的列),因此必须有一种比将整个矩阵存储在内存中更好的方法。有什么建议么?请记住,它必须能够轻松计算P.dot(x)
,因为x
是任意向量
最佳答案
为了简单起见,由于 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)
)是向量乘积,并且相对于矩阵乘法来说是一种廉价的运算。
关于python - PageRank 计算中矩阵向量积的稀疏矩阵,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20632533/