[정보검색] 10. Web Search & Link Analysis

 

11/19

원본 19, 21장

 

Ads(Advertise)

Goto(1996)

클릭하면 그 댓가 지불.

돈을 많이 낸 페이지를 위로.

문제는 성능(관련성)

 

Two ranked lists

왼쪽엔 검색결과, 오른쪽엔 광고.

 

광고도 rank하면?

-클릭 수가 많은 순서로?

-아니면 돈을 많이 낸 순서로?

 

처음은 bid price 순서로.

->관련성 문제.(관련 없는게 왜 뜸?)

대안: bid price와 관련성 2개로.

(CTR: clickthrough rate = clicks per impressions)

 

ad rank는 bid*CTR이 큰 순서대로

paid는 (다음 순번의 ad rank)/CTR 이고, 맨 아래는 1센트(변동 가능)

 

win-win-win

검색엔진은 돌릴 돈을 어느정도 받고

사용자는 필요한 검색을 하고, 어느정도 관련도 있는 광고를 클릭 가능하고

광고주는 어느정도는 클릭으로 이득을 얻을 수 있음.

 

 

Citation analysis

PageRank의 기원.

논문 등에서 참조문헌으로 많이 참조되었다면 좋은/중요한 문서일 경향이 있다.

inlink count: 참조해서 들어오는 것

중요한 문서에서 연결되었다면 중요성 가중.

 

PageRank

=long term visit rate = steady state probability

간단히 말해서 계속 돌아다니다가 일정 비율로 수렴한 그 값.

 

수식화-Markov chain 이용

state = page

N개의 state, N*N 크기의 전이 확률 행렬 P

바로 앞의 상황만 고려한다.

 

web graph는 ergodic*한 Markov chain에 해당.

dead ends를 포함하지 않아야함->없애기.

 

Dead end: random walk가 향하지만, 나오지 못함.

=>teleport 개념 사용

 

teleporting: dead end의 방지를 위해 아무 곳으로나 이동하는 확률(10%)을 부과한다.

 

Ergodic Markov chains

-irreducibility(역:환원불가능성): 어떤 페이지든 다른 페이지로의 경로 존재.

-aperiodicity(역:비주기성): random walk가 순차적이도록 분할할 수 없음.

steady-state

순회한 뒤에도 확률이 변하지 않음.

 

page rank의 계산

π = (p1, p2, p3... pN)은 pageRank vector

변하지 않으니까 π = π *P가 성립.(약간 e^x의 미분 같은.)

시작 상태 x에 대해 x*P^k를 하여 그 수렴하는게 π

(수렴할 때까지 P의 거듭제곱을 x에 곱하는 걸 power method라 한다.)