Day 22. 페이지랭크 & 전파모델

1. 페이지랭크 계산법 - 반복곱(power iteration)

• 1. 각 웹페이지 i의 페이지랭크 점수 초기값 r을 동일하게 1/웹페이지수(노드수)로 초기화함
• 2. 아래 식을 이용하여 각 웹페이지의 페이지랭크 점수를 갱신함

• 3. 페이지랭크 점수가 수렴하면 종료, 아니면 2.로 돌아감
  • 수렴 확인: r(t) - r(t+1)가 하이퍼파라미터인 에러 e 값보다 작으면 수렴

 

 

2. 순간이동(Teleport)

• 기존 페이지랭크의 한계를 극복하기 위해 → 순간이동을 통해 스파이더 트랩(간선이 엄청 많이 늘어나는)이나, 막다른 정점에 갇히는 일 없어짐
• 임의 보행(random walk) 관점에서 웹을 서핑하는 웹서퍼의 행동을 다음과 같이 수정함
  • 현재 웹페이지에 하이퍼링크가 없다면, 임의로 웹페이지로 순간이동을 함
  • 현재 웹페이지에 하이퍼링크가 있다면, 앞면이 나올 확률이 a인 동전을 던짐
  • 앞면이라면, 하이퍼링크중 하나를 균일한 확률로 선택해 클릭함
  • 뒷면이라면, 임의의 웹페이지로 순간이동 함
• a를 감폭 비율(damping factor)라고 부르며 보통 0.8 정도를 사용함
• 순간이동을 도입한 페이지랭크
  • 1. 각 막다른 정점에서 (자신 포함) 모든 다른 정점으로 가는 간선을 추가함
  • 2. 아래 수식을 이용해 반복곱을 수행함
    • 파란색 부분: 하이퍼링크를 따라 정점에 도착할 확률
    • 빨간색 부분: 순간이동을 통해 정점에 도착할 확률