1

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

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

また、ページランクの計算には 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();

すべてのノードで多かれ少なかれ同じページランク値が得られますが、そうであってはならないことが明確にわかっています。グラフ内のいくつかのノードには多数の発信ノードがあり、強く相互接続されています。

この場合に推奨されるアプローチは何ですか。このクラス PageRankWithPriors があることは知っています。最初にデッドリンクのないネットワークを抽出し、それらのページランクを計算してから、それらのランクが収束するまでデッドリンクに伝播する必要がありますか? 後者の場合、削減されたネットワーク (出次数 != 0) 内のすべてのノードに事前確率が設定されますが、デッドリンクは設定されません。

ここで何か不足していますか？

4

1 に答える 1

1

私はあなたが望むものではないと思いPageRankWithPriorsます。

のどのバージョンPageRankを使用していますか? クラスedu.uci.ics.jung.algorithms.importance.PageRankかedu.uci.ics.jung.algorithms.scoring.PageRank？前者は、Jung 2.0 Beta で後者を支持して廃止されました。

出次数 0 ノードの扱いが異なるようです。これが問題である可能性があります。前者の仕様は次のように述べています。

ノード u からノード v に行く確率は (1-alpha) [1/outdegree(u)] + alpha (1/|V|)に等しい

u が元のグラフにアウトエッジを持たない場合、1/outdegree(v) の代わりに 0 が使用されます。

それは確率の損失につながるため、間違っているようです (何らかの方法で u を離れる確率の合計は 1 に等しくなるはずですが、そうではありません)。後者は別の方法で行います:

頂点に外向きのエッジがない場合、その頂点からランダムにジャンプする確率は (デフォルトで) 事実上 1 です。

それはあなたが望む確率を保存するはずです。

于 2010-09-08T18:20:05.670 に答える