PageRank 개요 및 응용

• PageRank
  • Google 검색엔진의 기반 알고리즘
  • 하이퍼링크를 이용한 웹 페이지 중요도 측정
    • 하이퍼링크 네트워크: Web을 directed graph로 보기
• PageRank의 응용
  • 모든 그래프에서, 노드의 중요도 측정에 사용
    • 웹 페이지의 중요도 측정
    • 친구관계 네트워크에서 핵심 인물 탐색 등…
• 핵심 아이디어: 링크 정보를 이용해 페이지에 순위(점수)를 매기자
  • 많은 링크를 받는 페이지 → 높은 점수
  • 높은 점수의 페이지로부터 링크를 받으면 → 높은 점수
• Random Walk Interpretation
  • pagerank = 간선을 따라 그래프를 떠돌아다니는 행인이 각 정점에 머무를 확률
  • 웹을 서핑하는 과정과 유사

PageRank 심플버전

• 내 점수를 골고루 이웃에게 나눠주기
• PageRank score = 받은 점수의 합
• Power Iteration
  • 행렬의 주고유벡터 계산 방법
  • 모든 정점의 점수를 1/n으로 초기화
  • 정점마다 새로운 점수를 계산
    • 받은 점수의 합
  • 수렴할 때까지 반복

PageRank 오리지널

심플버전의 문제점

• 수렴하는가? → X
• 결과가 그럴듯한가? → X (daed end, spider trap)

Random Teleport

• 매 스텝마다, 특정 확률로 아무 노드로 순간이동
  • 수렴 문제 해결? → 해결
  • Spider trap 해결? → 언젠가 빠져나옴
  • Dead End 해결? → 무조건 순간이동