Result of a Search ※キーワード検索の結果 Too many pages ※多数のページ How to sort them? ※表示する順番は Cope with SEO: Search Engine Optimization ※SEOに負けない

Simple counting does not work If you count the number of occurrences of a specific term: xyz, they simply repeat it. If the background color is the same as the font color, we do not notice them. ※単純に特定の単語の出現を数えるだけでは 　 水増しで対抗するだろう ※背景と同じ色の文字を使うと人間には文字 　 が見えない xyz xyz xyz xyz xyz xyz xyz xyz xyz xyz xyz

Criteria ※判断基準 What is a good Web page? G: A good page is a popular page, i.e. the destination of many links. ※ 人気のあるページ、他のWebからの多くのリンクの行先となっている。

You have n ballots ※ 最初に n 票あるとします Four outgoing links (1/4)n=0.25n Deliver 0.25n for each link ４本の行き先に 等分に配ります n

A simple example with one ballot ※ 簡単な例題（１票と表示する） W=(1/3)G S=W+(1/3)G C=S+(1/3)G G=C W univ. S school C dept G lab １ 1/3 W=(1/9), S=(2/9), C=(1/3), G=(1/3)

Page Rank by Google Adjacent Matrix (Tansient) ※ 隣接行列（推移行列、遷移行列） Eigen value and vector ※　固有値と固有ベクトル W univ. S school C dept G lab Characters W, S, C, G around the matrix are comments. They are not included in the matrix. ※ 行列の上と左のW, S, C, Gは注釈 であり行列に含まれない

Transposed adjacent matrix Transpose the adjacent matrix ※ 隣接行列　　　　　　　を転置する W receives a link from G. ※ リンクを「出す」側から「受ける」側へ School Department W大学 S学部 C学科 G研究室 University Laboratory

From Adjacent matrix to Transition probability matrix ※ 隣接行列から推移確率行列へ The sum of elements in one column is 1 or 0. ※ 列(column)の総和が１または０になるように調整 The evaluation value is handed to the next page. ※ ページの評価値をリンク先に渡す W大学 S学部 C学科 G研究室 １ 1/3

Transition probability matrix and vector ※ 推移確率行列とベクトル Multiply the matrix M and a vector is make a transient from one node to the other node. ※ 行列 M を掛ける（乗算）ということは、グラフの 辺に沿って（確率的に）推移するということである

Eigen value and Eigen vector ※ 固有値と固有ベクトル Eigen value λ and Eigen vector r ※　固有値 λ と固有ベクトル ｒ Each element in the eigen vector is multiplied by a constant when multiplied by the matrix M. ※ 固有ベクトルの各要素は M を掛けても定数倍 しか変化しない。（安定している） The elements are used as the page rank after normalization: the sum of the elements is one. ※ 固有ベクトルの各要素がランクになる （ただし要素の和が１となるように正規化する）

Example: eigen vector ※ 固有ベクトルの具体例 GNU　Octaveを使って計算する。固有値λ＝１が最大の固有値であり、固有ベクトルは下の左のようになる。 Eigen vector Page rank これを正規化したページランクは上の右である。 W Univ. S School C dept. G laboratory １ 1/3 2/9 Page rank ページランクを記入した図 1/9

Another idea by Google ※ Googleにおける工夫 Eigen vector of a large sparse matrix ※ サイズの大きな 疎(sparse)行列の 固有ベクトルの計算 Radom walk by a user ※ ユーザがランダムにページを渡り歩くと仮定 School Department W大学 S学部 C学科 G研究室 University Laboratory

Actual calculation by Google ※ Googleにおけるページランク Calculate the eigen vector of the following matrix and normalize the elements. W大学 S学部 C学科 G研究室

For futher reading ※ より深く調べるために This slide assumes only four sites. The real PageRanks are Univ.(8/10）、School (6/10）、Dept. CS（5/10）、Goto Lab（4/10） when this slides first written. http://homepage2.nifty.com/baba_hajime/wais/pagerank.html　 (New, long) http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.html (Old, short) This slide is based on the modified calculation of the eigen vector by Octave. Google founders wrote the paper. 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

How Google earns money? The search results are shown with some advertisements. ※　検索連動型広告 The idea was brought by Overture. ※　オーバチュア The market size of the advertisements is fixed to some percentage of GDP. ※　ある説によると広告業界の経済規模はＧＤＰの一定の割合を占めており不変である

The best ordering algorithm Q: Please propose the best ordering algorithm when you have a huge number of “search” results. ※ 検索結果が膨大に存在するときに、もっとも良い並べ方のアルゴリズムを提案せよ。 Criteria: cope with simple SEO technique, automatic, original idea(s) ※ 判断基準：単純なＳＥＯに負けない、手作業が介在せずに自動的に行われる、オリジナリティ。