私はページランクの背後にある考え方を理解し、それを実装しました（「集団知能のプログラミング」という本を読んだとき）。
しかし、私はそれが複数のサーバーに分散される可能性があることを読みました（Googleが行っていると思います）。私の理解によれば、各ランキングは他のランキングと相対的であるため、ページランクを行うにはグラフ全体が必要だったので、少し混乱しています。
ウィキの記事を見つけましたが、あまり説明がありませんでした。
これがどのように可能かについての提案はありますか? また、おまけの質問: 分散型ページランクを行う手法はページランク専用ですか?それとも、使用されている方法をグラフに適用される他の機械学習アルゴリズムに適用できますか?
PageRankを計算する最先端の方法は、GooglePregelフレームワークを使用しています。今はもっと洗練されたものがあると確信していますが、それは最新の公開された取り組みです。
詳細については、リサーチブログをご覧ください。または、ここで公開された論文を読んでください。
私はApacheHamaと呼ばれるBulkSynchronousParallelパラダイムのオープンソースバージョンに取り組んでいます。グラフのユースケースやその他の多くにのみ焦点を当てたApacheGiraphもあります。
前述のmfrankliと同様に、PageRankの計算に使用できるMapReduceフレームワーク（たとえば、Apache Hadoop）もありますが、反復アルゴリズムには効率的ではありません。
追加する注目すべき点は、両方のソリューション（MapReduceとBSP）がバッチソリューションであるため、完全なWebグラフのPageRankを再計算するために使用できることです。Googleの更新はバッチアルゴリズムよりもはるかに高速であるため、サブグラフのPageRankを頻繁に再計算することが期待できます。
させて
| 0 0 0 1 0 |
| 0 0 0 1 0 |
| 0 0 0 1 1 |
| 1 1 1 0 0 |
| 0 0 1 0 0 |
隣接行列 (またはグラフ) になります。M次に、PageRank の遷移行列は次のようになります。
| 0 0 0 1/3 0 |
| 0 0 0 1/3 0 |
| 0 0 0 1/3 1 |
| 1 1 1/2 0 0 |
| 0 0 1/2 0 0 |
これは列確率的、既約、および非周期的です。
MapReduce はここから始まります。マッパーのシリアル化された入力は次のようになります
1 -> 4
2 -> 4
3 -> 4 , 5
4 -> 1 , 2 , 3
5 -> 3
そしてマッパーは以下を出力します:
< 1 , [4] >
< 4 , 1 >
< 2 , [4] >
< 4 , 1 >
< 3 , [4 , 5] >
< 4 , 1/2 >
< 5 , 1/2 >
< 4 , [1, 2, 3] >
< 1 , 1/3 >
< 2 , 1/3 >
< 3 , 1/3 >
< 5 , [3] >
< 3 , 1 >
マッパーの出力はキーでグループ化され、リデューサーによって取得されます。レデューサーが 5 つある場合は、次のようになります。
R1 takes [4] , 1/3 then computes 1/5*(1/3) = 2/30
R2 takes [4] , 1/3 then computes 1/5*(1/3) = 2/30
R3 takes [4, 5] , 1/3 , 1 then computes 1/5*(1/3 + 1) = 8/30
R4 takes [1, 2, 3] , 1 , 1 , 1/2 then computes 1/5*( 1 + 1 + 1/2) = 15/30
R5 takes [3] , 1/2 then computes 1/5*(1/2) = 3/30
これで、最初の (パワー) 反復が終了しました。次のリデュース ジョブの間、リデューサーはマッパーが行うのと同じように発行しますが、1 の代わりに計算された PR が使用されます。
< 1 , [4] >
< 4 , 2/30 >
< 2 , [4] >
< 4 , 2/30 >
< 3 , [4 , 5] >
< 4 , 4/30 >
< 5 , 4/30 >
< 4 , [1, 2, 3] >
< 1 , 5/30 >
< 2 , 5/30 >
< 3 , 5/30 >
< 5 , [3] >
< 3 , 3/30 >
十分に収束するか満足するまで、reduce ジョブを繰り返します。
MapReduceはいくつかの興味深い背景を提供し、このタスクをどのように並列化するかを明らかにするかもしれません。