【Google】PageRankの計算の仕方
1 ：１３２人目の素数さん：
http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.html
ここにGoogleで使われているPageRankのアルゴリズムが
書かれています。
そこで、一億×一億の正方行列を作り計算しようと思いましたが
PCのメモリ２GではOctaveを使って計算するにも
メモリ上にも載せれません。
別の公式かなにかはないのでしょうか？
ここにGoogleで使われているPageRankのアルゴリズムが
書かれています。
そこで、一億×一億の正方行列を作り計算しようと思いましたが
PCのメモリ２GではOctaveを使って計算するにも
メモリ上にも載せれません。
別の公式かなにかはないのでしょうか？
|
|
|
2 ：１３２人目の素数さん：03/02/01 09:17
だれも答えられないね
3 ：１３２人目の素数さん：03/02/01 09:46
仮想メモリじゃダメなの？
4 ：１３２人目の素数さん：03/02/01 10:11
∧_∧ ／￣￣￣￣￣
(ω・ )ゝ ＜ なんだって？
. ノ/ / ＼＿＿＿＿＿
ノ￣ゝ
5 ：１３２人目の素数さん：03/02/01 10:38
64bit環境にすれば？
6 ：１３２人目の素数さん：03/02/01 16:43
32bitでしたいのれす
7 ：１３２人目の素数さん：03/02/01 16:46
無理
8 ：１３２人目の素数さん：03/02/01 20:44
一億×一億のデータがそもそも入りきんないだろ。
9 ：１３２人目の素数さん：03/02/01 20:49
行列の固有ベクトルに関連して。
リーグ戦で
Ａ Ｂ Ｃ Ｄ
Ａ ＼○○×
Ｂ ×＼○○
Ｃ ××＼○
Ｄ ○××＼
っつう結果だったら、
1 2 2 0
0 1 2 2
0 0 1 2
2 0 0 1ていう行列の固有ベクトルを求めて、すべての成分が皮膚の物を探すと、
{0.62563, 0.551628, 0.321336, 0.448372}
てのがあるから、Ａ〜Ｄの実力の比率はこんなもんだろうと分かる。
リーグ戦で
Ａ Ｂ Ｃ Ｄ
Ａ ＼○○×
Ｂ ×＼○○
Ｃ ××＼○
Ｄ ○××＼
っつう結果だったら、
1 2 2 0
0 1 2 2
0 0 1 2
2 0 0 1ていう行列の固有ベクトルを求めて、すべての成分が皮膚の物を探すと、
{0.62563, 0.551628, 0.321336, 0.448372}
てのがあるから、Ａ〜Ｄの実力の比率はこんなもんだろうと分かる。
10 ：１３２人目の素数さん：03/02/01 23:57
>>9
友達が卒論で、こういうスポーツのリーグ戦などの最終的な順位付けについて
グラフ構造にもっていって順位付けの方法を公理化するなんてことをやっていて、
勝ち2, 引き分け1, 負け0のときの公理だかなんだかを
卒論提出の二週間前にやりはじめて、最終的に4つぐらいの公理におさまったらしいのだが、
証明などが膨大な量になってしまって、指導教官がチェックを投げ出してしまった。
引き分けがない状態では、勝ち数のみで順位を決定する方式が
非常にシンプルな公理で表されているみたいです。
友達が卒論で、こういうスポーツのリーグ戦などの最終的な順位付けについて
グラフ構造にもっていって順位付けの方法を公理化するなんてことをやっていて、
勝ち2, 引き分け1, 負け0のときの公理だかなんだかを
卒論提出の二週間前にやりはじめて、最終的に4つぐらいの公理におさまったらしいのだが、
証明などが膨大な量になってしまって、指導教官がチェックを投げ出してしまった。
引き分けがない状態では、勝ち数のみで順位を決定する方式が
非常にシンプルな公理で表されているみたいです。
11 ：１３２人目の素数さん：03/02/01 23:58
>>8
そこを考えてほしいなりけり
そこを考えてほしいなりけり
12 ：１３２人目の素数さん：03/02/02 00:00
13 ：１３２人目の素数さん：03/02/02 00:11
2chの数学板でもこのあたりに詳しい人はいないのね
14 ：１３２人目の素数さん：03/02/02 00:18
>>12
引き分けがない状態での公理は、
Ranking the Participants in a Tournament,
Journal of the Society of Industrial and Applied Mathematics 38 (1980), 108-111.
に書いてあるんだけど、論文捨てちゃった(作者は経済の人みたい)。
覚えているのは、「公理I: Anonimity」だけ・・・
引き分けがない状態での公理は、
Ranking the Participants in a Tournament,
Journal of the Society of Industrial and Applied Mathematics 38 (1980), 108-111.
に書いてあるんだけど、論文捨てちゃった(作者は経済の人みたい)。
覚えているのは、「公理I: Anonimity」だけ・・・
15 ：１３２人目の素数さん：03/02/02 00:22
馬場氏のページには、
"Google での実際の PageRank 計算に要する時間は、7500万のURLに対して約5時間だったそうである。
(2001年2月現在でどうなっているかは不明)。
このことからすると、
より効率的な加速法を検討する余地が十分に残されていることは言えるだろう。 "
らしいから、何か方法があるのかな？
２ちゃねらーで導けば、すごいよね 笑
"Google での実際の PageRank 計算に要する時間は、7500万のURLに対して約5時間だったそうである。
(2001年2月現在でどうなっているかは不明)。
このことからすると、
より効率的な加速法を検討する余地が十分に残されていることは言えるだろう。 "
らしいから、何か方法があるのかな？
２ちゃねらーで導けば、すごいよね 笑
16 ：１３２人目の素数さん：03/02/02 00:43
17 ：１３２人目の素数さん：03/02/02 00:50
http://www.searchdesk.com/survey/svy2002.htm
2月7日のWeb記事に"Understanding and Building Google PageRank"という英文の解説記事があります。
ページランクはInternal Linking と External Linking を使っているとのことです。私が十数年前に
リファレーション（Referations = References + Document + Citations）を使った文献検索技術を研究していましたが、
まだDocumentの部分が含んでないように思います。いろいろな測度を計算するのに、データ数が多く、しかもSparse行列を
解くのは不可能です。この難解な測度を非常に簡単なアルゴリズムで求める方法を十数年前に開発しています。
それにしてもGoogleの躍進でリンクが脚光を浴びてきたことは大変望ましい状況です。
2月7日のWeb記事に"Understanding and Building Google PageRank"という英文の解説記事があります。
ページランクはInternal Linking と External Linking を使っているとのことです。私が十数年前に
リファレーション（Referations = References + Document + Citations）を使った文献検索技術を研究していましたが、
まだDocumentの部分が含んでないように思います。いろいろな測度を計算するのに、データ数が多く、しかもSparse行列を
解くのは不可能です。この難解な測度を非常に簡単なアルゴリズムで求める方法を十数年前に開発しています。
それにしてもGoogleの躍進でリンクが脚光を浴びてきたことは大変望ましい状況です。
18 ：１３２人目の素数さん：03/02/02 01:06
http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=2002-6&format=pdf&compression=
これは関係ないよね？
これは関係ないよね？
19 ：１３２人目の素数さん：03/02/02 01:11
http://www.rakuten.co.jp/elblanco/img1005177827.jpeg
これはもっと関係ないよね
これはもっと関係ないよね
20 ：１３２人目の素数さん：03/02/02 14:34
>>19
ﾜﾗﾀ
ﾜﾗﾀ
21 ：１３２人目の素数さん：03/02/03 00:15
ちゃねらー 期待あげ
22 ：１３２人目の素数さん：03/02/03 02:19
ふ〜ん…今日はじめて数学板のぞいたけど面白いね
これ、俺わかるよ。加速方法もなんとなく予想できる。
>収束が遅いというのは、ベタな言葉で言えば、いつまで経っても計算が
>終らないということである。 対して、収束を速めるための 適当な加速法も
>いくつか存在することは存在するが、 それらを適用するためには数値計算
>技法に対する十二分な理解が必要と なるため、 数値計算の専門家でない限
>りは導入は易しいものではない。
って勉強すればいいじゃん。Googleのやつは勉強ぎらいなのか？
これ、俺わかるよ。加速方法もなんとなく予想できる。
>収束が遅いというのは、ベタな言葉で言えば、いつまで経っても計算が
>終らないということである。 対して、収束を速めるための 適当な加速法も
>いくつか存在することは存在するが、 それらを適用するためには数値計算
>技法に対する十二分な理解が必要と なるため、 数値計算の専門家でない限
>りは導入は易しいものではない。
って勉強すればいいじゃん。Googleのやつは勉強ぎらいなのか？
あら、最後にこんなこと書いてあったわ。
>あまり軽々しく考えてはいけない。
スマソ。じゃあもっと深く考えてみるか。
>あまり軽々しく考えてはいけない。
スマソ。じゃあもっと深く考えてみるか。
24 ：１３２人目の素数さん：03/02/03 18:36
25 ：１３２人目の素数さん：03/02/03 18:37
やっぱりこれはすんごい関係ないよね
26 ：22：03/02/03 19:40
27 ：１３２人目の素数さん：03/02/03 19:45
>>26
悪いけどそれはびっくりするほど関係ないね
悪いけどそれはびっくりするほど関係ないね
28 ：１３２人目の素数さん：03/02/03 20:41
数学板の人はね、物事の元の元から考えるんですね。
だいたい今のPCってのはよくわからないものをオブジェクト、つまり一個の者として扱ってるんですね、
それを「2進数だよね?」とかいって考えるのが数学板の人なんだよね。
それが数それが数学板の人なんだよねれそれが数それが数学それが数学板の人なんだよね。板の人なんだよね。なんだよね。なんだよね。
だいたい今のPCってのはよくわからないものをオブジェクト、つまり一個の者として扱ってるんですね、
それを「2進数だよね?」とかいって考えるのが数学板の人なんだよね。
それが数それが数学板の人なんだよねれそれが数それが数学それが数学板の人なんだよね。板の人なんだよね。なんだよね。なんだよね。
29 ：１３２人目の素数さん：03/02/04 03:10
>>22
ここでご披露願いたいものです。
ここでご披露願いたいものです。
30 ：１３２人目の素数さん：03/02/04 05:58
こういうスレはシミュレーション板じゃないのかなあ
31 ：１３２人目の素数さん：03/02/04 09:20
32 ：１３２人目の素数さん：03/02/04 11:47
要するに
２ ｃ ｈ の 有 名 な ス レ に 書 き こ め ば Ｐ ａ ｇ ｅ Ｒ ａ ｎ ｋ が 上 が る
２ ｃ ｈ の 有 名 な ス レ に 書 き こ め ば Ｐ ａ ｇ ｅ Ｒ ａ ｎ ｋ が 上 が る
33 ：１３２人目の素数さん：03/02/04 11:52
有名なスレ≒伸びが速い
クローラが訪問するころにはとっくに次スレ移行してそのスレはdat落ちしてますが。
人間と違ってpartXXなどのシリーズモノかどうかの判別はできない。
クローラが訪問するころにはとっくに次スレ移行してそのスレはdat落ちしてますが。
人間と違ってpartXXなどのシリーズモノかどうかの判別はできない。
34 ：１３２人目の素数さん：03/02/04 13:08
おまえらな、難しく考えすぎですよ。もっと素直に考えろよ。
近似固有値を計算したいだけだろ？ ミロ↓
http://www.rakuten.co.jp/elblanco/img1005180869.jpeg
近似固有値を計算したいだけだろ？ ミロ↓
http://www.rakuten.co.jp/elblanco/img1005180869.jpeg
36 ：１３２人目の素数さん：03/02/04 19:36
>>1
実際のところ1億×1億の全ての要素が埋まっているわけではなく
むしろそのほとんどが0なわけだから、そこらへんを上手く扱うと
メモリに収まるのかもしれない。
(これは1のリンク先にも書いてあるけど)
ただ数学でもシミュでも共通して言えることだが
いきなり1億なんてやらずに、ある程度閉じた環境でローカルの
ランキングとか計るとかしてみたほうがいいのではないかと思う。
1億サイトのランキングを計算する意味って何よ？ >>1
実際のところ1億×1億の全ての要素が埋まっているわけではなく
むしろそのほとんどが0なわけだから、そこらへんを上手く扱うと
メモリに収まるのかもしれない。
(これは1のリンク先にも書いてあるけど)
ただ数学でもシミュでも共通して言えることだが
いきなり1億なんてやらずに、ある程度閉じた環境でローカルの
ランキングとか計るとかしてみたほうがいいのではないかと思う。
1億サイトのランキングを計算する意味って何よ？ >>1
37 ：1：03/02/04 20:50
>>36
当方、ただいま約一億サイトの収集を完了したので。
当方、ただいま約一億サイトの収集を完了したので。
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