デッドリンクの割合が高いスパース指示グラフのページランクの計算

Question

私はブルーミントンのインディアナ大学のコンピューターサイエンスの大学院生です。私の研究プロジェクトの1つでは、非常にまばらでデッドリンクの割合が高い指向グラフのPageranksの計算に取り組んでいます。

デッドリンクとは、ゼロがゼロのノードを意味します。多くのデッドリンクがあるグラフでは、クモのトラップが発生する場合があります。とにかく、私が興味を持っている問題は、このシナリオでページランクを見つけることです。

そして、私はページランクを計算するためにJung（Java Universal Graph Network）を使用しています。

通常の手順を使用するとき、

Graph<String, String> jungGraph = new DirectedSparseGraph<String, String>();
PageRank<String, String> pagerank = new PageRank<String,String>(jungGraph, 0.2);
pagerank.setMaxIterations(20);
pagerank.setTolerance(0.000001);
pagerank.evaluate();

すべてのノードに対して、多かれ少なかれ同じPagerank値を取得します。グラフの一部のノードには多数の発信ノードがあり、強く相互接続されています。

この場合、提案されているアプローチは何ですか。このクラスは、PagerankWithPriorsがあることを知っています。最初にデッドリンクなしでネットワークを抽出し、それらのページランクを計算してから、それらが収束するまでデッドリンクまでランクを伝播する必要がありますか？後者の場合、削減されたネットワークのすべてのノード（アウトドグリー！= 0）には、プライアーが設定されますが、デッドリンクは残りません。

ここで何かが足りませんか？

Answer 1

私は考えていません PageRankWithPriors あなたが望むものです。

どのバージョンのバージョン PageRank 使っていますか？クラス edu.uci.ics.jung.algorithms.importance.PageRank また edu.uci.ics.jung.algorithms.scoring.PageRank？前者は、Jung 2.0ベータ版で後者を支持して非難されています。

彼らは、外側の0ノードを異なる方法で扱うように見えますが、それがあなたの問題かもしれません。前者の仕様は次のように述べています

ノードuからノードVに移動する確率は（1-alpha）に等しい1/outsegree（u）] + alpha（1/| v |）

元のグラフに外出エッジがない場合、1/oututdegree（v）の代わりに0が使用されます。

確率の損失につながるため、それは間違っているように見えます（何らかの方法でuを離れる確率は1に等しいはずですが、そうではありません）。後者はそれを違って行います：

頂点に発信エッジがない場合、その頂点からランダムなジャンプを取得する確率は（デフォルトでは）効果的です1

それはあなたが望むものである確率を節約するはずです。