【Google】PageRankの計算の仕方
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
NGNGここにGoogleで使われているPageRankのアルゴリズムが
書かれています。
そこで、一億×一億の正方行列を作り計算しようと思いましたが
PCのメモリ２GではOctaveを使って計算するにも
メモリ上にも載せれません。
別の公式かなにかはないのでしょうか？
00371
NGNG当方、ただいま約一億サイトの収集を完了したので。
0038１３２人目の素数さん
NGNG仮に N が 10^4 のオーダだったとしよう。
通常は数値計算プログラムの内部では行列やベクトルは倍精度で格納されるから、
N次正方行列 A の記憶領域は
sizeof(double) * N * N = 8 * 104 * 104 = 800MB となる。
さすがに、800MB の主記憶領域はなかなか持てるものではないだろうが、
とはいえ不可能な数字と言うわけでもない。
だが、N が 10^5 や 10^6 になると、それぞれ 80GB, 8TB となる。
こうなるとメモリどころかハードディスクでももうムリである。
Google では 10億以上のページを扱っているから(2001年時点)、
まともなやり方ではまったくダメであることがわかる。
もっとも、A は疎(sparse)な行列である。
リンクを張りまくっているページが一部にあったとしても、
Web全体に張っているものはないし、
あったとしてもそれは極めてまれな存在であるからだ。
平均的には、1ページあたり10-20リンク程度ではないだろうか
(IBM Almaden 研究所による 'Graph structure in the web'によれば、
平均すると 16.1 程度だそうである)。
だから、A は適切な圧縮方法を用いて圧縮できる。
N が 10^6 であっても平均リンク数を10とすれば 80MB で済み、
規模からいって無理のない数字に納めることができる。
0039１３２人目の素数さん
NGNGそこはわかったから、それ以外の加速法を聞いているわけで
004014
NGNG先日卒研発表があって、友達の発表を聞いたら、
Rubinsteinさんの論文では
1. 匿名性
2. 正の反応性
3. 無関係対象からの独立性
を満たすランキング方法は、勝ち数でランク付けする以外ないとのことでした。
0041１３２人目の素数さん
NGNG厨房でもわかりやすくお願いします
0042１３２人目の素数さん
NGNG0043１３２人目の素数さん
NGNG0044１３２人目の素数さん
NGNG難しいみたいだね
0045１３２人目の素数さん
NGNG0046１３２人目の素数さん
NGNG0047山崎渉
NGNG0048１３２人目の素数さん
NGNG0049d ◆GJenck4cmw
NGNG0050１３２人目の素数さん
NGNG0051１３２人目の素数さん
NGNGそのときの固有値は3.79067になりましたがこれに意味はあるんでしょうか？
0052１３２人目の素数さん
NGNG0053１３２人目の素数さん
NGNG２ちゃんアカデミーとか？
0054１３２人目の素数さん
NGNG0055山崎渉
NGNG0056山崎渉
NGNG（ ＾＾ ）＜ ぬるぽ（＾＾）
0057１３２人目の素数さん
NGNGの語源なの？
0058動画直リン
NGNG0059１３２人目の素数さん
NGNGGoogleだと17%はリンクさしてないサイトに等分にして配分。
83%をリンクしているサイトに配分するので。
1億ページ中のリンク構造モデルを用意しておいて。
1億ページ分のページランク領域を2つだけ確保すれば良いのです。
計算量も、くそマジメに計算するよりかなり減るです。
ちなみに自前検索エンジンで、キーワードに引っかかったサイト一覧の中の
リンク構造を元にページランクを動的に計算しているのですが、ページランクを
計算することによる負荷は殆ど発生してないです。
0060１３２人目の素数さん
NGNG0061山崎渉
NGNG0062山崎渉
NGNG0063山崎渉
NGNGﾋﾟｭ.ｰ ( ＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
＝〔~∪￣￣〕
＝ ◎――◎ 山崎渉
0064１３２人目の素数さん
NGNG0065１３２人目の素数さん
NGNG「PageRank をマルコフ過程の用語で言い直すならば、
PageRank は、ランダムにリンクをたどって動くユーザが一定の時間のうちに
それぞれのページを訪問する定常分布であるとも言える。」
ちゅうことなんで、モンテカルロ法じゃだめ?
かえって時間かかるかなあ?
0066１３２人目の素数さん
NGNG0067１３２人目の素数さん
NGNG0068ぼるじょあ ◆yBEncckFOU
NGNGﾋﾟｭ.ｰ （ ・３・） ( ＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
＝〔~∪￣￣￣∪￣￣〕
＝ ◎――――――◎ 山崎渉&ぼるじょあ
0069１３２人目の素数さん
NGNG0070１３２人目の素数さん
NGNG0071１３２人目の素数さん
NGNG0072１３２人目の素数さん
NGNG0073１３２人目の素数さん
NGNG0074１３２人目の素数さん
NGNG0075１３２人目の素数さん
NGNG0076１３２人目の素数さん
NGNG0077１３２人目の素数さん
NGNG0078１３２人目の素数さん
NGNG0079１３２人目の素数さん
NGNG0080１３２人目の素数さん
NGNG0081１３２人目の素数さん
NGNG0082１３２人目の素数さん
NGNG0083１３２人目の素数さん
NGNG0084１３２人目の素数さん
NGNGここみるとgoogleつくってる人たちのただもので無さが伝わってくる・・・
ぐーぐる、ぐーぐる簡単に言ってるけど実はけっこうすごいものなんだなぁと・・・
まあ、ジュリア集合の時点でちょっとそんな気してたけど・・・
0085１３２人目の素数さん
NGNGこんなの楽勝だろーが。
0086１３２人目の素数さん
NGNG0087１３２人目の素数さん
NGNG■ このスレッドは過去ログ倉庫に格納されています