Week5 Day2

📋 $PageRank$ $Algorithm$

📌 페이지 랭크의 배경

• 웹은 웹페이지와 하이퍼링크로 구성된 거대한 방향성있는 그래프
  
• 기존 검색엔진 에서는 웹을 거대한 디렉토리로 정리 시도
  -> 웹페이지 수가 증가하며 카테고리 수와 깊이 무한정 커지고, 카테고리 구분이 모호해져 어려움
• 이어서 키워드에 의존한 검색엔진
  -> 악의적인 웹페이지에 취약한 문제

📌 페이지 랭크의 정의

• 페이지 랭크는 투표를 통해서 키워드와 관련성이 높고, 신뢰할 수 있는 웹페이지 찾는다.
• 들어오는 간선 수 만으로는 약용의 소지가 여전히 존재하므로
  신뢰성이 높은 사이트에 가중 투표를 할 수 있는 방식
  
• 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식의 임의 보행$(Random$ $Walk)$ 과정에서도 정의가 가능하다.

📌 페이지 랭크의 계산

• 페이지 랭크 점수 계산은 반복곱을 사용한다.
  
• 하지만 이는 항상 수렴하지 않는다
  -> 들어오는 간선은 있지만 나가는 간선 없는 정점 집합/정점
• 문제 해결위해 순간이동$(Teleport)$도입
  
• 순간이동을 통해 다음과 같이 계산을 바꾼다