Googleのページランク
W
• 基本的な仕組は数学的
W 0
グラフの行列による表現
隣接行列（推移行列、遷移行列） S 0
C 0
固有値と固有ベクトル
G 1
S学部
W大学
C学科
G研究室
S C G
1 0 0
0 1 0
0 0 1
1 1 0
1 頂点iから頂点 jに辺がある
aij
０ 頂点iから頂点 jに辺がない
行列の上と左のW, S, C, Gは注釈
であり行列に含まれない
WEBページのリンクの関係
1
隣接行列を転置する
• 隣接行列 A (aij ) を転置する
リンクを「出す」側から「受ける」側へ
S学部
C学科
A
t
W大学
G研究室
WEBページのリンクの関係
0
1
0
0
0
0
1
0
0
0
0
1
1
1
1
0
2
隣接行列から推移確率行列へ
• 列(column)の総和が１または０になるように調整
ページの評価値をリンク先に渡す
１
S学部
１
1/3
W大学
1/3
C学科
1/3
１
G研究室
M
0
1
0
0
0 0
0 0
1 0
0 1
1
3
1
3
1
3
0
WEBページのリンクの関係
3
推移確率行列の固有値と固有ベクトル
• 固有値λと固有ベクトルｒ
M r r
• 行列 M を掛ける（乗算）ということは、グラフの
辺に沿って（確率的に）推移するということである
• 固有ベクトルの各要素は M を掛けても定数倍
しか変化しない。（安定している）
固有ベクトルの各要素がランクになる
（ただし要素の和が１となるように正規化する）
4
固有ベクトルの具体例
• GNU Octaveを使って計算する。固有値λ＝１が最大
の固有値であり、固有ベクトルは下の左のようになる。
0.11111
0.22222
0.33333
0.33333
0.20851
0.41703
0.62554
0.62554
• これを正規化したページランクは上の右である。
2/9
１
１
S学部
1/3
1/9
W大学
1/3
C学科
1/3
1/3
１
G研究室
ページランクを記入した図
1/3
5
Googleにおける工夫
• サイズの大きな
疎(sparse)行列の
固有ベクトルの計算
• ユーザがランダムに
ページを渡り歩くと仮定
S学部
W大学
1 N
N 4
1
4
1
4
1
4
1
4
1
1
1
1
4
4
4
4
1
1
1
1
4
4
4
4
1
4
1
4
1
4
1
4
C学科
G研究室
6
Googleにおけるページランク
• 次の行列の固有ベクトルを求めて、要素の和が１に
なるように正規化する。
4
0.85 M 0.15 1
N 4
0.0375
0.8875
0.0375
0.0375
S学部
W大学
0.0375
0.0375
0.8875
0.0375
0.0375 0.320833
0.0375 0.320833
0.0375 0.320833
0.8875 0.0375
C学科
0.12649
0.23401
0.32540
0.31409
G研究室
7
より深く調べるために
• 本資料の例題は簡単にするために４つのサイトに閉じて
いた。
現実のPageRankは早稲田大学（8/10）、理工学部
（6/10）、CS学科（5/10）、後藤研（4/10）。
• 次の資料が参考になる
http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.html
本資料は上記を参考にした。ただしOctaveのスクリプトは若干改良した。
• Googleの創始者による論文も入手できる。
Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd,
'The PageRank Citation Ranking: Bringing Order to the Web', 1998,
http://www-db.stanford.edu/~backrub/pageranksub.ps
Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford
Technical Report, 1999,
http://dbpubs.stanford.edu:8090/pub/1999-31
8
特集：情報数学の演習問題
• 2005年度の定期試験問題の解答を解説します。
2006年度の諸君の勉強の参考にして下さい。
• 次の事実に注意してください。
2004年度の金曜日（前半）の担当は上田和紀教
授、2005年度から担当を交代して後藤滋樹です。
• 本日の授業では３題を解説します。残り２題は来
週以降に解説する予定。
9
問１．集合 A＝{ 2, 3, 4, 5 }, 集合 B={ 1, 3, 5, 7 }
とするとき、次の(1-1)～(1-6)の集合を外延的に表
現せよ。
(1 1)
A B
(1 2)
A B
(1 3)
A B
(1 4)
A B
(1 5)
A B
(1 6) 2 ( B )
B
• ヒント： 記号の意味を覚えておく必要がある
10
問１．解答
(1 1) A B 1, 2, 3, 4, 5, 7}
(1 2) A B 3, 5
2,1 , 2,3 , 2,5 , 2,7 , 3,1 , 3,3 , 3,5 , 3,7
(1 3) A B
4,1 , 4,3 , 4,5 , 4,7 , 5,1 , 5,3 , 5,5 , 5,7
(1 4) A B 0,2 , 0,3 , 0,4 , 0,5 , 1,1 , 1,3 , 1,5 , 1,7
(1 5)
A B 2, 4
(1 6) 2 ( B)
B
, 1, 3, 5, 7, 1,3, 1,5, 1,7, 3,5, 3,7, 5,7,
1,3,5, 1,3,7, 1,5,7, 3,5,7, 1,3,5,7
• ヒント： 各集合の要素の数を考えてみる
11
問２．自然数の集合 N は無限集合である。このと
き集合 N 2 が可算無限集合 (enumerable set,
countable set) であることを示せ。
• ヒント： N 2 という表記法を誤解しないように
12
問2．解答
N N N は自然数の集合の直積である。
2
N N の要素<x,y>に自然数 {( x y) 3x y} 2
を対応づける関数は全単射である。よって N と
2
N N N とは対等で同じ濃度をもつ。
集合 N が可算無限集合であるから N 2 も可算
無限集合である。
2
13
問３．次の(3-1)～(3-3)で定義する各々の二項関
係は、（a）反対称律、（r）反射律、（s）対称律、
（t）推移律のどれを満たすか？
(3-1)～(3-3)の各々について、満たす性質すべて
を記号（a, r, s, t）で答えよ。
14
問３．
(3-1) A は2次元平面上のすべての点の集合で、
関係 R は「点 x は点 y よりも原点より遠くない」
と定義される。
(3-2) A は2次元平面上のすべての直線の集合
で、関係 R は「直線 x と直線 y が平行である」
と定義される。
(3-3) 有限集合 A={0, 1, 2, 3, 4} の上でRは
R={<0,0>,<1,1,>,<2,2>,<3,3>,<4,4>}という
グラフで定義される。
15
問3．解答
(3-1) r, t
(3-2) r, s, t
(3-3) a, r, s, t
16
レポートの提出方法
(2006年度 後藤担当）
• レポート用紙を下記のURLからプリントする
http://www.goto.info.waseda.ac.jp/~goto/infomath.html
１班 (奇数班), と２班 (偶数班) で用紙が異なる
• 提出場所は、60号館2階の
CS学科事務所前のBOX
BOX番号は掲示による
• 締切厳守のこと
提出期間は、2006年5月22日(月)～26日(金)の間
17
問１ 集合の要素
• 次の集合に属するすべての要素を列挙せよ。
例： {0,1}{a} 0, a , 1, a
[1-1]
2
2{}
(または
P
(P
(f
g )) )
{a, {a}, {a, {a}}} {a, {a}}
[1-2]
ヒント： [1-2]では＋の左と右の集合の要素の数を、まず数えてみる。
これは有限集合である。
18
問2 関数
• 次の集合に属する要素を具体的に一つ挙げよ。
N{0,1}×{2,3｝
ヒント： まず集合 {0, 1}×{2, 3} の要素を具体的に書いてみる。
19
問３ 集合の濃度（可算集合）
• 自然数の集合 N={0,1,2,…}の直積 N2=N×N
から N への関数 f(x,y)={(x+y)2+3x+y}÷2 を考
える。
(3-1) f(0,0), f(0,1), f(1,0) ,f(0,2), f(1,1), f(2,0)
の値を計算せよ。
(3-2) N2は可算集合であることを説明せよ。
20
問４ 二項関係の反射推移的閉包
• 集合A = {p, q, r, s} 上の二項関係
R = {<p, q>, <q, r>, <r, s>, <r,r>} の
反射推移閉包（すなわち R * ）を求めよ．
ヒント
p
s
R0
R1
R2
R3
R4
p
p
q
r
r,s
r,s
q
q
r
r,s
r,s
r,s
r
r
r,s
r,s
r,s
r,s
s
s
q
r
21
© Copyright 2024 ExpyDoc
