【Google】PageRankの計算の仕方
38 ：１３２人目の素数さん：03/02/05 00:27
よく読んでからスレ立てろ。
仮に 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 で済み、
規模からいって無理のない数字に納めることができる。
仮に 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 で済み、
規模からいって無理のない数字に納めることができる。
39 ：１３２人目の素数さん：03/02/05 01:02
>>38
そこはわかったから、それ以外の加速法を聞いているわけで
そこはわかったから、それ以外の加速法を聞いているわけで
40 ：14：03/02/05 02:12
>>31
先日卒研発表があって、友達の発表を聞いたら、
Rubinsteinさんの論文では
1. 匿名性
2. 正の反応性
3. 無関係対象からの独立性
を満たすランキング方法は、勝ち数でランク付けする以外ないとのことでした。
先日卒研発表があって、友達の発表を聞いたら、
Rubinsteinさんの論文では
1. 匿名性
2. 正の反応性
3. 無関係対象からの独立性
を満たすランキング方法は、勝ち数でランク付けする以外ないとのことでした。
41 ：１３２人目の素数さん：03/02/05 03:20
>>40
厨房でもわかりやすくお願いします
厨房でもわかりやすくお願いします
42 ：１３２人目の素数さん：03/02/06 14:41
age
43 ：１３２人目の素数さん：03/02/07 00:50
age
44 ：１３２人目の素数さん：03/02/07 16:19
やっぱり ちゃねらーでは
難しいみたいだね
難しいみたいだね
45 ：１３２人目の素数さん：03/02/07 16:27
レスもろくに読んでない癖に何を言ってるのやら
46 ：１３２人目の素数さん：03/02/21 02:00
google
（＾＾）
48 ：１３２人目の素数さん：03/03/16 08:00
49 ：d ◆GJenck4cmw ：03/04/07 23:19
saですよ
50 ：１３２人目の素数さん：03/04/07 23:21
agだす
51 ：１３２人目の素数さん：03/04/08 10:51
>>9
そのときの固有値は3.79067になりましたがこれに意味はあるんでしょうか？
そのときの固有値は3.79067になりましたがこれに意味はあるんでしょうか？
52 ：１３２人目の素数さん：03/04/12 11:41
このテーマを修論にして誰かまとめれ。
53 ：１３２人目の素数さん：03/04/13 23:30
>>52
２ちゃんアカデミーとか？
２ちゃんアカデミーとか？
54 ：１３２人目の素数さん：03/04/14 00:34
いいえ、トリニティアカデミーです。
（＾＾）
∧＿∧
（ ＾＾ ）＜ ぬるぽ（＾＾）
（ ＾＾ ）＜ ぬるぽ（＾＾）
57 ：１３２人目の素数さん：03/05/11 22:23
ぐぐれ！
の語源なの？
の語源なの？
58 ：動画直リン：03/05/11 22:23
59 ：１３２人目の素数さん：03/05/19 23:27
1億ページの集合が有ったとしても、1億×1億の領域を確保する必要は無いのです。
Googleだと17%はリンクさしてないサイトに等分にして配分。
83%をリンクしているサイトに配分するので。
1億ページ中のリンク構造モデルを用意しておいて。
1億ページ分のページランク領域を2つだけ確保すれば良いのです。
計算量も、くそマジメに計算するよりかなり減るです。
ちなみに自前検索エンジンで、キーワードに引っかかったサイト一覧の中の
リンク構造を元にページランクを動的に計算しているのですが、ページランクを
計算することによる負荷は殆ど発生してないです。
Googleだと17%はリンクさしてないサイトに等分にして配分。
83%をリンクしているサイトに配分するので。
1億ページ中のリンク構造モデルを用意しておいて。
1億ページ分のページランク領域を2つだけ確保すれば良いのです。
計算量も、くそマジメに計算するよりかなり減るです。
ちなみに自前検索エンジンで、キーワードに引っかかったサイト一覧の中の
リンク構造を元にページランクを動的に計算しているのですが、ページランクを
計算することによる負荷は殆ど発生してないです。
60 ：１３２人目の素数さん：03/05/19 23:28
って、計算式とは関係なかったですね。。。
━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―
━―━―━―━―━―━―━―━―━[JR山崎駅（＾＾）]━―━―━―━―━―━―━―━―━―
∧＿∧
ﾋﾟｭ.ｰ ( ＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
＝〔~∪￣￣〕
＝ ◎――◎ 山崎渉
ﾋﾟｭ.ｰ ( ＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
＝〔~∪￣￣〕
＝ ◎――◎ 山崎渉
64 ：１３２人目の素数さん：03/06/09 11:50
12
65 ：１３２人目の素数さん：03/06/09 14:55
すんません、門外漢ですが、>>1のリンクによると
「PageRank をマルコフ過程の用語で言い直すならば、
PageRank は、ランダムにリンクをたどって動くユーザが一定の時間のうちに
それぞれのページを訪問する定常分布であるとも言える。」
ちゅうことなんで、モンテカルロ法じゃだめ?
かえって時間かかるかなあ?
「PageRank をマルコフ過程の用語で言い直すならば、
PageRank は、ランダムにリンクをたどって動くユーザが一定の時間のうちに
それぞれのページを訪問する定常分布であるとも言える。」
ちゅうことなんで、モンテカルロ法じゃだめ?
かえって時間かかるかなあ?
66 ：１３２人目の素数さん：03/07/06 05:02
10
67 ：１３２人目の素数さん：03/07/22 07:48
6
68 ：ぼるじょあ ◆yBEncckFOU ：03/08/02 03:29
∧＿∧ ∧＿∧
ﾋﾟｭ.ｰ （ ・３・） ( ＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
＝〔~∪￣￣￣∪￣￣〕
＝ ◎――――――◎ 山崎渉&ぼるじょあ
ﾋﾟｭ.ｰ （ ・３・） ( ＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
＝〔~∪￣￣￣∪￣￣〕
＝ ◎――――――◎ 山崎渉&ぼるじょあ
69 ：１３２人目の素数さん：03/08/16 06:15
14
70 ：１３２人目の素数さん：03/09/29 05:17
1
71 ：１３２人目の素数さん：03/10/22 04:22
18
72 ：１３２人目の素数さん：03/11/07 02:37
21
73 ：１３２人目の素数さん：03/12/01 07:22
20
74 ：１３２人目の素数さん：03/12/12 05:07
37
75 ：１３２人目の素数さん：03/12/18 06:02
17
76 ：１３２人目の素数さん：04/01/05 06:50
14
77 ：１３２人目の素数さん：04/01/13 07:32
22
78 ：１３２人目の素数さん：04/01/29 04:49
438
79 ：１３２人目の素数さん：04/02/01 06:43
620
80 ：１３２人目の素数さん：04/02/20 07:02
22
81 ：１３２人目の素数さん：04/03/07 00:35
172
82 ：１３２人目の素数さん：04/03/31 07:04
435
83 ：１３２人目の素数さん：04/04/06 10:06
345
84 ：１３２人目の素数さん：04/04/15 01:42
http://www.npr.org/programs/morning/features/2004/apr/google/
ここみるとgoogleつくってる人たちのただもので無さが伝わってくる・・・
ぐーぐる、ぐーぐる簡単に言ってるけど実はけっこうすごいものなんだなぁと・・・
まあ、ジュリア集合の時点でちょっとそんな気してたけど・・・
ここみるとgoogleつくってる人たちのただもので無さが伝わってくる・・・
ぐーぐる、ぐーぐる簡単に言ってるけど実はけっこうすごいものなんだなぁと・・・
まあ、ジュリア集合の時点でちょっとそんな気してたけど・・・
85 ：１３２人目の素数さん：04/04/15 01:53
おまえらなんのために数学勉強してんだよ・・・
こんなの楽勝だろーが。
こんなの楽勝だろーが。
86 ：１３２人目の素数さん：04/04/26 03:41
221
87 ：１３２人目の素数さん：
267