3

このサイトから PageRank アルゴリズムの理論を読んだ後、それで遊んでみたいと思います。これをJavaで実装しようとしています。つまり、PageRank を詳細に操作したいと考えています (さまざまな重み付けなど)。このために、ハイパーリンク マトリックスを作成する必要があります。100 万のノードがある場合、ハイパーリンク マトリックスは 100 万 x 100 万のサイズになり、次の例外が発生します。

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

JavaでPageRankを実装するにはどうすればよいですか?ハイパーリンクマトリックスを保存する方法はありますか?

4

7 に答える 7

8

これは、ページランクについて学ぶのに最適な記事です。ここから Perl バージョンを実装して、 Textrankで使用します。ただし、ページランクと、記事で説明したさまざまな側面 (減衰係数、直接グラフまたは無向グラフなど) が結果にどのように影響するかについて知りたい場合は、RまたはOctaveで実験を実行することをお勧めします。効率的に実装する方法を学びたい場合は、現在行っているようにゼロからプログラミングするのが最善です。

ほとんどの Web グラフ (またはネットワーク) は非常にまばらです。これは、グラフの行列表現のほとんどのエントリがゼロであることを意味します。スパース行列を表すために使用される一般的なデータ構造はhash-mapで、ゼロ値は保存されません。たとえば、マトリックスが

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

2 次元のハッシュ マップは、hm(0,0)=1、hm(1,2)=2、および hm(2,1)=3 の値のみを格納します。したがって、 Web グラフの 1,000,000 x 1,000,000 マトリックスでは、ゼロ以外の値は数百万しかないと予想されます。各行の平均値がゼロ以外の値が 5 つだけの場合、ハッシュマップは約 5*(8+8+8)*10^6 バイト ~ 115MB を使用して格納します (左の int インデックスに 8、右の int に 8)。 index、double 値の場合は 8)。正方行列は 8*10^6*10^6 ~ 7 テラバイトを使用します。

Java で効率的なスパース行列とベクトルの乗算を実装するのは簡単ではありません。アルゴリズムのその側面に時間を割きたくない場合は、既に実装されているものもあります。疎行列の乗算は、pagerank アルゴリズムの実装が最も難しい側面であるため、その後は簡単になります (そしてより興味深いものになります)。

于 2012-11-17T00:48:14.553 に答える
4

Pythonnetworkxモジュールには、pagerankの優れた実装があります。マトリックスの実装にはscipy/numpyを使用します。スタックオーバーフローに関する以下の2つの質問は、始めるのに十分なはずです。

于 2012-11-12T06:04:13.910 に答える
2

いくつかの提案:

  • Java ではなく Python を使用してください: Python は優れたプロトタイピング言語であり、(scipy で) 利用可能なスパース行列や他の多くの優れた機能を備えています。他の人が指摘したように、ページランクの実装もあります。

  • すべてのデータをメモリに保存するわけではありません。たとえば、sqlite、hibernate など、どのタイプの軽量データベースでも問題ありません。

  • データのタイルで作業します。大きな行列 NxN がある場合は、メモリに収まる小さなタイル MxM (M は N の一部) に分割します。スパース行列と組み合わせると、非常に大きな N (データのスパース度に応じて、数億から数十億) を扱うことができます。

于 2012-11-16T11:10:16.660 に答える
0

Dan Wが提案したように、ヒープサイズを大きくしてみてください。コマンドラインからJavaアプリケーションを実行する場合は-Xmx、必要なヒープサイズでスイッチを追加するだけです。Javaコードをと呼ばれる実行可能なJARファイルにコンパイルしpagerank.jar、ヒープサイズを512 MBに設定したい場合は、次のコマンドを発行します。

java -jar -Xmx512m pagerank.jar

編集： しかし、それはあなたがそれほど多くの「ページ」を持っていない場合にのみ機能します...100万×100万の配列はRAMに収まるには大きすぎます（1兆倍*64ビット倍精度=7.27595761テラバイト）。アルゴリズムを変更して、ディスクからデータのチャンクをロードし、操作して、ディスクに保存する必要があります。

そのために、Neo4jのようなグラフデータベースを使用できます。

于 2012-11-12T17:21:21.753 に答える
0

ほとんどの行列エントリはゼロになるため、1000000x1000000 行列全体を保存する必要はありません。代わりに、(たとえば) 各行の非ゼロ エントリのリストを格納し、それを完全な行列に展開せずに直接使用するように行列関数を記述できます。

この種の圧縮された表現は疎行列形式と呼ばれ、ほとんどの行列ライブラリには、疎行列を構築して操作するためのオプションがあります。

疎な行列の欠点の 1 つは、2 つの行列を乗算すると、疎でない行列が得られることです。ただし、PageRank アルゴリズムは、その必要がないように設計されています。ハイパーリンク マトリックスは一定で、スコア ベクトルのみが更新されます。

于 2012-11-12T18:09:29.397 に答える
0

行列が疎であるため、svd、pca、mds、または svd を含む Lsi のような次元削減を実装できます。Jama と呼ばれるこの種のプロセスを実装するためのライブラリがあります。ここで見つけることができます

于 2012-11-16T13:00:27.987 に答える
0

PageRank は、「Pregel」BSP (実際には単なるキーワード) フレームワークを使用して Google によって実行されます。

ベンチマーク パッケージに PageRank のバージョンが含まれているApache Giraph (別の Pregel)を思い出しました。

これは Giraph に関するビデオです。これは紹介であり、PageRank の処理について具体的に説明しています。

それでもうまくいかない場合:

Java には、GoldenOrbと呼ばれる Pregel の実装があります。

PageRank アルゴリズムの疑似コードはこちら(Pregel の別の実装) にあります。

持っているデータのサイズを処理するには、BSP と PageRank を読み解く必要があります。

于 2012-11-12T17:31:27.287 に答える