PageRank計算矩陣向量乘積的稀疏矩陣

Question

我正在實現一些迭代算法來計算webgraph的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。

所以我有兩個掙扎，不是完全獨立的，事情：

1. 如何實現numpy的同樣的「貓膩」，因爲e*d.T簡單地計算標產品，而我想要的矩陣。我想這是一些巧妙的廣播和切片使用，但我仍然是新的numpy，並不能解決它
2. 如果我只是定義P如上（假設我已找到解決方案1），我鬆散的存儲優勢，我獲得存儲B作爲稀疏矩陣，突然我需要存儲n^2浮游物。無論如何，我添加到B的矩陣非常多餘（只有兩種類型的列），所以必須有比存儲整個矩陣更好的方法。有什麼建議麼？請記住，它是在一個方式，很容易讓的P.dot(x)計算，爲x任意向量

Answer 1

對於簡單起見，與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)如果使用陣列）是向量乘積並且是相對於矩陣乘法的便宜操作。

Answer 2

答案點1是：

numpy.outer

它創建一個從v1（M）陣列B（MXN）的基質和v2（N）陣列，使得B(i,j) = v1[i]*v2[j]

答案爲2是更復雜的。

1. 如果不再次需要B，你可以簡單地把它定義爲一個numpy.empty((n,n))，填補其作爲問題的開始，然後B += (1/n)*np.outer(e, d)
2. 如果n不是太大，大概有一疏或標準基質並沒有太大的差別
3. 如果可能考慮np.outer(e, d)爲稀疏矩陣，然後嘗試一些建議從this post