研究的PageRank實現

從this site閱讀PageRank算法的理論後，我想玩它。我想在Java中實現這一點。我的意思是我希望能夠與PageRank進行比較（比如賦予不同的權重等）。爲此，我需要構建超鏈接矩陣。如果我有1個萬個節點，然後我的超級鏈接矩陣將100萬X 1萬超大，導致此異常：研究的PageRank實現

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space 
    at WebGraph.main(WebGraph.java:6)

我如何在Java中實現的PageRank，是存儲有超鏈接矩陣的方法嗎？

來源

2012-11-04 torayeff

你從哪裏看過？你有沒有發現任何非開源實現？你有沒有考慮過自己實施它？你有對語言的偏好嗎？ – acattle

@acattle我曾看過Jung和WebLA。我想關注理論而不是實施。語言偏好：任何。 – torayeff

你是否嘗試過增加堆大小以擺脫該異常？ –

這是一個偉大的文章，瞭解pagerank。我實現了一個Perl版本here與Textrank一起使用。但是，如果您只想瞭解pagerank以及文章中討論的各個方面如何影響結果（阻尼因子，直接或無向圖等），我會建議在R或Octave中運行實驗。如果你想學習如何有效地實現它，那麼從頭開始對它進行編程是最好的。

大多數網絡圖（或網絡）都很sparse，這意味着該圖的矩陣表示中的大部分條目都是零。用於表示稀疏矩陣的常見數據結構是hash-map，其中不存儲零值。例如，如果基體是

1, 0, 0 
0, 0, 2, 
0, 3, 0

一個二維哈希圖將僅存儲於HM的值（0,0）= 1，HM（1,2）= 2，和HM（2,1 ）= 3。因此，在web graph的1,000,000乘以1,000,000的矩陣中，我預計只有幾百萬個值不爲零。如果每行平均只有5個非零值，哈希映射將使用大約5 *（8 + 8 + 8）* 10^6個字節〜115mb來存儲它（左邊的int索引爲8，右邊的int爲8索引，8爲雙值）。方陣將使用8 * 10^6 * 10^6〜7太字節。在Java中實現一個高效的稀疏矩陣向量乘法並不是微不足道的，如果不想爲該算法的這個方面投入時間，那麼已經有一些已經存在的implemented。稀疏矩陣乘法是實現pagerank算法最困難的方面，因此在這之後它變得更容易（也更有趣）。

來源

2012-11-17 00:48:14

Python networkx模塊有很好的pagerank實現。它使用scipy/numpy來實現矩陣。下面兩個關於stackoverflow的問題應該足以讓你開始。

來源

2012-11-12 06:04:13 greeness

由於丹W¯¯建議，嘗試增加堆大小。如果您從命令行運行Java應用程序，只需將交換機-Xmx添加到所需的堆大小。讓我們假設你編譯Java代碼到名爲pagerank.jar運行的JAR文件，並要將堆大小設置爲512 MB，您會發出以下命令：

java -jar -Xmx512m pagerank.jar

編輯： 但是，只有作品如果你沒有那麼多的「頁面」......一百萬×一百萬個陣列太大而無法放入你的RAM（1萬億次* 64位雙值= 7.27595761兆兆字節）。你應該改變你的算法，從磁盤加載數據塊，操作它，並將其存回磁盤。

您可以使用圖形數據庫，如Neo4j。

來源

2012-11-12 17:21:21

我有WebGraph.class，所以我跑：java -Xmx2048m WebGraph，但它仍然給OutOfMemoryError – torayeff

@torayeff：請參閱我編輯的答案。 1百萬* 1百萬個節點= 1萬億個單元。如果你使用一個雙數組（double可能是64位），這個數組可能超過7TB，這可能比你的RAM可以處理的多。 –

PageRank由Google使用'Pregel'BSP（真正的關鍵字）框架執行。

我記得Apache Giraph（另一個Pregel），其基準包中包含一個PageRank版本。

Here's a video about Giraph：這是一個介紹，它具體談到處理PageRank。

如果不工作：

在Java中有預凝膠的實現稱爲GoldenOrb。

PageRank算法的僞代碼是here（在不同的Pregel實現上）。

您必須閱讀BSP和PageRank才能處理您擁有的數據大小。

來源

2012-11-12 17:31:27 Tom

您不必存儲整個1000000x1000000矩陣，因爲大多數矩陣條目將爲零。相反，您可以（例如）爲每行存儲一個非零條目列表，然後編寫您的矩陣函數以直接使用它，而不必將其擴展爲完整的矩陣。

這種壓縮表示形式被稱爲sparse matrix格式，大多數矩陣庫可以選擇構建和使用稀疏矩陣。

稀疏矩陣的一個缺點是將它們中的兩個相乘會導致矩陣不夠稀疏。但是，PageRank算法的設計使您無需這樣做：超鏈接矩陣是恆定的，只有得分向量被更新。

來源

2012-11-12 18:09:29 comingstorm

幾點建議：

使用Python，而不是Java：蟒蛇是一個優秀的原型語言，並具有可稀疏矩陣（在SciPy的）以及許多其他的東西。正如其他人所指出的那樣，它也有一個pagerank實現。
存儲你的數據不是所有的內存：任何類型的輕量級數據庫的就可以了，比如sqlite的，休眠，...
上的數據的瓦片工作：如果有一個大的N×N的矩陣，將其分解成小塊瓷磚MxM，其中M是N的一小部分，適合記憶。結合稀疏矩陣，您可以使用非常大的N（從數億到數十億，取決於數據的稀疏程度）。

來源

2012-11-16 11:10:16

因爲矩陣很稀疏，所以可以實現像svd，pca，mds或Lsi這樣的包含svd的降維。有一個圖書館來實施這種稱爲賈馬的過程。你可以找到它here

來源

2012-11-16 13:00:27

研究的PageRank實現

回答

相關問題