2001年度情報数学

Result of a Search
※キーワード検索の結果
Too many pages
※多数のページ
How to sort them?
※表示する順番は
Cope with SEO:
Search Engine
Optimization
※SEOに負けない
1
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
※単純に特定の単語の出現を数えるだけでは
水増しで対抗するだろう
※背景と同じ色の文字を使うと人間には文字
が見えない
2
Criteria ※判断基準
What is a good Web page?
G: A good page is a popular page, i.e. the
destination of many links.
※ 人気のあるページ、他のWebからの多くのリン
クの行先となっている。
3
You have n ballots
※ 最初に n 票あるとします
n
Four outgoing links
(1/4)n=0.25n
Deliver 0.25n for each link
４本の行き先に
等分に配ります
4
A simple example with one ballot
※ 簡単な例題（１票と表示する）
１
１
S school
C dept
１
1/3
W univ.
1/3
1/3
G lab
W=(1/3)G
S=W+(1/3)G
C=S+(1/3)G
G=C
W=(1/9), S=(2/9), C=(1/3), G=(1/3)
5
Page Rank by Google
• Adjacent Matrix (Tansient)
※ 隣接行列（推移行列、遷移行列）
• Eigen value and vector
※ 固有値と固有ベクトル
W
W 0

S 0
C 0

G  1
S C G
1 0 0

0 1 0
0 0 1

1 1 0 
1 there is an edge from vertex i to vertex j
aij  
０ there is no edge from vertex i to vertex j
S school
W univ.
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は注釈
であり行列に含まれない
6
Transposed adjacent matrix
• Transpose the adjacent matrix
※ 隣接行列 A  (aij ) を転置する
• W receives a link from G.
※ リンクを「出す」側から「受ける」側へ
School
Department
S学部
C学科
A 
t
W大学
G研究室
University
Laboratory
0

1
0

0

0
0
1
0
A
0
0
0
1
t
1

1
1

0 
7
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.
※ ページの評価値をリンク先に渡す  0
１
１
S学部
1/3
W大学
1/3
C学科
1/3
１
G研究室
M 
0 0

1 0 0

0 1 0

0 0 1
1 
3
1 
3
1 
3
0 
8
Transition probability matrix and vector
※ 推移確率行列とベクトル
• Multiply the matrix M and a vector is make a
transient from one node to the other node.
※ 行列 M を掛ける（乗算）ということは、グラフの
辺に沿って（確率的に）推移するということである
v'  M  v
 1/3g
  0


 w  1/3g   1
 s  1/3g   

 0
c
 

 0
0 0
0 0
1 0
0 1
1   w
3  
1  s 
3  
1  c
3   
0  g
9
Eigen value and Eigen vector
※ 固有値と固有ベクトル
• Eigen value λ and Eigen vector r
M r  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.
※ 固有ベクトルの各要素がランクになる
（ただし要素の和が１となるように正規化する）
10
Example: eigen vector
※ 固有ベクトルの具体例
• GNU Octaveを使って計算する。固有値λ＝１が最大
の固有値であり、固有ベクトルは下の左のようになる。
 0.20851


 0.41703
 0.62554


 0.62554


Eigen vector
Page rank
 0.11111


 0.22222
 0.33333


 0.33333


• これを正規化したページランクは上の右である。
2/9
１
S
１
School
1/3
1/9
W Univ.
1/3
C
dept. 1/3
1/3
G
１
Page rank
ページランクを記入した図
laboratory 1/3
11
Another idea by Google
※ Googleにおける工夫
Eigen vector of a large
sparse matrix
※ サイズの大きな
疎(sparse)行列の
固有ベクトルの計算
Radom walk by a user
※ ユーザがランダムに
ページを渡り歩くと仮定
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
School
Department
S学部
C学科
W大学
University
G研究室
Laboratory
12
Actual calculation by Google
※ Googleにおけるページランク
• Calculate the eigen vector of the following matrix
and normalize the elements.
 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研究室
13
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
14
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.
※ ある説によると広告業界の経済規模はＧ
ＤＰの一定の割合を占めており不変である
15
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)
※ 判断基準：単純なＳＥＯに負けない、手作業が介
在せずに自動的に行われる、オリジナリティ。
16

Download Report