PageRank计算矩阵向量乘积的稀疏矩阵

我正在实现一些迭代算法来计算webgraph的PageRank，而且我在寻找存储内存矩阵的最佳方法时遇到了一些麻烦。PageRank计算矩阵向量乘积的稀疏矩阵

我有一个Bn x n矩阵，其rappresents的webgraph（B[i,j]=1/outdegree[j]如果有从j到i电弧，0否则; outdegree[j]是传出弧的从节点j数），并且我存储作为scipy.sparse.dok_matrix因为当然它主要有0条目。问题是我必须计算类型Px，其中

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

其中e是所有那些矢量和d是具有1在组分j如果outdegree[j] > 0一个布尔矢量的许多矩阵X向量积。基本上e*d^T是排序的线性代数“特技”的写n x n矩阵的列或者全部由1 S或0 S，取决于如果在d相应的条目是1或0。

所以我有两个挣扎，不是完全独立的，事情：

如何实现numpy的同样的“猫腻”，因为e*d.T简单地计算标产品，而我想要的矩阵。我想这是一些巧妙的广播和切片使用，但我仍然是新的numpy，并不能解决它
如果我只是定义P如上（假设我已找到解决方案1），我松散的存储优势，我获得存储B作为稀疏矩阵，突然我需要存储n^2浮游物。无论如何，我添加到B的矩阵非常多余（只有两种类型的列），所以必须有比存储整个矩阵更好的方法。有什么建议么？请记住，它是在一个方式，很容易让的P.dot(x)计算，为x任意向量

来源

2013-12-17 renato

如果您可以添加一些代码来生成适当形状/类型的示例输入变量（B，d，e等），将会有所帮助。 – YXD

对于简单起见，与np.dot表达式将是笨重的，让∙分别表示矩阵乘法，e，d和x是向量，即具有形状（N，1），和在用方括号*表达式是一个Python的列表multiplcation。然后，通过关联

(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)如果使用阵列）是向量乘积并且是相对于矩阵乘法的便宜操作。

来源

2013-12-17 11:25:25 alko

是的，我只是想出了本质上相同的东西，而不是在需要时编写'P.dot（x）'，我只是写'B.dot（x）+（d.dot（x）* e）/N'。这样我就解决了问题2并完全避免了问题1。 – renato

答案点1是：

numpy.outer

它创建一个从v1（M）阵列B（MXN）的基质和v2（N）阵列，使得B(i,j) = v1[i]*v2[j]

答案为2是更复杂的。

如果不再次需要B，你可以简单地把它定义为一个numpy.empty((n,n))，填补其作为问题的开始，然后B += (1/n)*np.outer(e, d)
如果n不是太大，大概有一疏或标准基质并没有太大的差别
如果可能考虑np.outer(e, d)为稀疏矩阵，然后尝试一些建议从this post

来源

2013-12-17 11:14:55

PageRank计算矩阵向量乘积的稀疏矩阵

回答

相关问题