JUNG圖表性能 - 緻密圖表上的PageRank

Question

我想知道如果我使用JUNG2和PageRank時遇到的相對較慢的性能是否合理，考慮到我正在使用的數據。

給定一個包含200個頂點和40000個邊的圖，計算該圖的PageRank大約需要15秒。給定一個具有〜900個頂點和〜800000個邊的圖，計算該圖的PageRank需要將近5分鐘的時間。

我意識到這些圖很密集，也許這自然會需要一段時間來計算。但是，這些圖形並不是特別大，按照這個速度，一次只能計算一小部分圖形是不可能的。 （10,000個頂點和100,000,000個邊緣大約需要8個小時）。

我正在使用一個DirectedSparseGraph與基元整數作爲頂點和邊緣，並沒有邊權重。這些顯然不是稀疏圖，所以也許有一個更合適的圖結構可用於密集圖更優化？

我在服務器模式下運行帶有大量堆空間的jvm，並確認整個圖形適合內存，並且不使用交換。

排名結果是正確的，總和爲1，並匹配榮格源和其他地方的測試示例。

也許有一個更高性能的方法和庫？但是，即使速度提高了10倍，是否它的時間複雜度與邊數成正比這一事實並不意味着我很快就會超出的限制，無論我使用的是什麼方法？

例如，我認爲只是完全跳過圖表方法，並使用矩陣來表示轉換概率，這可能會提供顯着提升。但是 - PageRank並不是我感興趣的唯一算法。如果我開始滾動我自己的方法來解決一個問題並引入其他幾個方法。另外，我在一個慢盒子，雙核1Ghz，所以，你的數字可能會好很多（比如我的第一個例子說4-5秒），但這一點成立。我主要關心的是，如果代碼預計會以更快的速度運行，或者預期以對數形式進行擴展。

無論如何，謝謝你的見解。

Answer 1

tl; dr：這是PageRank算法的一個固有限制，漸近地說。

任何想要考慮所有邊緣的算法將具有Omega（| E |）的時間複雜性。任何試圖測量全局拓撲性質的算法（例如PageRank等特徵向量度量）都必須至少查看一次邊緣。

您可以通過改變Graph實現來改進性能，但最終在密集圖上執行操作往往很昂貴。

框架問題：你的圖的語義是什麼，你希望通過 計算PageRank學到什麼？你想解決什麼問題？