[CS224W] 4.2 How to Solve PageRank

How to Solve PageRank

간단하게 R에 random한 값을 부여 후, 값이 수렴할 때 까지 iteration을 반복

• 새로운 R로 갱신 후, 반복 (Power Iteration)
  

• L1 Norm을 사용

• 일반적으로 50번의 계산이 요구됨

• 구글은 매일 PageRank를 계산

• 요런 과정

두 가지 문제

Dead Ends

• out link가 없음
• 들어오면 종료 (leaks out)
• Teleport로 해결
  leaks 되면 무작위 Node로 teleport (1/# node)의 확률

Spider traps

• absorbing space
• 계속 같은 space를 반복
• Random Jump로 해결
  무작위로 teleport하는 확률 (1 - 베타)를 설정해 탈출하게 함
  보통 베타는 0.8,0.9

Why Teleports solve problem

• Spider Trap은 수학적으로는 문제가 없지만 알고리즘적으로 원하는 결과가 아님
• Dead-ends는 수학적으로 문제가 맞음
  열확률인접행렬에 확률을 추가하는 방법으로 해결하는 것

• 최종적으로 다음과 같은 공식
  
• 다음과 같은 행렬