Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学 基本的な仕組は数学的 グラフの行列による表現 　隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学 S学部 C学科 G研究室 WEBページのリンクの関係 行列の上と左のW, S, C, Gは注釈 であり行列に含まれない

隣接行列を転置する 隣接行列　　　　　　　を転置する リンクを「出す」側から「受ける」側へ W大学 S学部 C学科 G研究室 WEBページのリンクの関係

隣接行列から推移確率行列へ 列(column)の総和が１または０になるように調整 ページの評価値をリンク先に渡す W大学 S学部 C学科 G研究室 WEBページのリンクの関係 １ 1/3

推移確率行列の固有値と固有ベクトル 固有値λと固有ベクトルｒ 行列 M を掛ける（乗算）ということは、グラフの 辺に沿って（確率的に）推移するということである 固有ベクトルの各要素は M を掛けても定数倍 しか変化しない。（安定している） 固有ベクトルの各要素がランクになる （ただし要素の和が１となるように正規化する）

固有ベクトルの具体例 GNU Octaveを使って計算する。固有値λ＝１が最大の固有値であり、固有ベクトルは下の左のようになる。 これを正規化したページランクは上の右である。 W大学 S学部 C学科 G研究室 １ 1/3 2/9 ページランクを記入した図 1/9

Googleにおける工夫 サイズの大きな 疎(sparse)行列の 固有ベクトルの計算 ユーザがランダムにページを渡り歩くと仮定 W大学 C学科 G研究室

Googleにおけるページランク 次の行列の固有ベクトルを求めて、要素の和が１になるように正規化する。 W大学 S学部 C学科 G研究室

より深く調べるために 本資料の例題は簡単にするために４つのサイトに閉じていた。 現実の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

特集：情報数学の演習問題 2005年度の定期試験問題の解答を解説します。 2006年度の諸君の勉強の参考にして下さい。 次の事実に注意してください。 2004年度の金曜日（前半）の担当は上田和紀教授、2005年度から担当を交代して後藤滋樹です。 本日の授業では３題を解説します。残り２題は来週以降に解説する予定。

問１．集合 A＝{ 2, 3, 4, 5 }, 集合 B={ 1, 3, 5, 7 }とするとき、次の(1-1)～(1-6)の集合を外延的に表現せよ。 ヒント：　記号の意味を覚えておく必要がある

問１．解答 ヒント：　各集合の要素の数を考えてみる

問２．自然数の集合 N は無限集合である。このとき集合 N 2 が可算無限集合 (enumerable set, countable set) であることを示せ。

問2．解答 　　　　　　　　は自然数の集合の直積である。 　　　　　の要素<x,y>に自然数 を対応づける関数は全単射である。よって　　と 　　　　　　　　　とは対等で同じ濃度をもつ。 集合　　が可算無限集合であるから　　　も可算 無限集合である。

問３．次の(3-1)～(3-3)で定義する各々の二項関係は、（a）反対称律、（r）反射律、（s）対称律、 （t）推移律のどれを満たすか？ (3-1)～(3-3)の各々について、満たす性質すべてを記号（a, r, s, t）で答えよ。

問３． (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>}というグラフで定義される。

問3．解答 (3-1) r, t (3-2) r, s, t (3-3) a, r, s, t

レポートの提出方法 (2006年度 後藤担当） レポート用紙を下記のURLからプリントする レポートの提出方法 (2006年度 後藤担当） レポート用紙を下記のURLからプリントする http://www.goto.info.waseda.ac.jp/~goto/infomath.html １班 (奇数班), と２班 (偶数班) で用紙が異なる 提出場所は、60号館2階の CS学科事務所前のBOX BOX番号は掲示による 締切厳守のこと 提出期間は、2006年5月22日(月)～26日(金)の間

問１ 集合の要素 次の集合に属するすべての要素を列挙せよ。 例： [1-1] (または P (P (f g )) ) [1-2] 問１　集合の要素 次の集合に属するすべての要素を列挙せよ。 例： [1-1] (または　 P (P (f g )) 　) [1-2] ヒント：　[1-2]では＋の左と右の集合の要素の数を、まず数えてみる。 　　　　　これは有限集合である。

問2 関数 次の集合に属する要素を具体的に一つ挙げよ。 N{0,1}×{2,3｝ 問2　関数 次の集合に属する要素を具体的に一つ挙げよ。 　　N{0,1}×{2,3｝ ヒント：　まず集合 {0, 1}×{2, 3}　の要素を具体的に書いてみる。

問３　集合の濃度（可算集合） 自然数の集合 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は可算集合であることを説明せよ。

問４　二項関係の反射推移的閉包 集合A = {p, q, r, s} 上の二項関係 R = {<p, q>, <q, r>, <r, s>, <r,r>} の 反射推移閉包（すなわち R * ）を求めよ． ヒント p q r s R0 R1 R2 R3 R4 p q r r,s s