JUNG圖 - 帶無向圖和加權邊的PageRank

我在帶有加權邊的無向圖上實現PageRank。我的的理解是，因爲我的圖是無向的，所以代表邊權重的概率將根據起始頂點的不同而有所不同。這是有道理的，因爲概率必須爲頂點的出站邊界的總數爲1，但邊緣的每個入射頂點將具有不同的要求，這意味着我不能在它們之間具有公共轉換概率。（如果這種理解錯誤，請糾正我）。JUNG圖 - 帶無向圖和加權邊的PageRank

但是，我遇到了麻煩，因爲測試和文檔中的示例只使用簡單的邊權重，而我需要VertexEdge鍵對權重（我認爲）。當替代標準整數鍵控邊權時，VEPair類拋出空指針異常。

的語義如下：

我創建UndirectedSparseGraph，我添加頂點0，1，2，3。

g.addVertex(0); 
g.addVertex(1); 
g.addVertex(2); 
g.addVertex(3);

然後到該圖中，予添加邊緣0,1， 2，3.連接頂點0 => 1 1 => 2 2 => 3 3 => 0，即，

g.addEdge(0, 0, 1); 
g.addEdge(1, 1, 2); 
g.addEdge(2, 2, 3); 
g.addEdge(3, 3, 0);

我在0.5等於邊緣權重增加爲每個頂點。

map.put(0, 0.5); 
map.put(1, 0.5); 
map.put(2, 0.5); 
map.put(3, 0.5);

我實例使用圖形的PageRank的，轉化的邊緣的權重，和0α，即：現在

pr = new PageRank(g, MapTransformer.getInstance(map), 0);

，每個頂點評分結果在0.25，這是正確的，即：

pr.getVertexScore(0); // 0.25 
pr.getVertexScore(1); // 0.25

我的問題是，我不能簡單地在邊緣上有邊緣權重，因爲圖形是無向的。邊緣的權重必須根據起點頂點而不同，因爲頂點的所有出站邊緣的邊緣權重必須等於1.所以我需要一種不是說邊緣0的權重爲x，而是邊緣0有x的頂點0的頂點1.

所以，我想這可能是可以使用VEPair類在我maptransformer的重量，和Y，而不是整數之上，即：

map.put(new VEPair(0, 0), 0.5); 
map.put(new VEPair(1, 0), 0.5); 
map.put(new VEPair(1, 1), 0.5); 
map.put(new VEPair(2, 1), 0.5); 
map.put(new VEPair(2, 2), 0.5); 
map.put(new VEPair(3, 2), 0.5); 
map.put(new VEPair(3, 3), 0.5); 
map.put(new VEPair(0, 3), 0.5);

所以，語義是相同的，我只是明確指定每個邊緣給定一個起點頂點的權重。

調用pr.evaluate（），但是會導致空指針異常的PageRankWithPriors.update線87（）

尤其是代碼試圖獲得指定的第一個邊緣的重量，它是零。

請注意，僅使用apache.commons中的普通舊版MapTransformer與VEPairs作爲關鍵字將始終導致空值，因爲VEPair類尚未實現hashCode或equals。所以VEPair（0,0）不等於VEPair（0,0）。我是否只需要重寫此類並提供相等語義以使其工作？或者我完全使用錯誤的方法？

感謝您的幫助。

來源

2014-10-20 Scott

請添加更多關於您的需求的上下文（您希望邊權重的語義是什麼？），並提供詳細信息（帶代碼段的堆棧跟蹤將是理想的）。 – 2014-10-21 01:18:49

對不起@Joshua遲到了。我已經添加了更多細節，希望能夠告訴你我想要達到的目標。讓我知道它是否不足。由於我使用的是Clojure而不是Java，因此代碼和跟蹤並不準確，所以希望我提供的內容足以讓我指出正確的方向。 – Scott 2014-10-25 19:18:52

你知道，我猜對我的問題最簡單的解決方案就是使用帶有來自和來自每個頂點的邊的有向圖，並且可以將邊的權重綁定到頂點而不必求助於上面的VEPair方法。 – Scott 2014-10-26 06:30:44

VEPair是不是真的適合外用。它在內部非常用於處理常見情況（邊緣權重隱式統一的無向圖）。

我看到你已經有一個可以爲你工作的解決方案，但是如果你想要一個不需要你創建一個新的DirectedGraph的解決方案，你可以覆蓋PageRank的getEdgeWeight（V，E）方法在AbstractIterativeScorer中實現）根據無向邊權重執行任何你想要的操作。

來源

2014-11-03 01:59:59

我推翻了getEdgeWeight，它與DirectedSparseGraph方法的結果相同，但只需要殺死兩隻鳥的一半邊緣（因爲我也有性能問題）。感謝那。 – Scott 2014-11-26 03:43:09

JUNG圖 - 帶無向圖和加權邊的PageRank

回答

相關問題