[Algorithm] PageRank 란?

개요

• PageRank 개요
  • PageRank 란?
  • 하이퍼링크 네트워크란?
  • PageRank 의 응용
  • PageRank 의 핵심 아이디어
  • Random Walk Interpretation
• PageRank 심플버전
  • PageRank 심플버전 설명
  • Power Iteration
• PageRank 오리지널
  • PageRank Score 심플 버전의 문제점
  • Random Teleport
  • PageRank 오리지널 버전 설명

PageRank 란?

• Google 검색 엔진의 기반 알고리즘이다.
• 하이퍼링크를 이용해 웹 페이지 중요도를 측정한다.

하이퍼링크 네트워크란?

• Web 을 Directed graph 로 보는 형태이다.
  • Node : 웹페이지
  • Edge : 하이퍼링크

PageRank 의 응용

• 모든 그래프에서, 노드의 중요도 측정에 사용한다.
  • 예시)
    • 웹 페이지의 중요도 측정
    • 친구관계 네트워크에서 핵심 인물 탐색
    • 생물학 그래프에서 중요한 단백질 조사
    • 컴퓨터 네트워크 통신 로그에서 DDos 공격 탐지

PageRank 의 핵심 아이디어

• 핵심 아이디어 : 링크 정보를 이용하여 노드(페이지)마다 점수(순위)를 매기자
  • 그렇다면 어떤 노드에 높은 점수를 줄 것인가?
    • 1) 많은 링크를 받는 페이지 → 높은 점수
    • 2) 높은 점수의 페이지로부터 링크를 받으면 → 높은 점수

Random Walk Interpretation

• PageRank : 간선(링크)을 따라 그래프를 떠돌아다니는 행인이 각 정점에 머무를 확률
  • 행인은 간선(링크)를 계속 떠돌며,
  • 행인이 멈췄을 때, 그 행인이 a, b, c, d 에 있을 확률이 각각 pagerank 점수가 된다.
  • 웹을 서핑하는 과정과 유사하다.

PageRank Score 심플 버전

• 순서

  

  • 1) 각각의 노드(a, b, c, d)는 점수(ra, rb, rc, rd)를 가지고 있다.
  • 2) 각각의 노드는, 본인의 점수를 이웃에게 골고루 나눠준다.
  • 3) 이 때, 각 노드가 받은 점수의 합이 PageRank score 이다.
  • 4) 각 노드가 받은 점수의 합은 노드가 적을 경우엔 연립방정식을 통해서 구할 수 있지만, 보통 노드가 많으므로 행렬 곱셈을 통해 구할 수 있다.
    • 연립방정식으로 4가지의 미지수를 추측할 땐, ra + rb + rc + rd = 1 이라는 조건을 추가로 달아준다. (식은 미지수 개수보다 많아야한다.)

• 행렬 곱셈을 통한 PageRank score 계산 방법은 아래 그림과 같다.

  

  • 1) PageRank 를 행렬과 벡터로 표현한다.
    • 왼쪽 행렬에서 행은 도착점, 열은 시작점을 의미한다.
      • (a,b) = 1/2 라는 것은 a 가 b 에게 링크 될 확률이 1/2 라는 것이다.
    • 오른쪽 행렬은 각 노드가 초기에 가지고 있던 점수를 의미한다.
  • 2) 행렬 곱셈을 통해 각 노드의 PageRank score 를 계산한다.

Power Iteration

• 행렬 곱셈을 통해, PageRank 의 미지수를 구할 때,

• 그래프가 작은 사이즈라면 가우스 소거법 등을 사용해 구할 수 있지만,

• 그래프의 사이즈가 크다면 무리가 있다.

• 따라서, 큰 그래프에서 미지수를 대략적으로 구할 땐, Power Iteration 을 사용한다.

• 순서

  

  

  • 1) 처음에 모든 노드의 점수(ra, rb, rc, rd) 를 1/n 로 초기화한다.
    • 여기서 n은 모든 노드의 개수이다.
  • 2) 행렬 곱셈을 통해, 모든 노드의 새로운 점수를 계산한다.
  • 3) 노드 별 점수 결과를 우측 행렬로 다시 삽입한다.
  • 4) 노드의 점수가 수렴할 때 까지, 2)부터 반복한다.

• Power Iteration의 수학적 과정

  • Power Iteration : 행렬이 주어지면, 해당 행렬의 주고유벡터를 계산하는 방법이다.
    • 주고유벡터(Principal Eigen Vector)
      • M * v = λ * v
      • M(행렬) * v(벡터) 값이, 어떤 λ(상수값) * v(벡터)와 같다면
      • 이때의 v(벡터)를 Eigen Vector 라고 하며, λ(상수값)을 Eigen Value 라고 한다.
      • 이 조건을 만족하는 Eigen Vector 와 Eigen Value 는 여러가지가 나온다.
      • 그 중에서 Eigen Value 를 가장 크게하는 Eigen Vector 가 Principal Eigen Vector이다.
  • 따라서 Power Iteration 을 사용한 PageRank 는,
  • M * v = λ * v 에서 λ가 1일 때, Principal Eigen Vector 를 구하는 것과 동일하다.

PageRank Score 심플 버전의 문제점

• 수렴하는가?

  

  • a 와 b 가 서로 참조한다면 PageRank score 가 수렴하지 않는 경우가 발생한다.

• 결과가 그럴듯한가?

  

  • b 가 더 이상 링크되는 곳이 없다거나, 계속 본인에게 링크된다면
  • PageRank score 값이 사라지거나, 동일한 값을 계속 뽑아낸다.

Random Teleport

• 매 스텝마다, 특정 확률(β)로 아무 노드로 순간이동한다.
  • 수렴 하지 않는 문제, Spider Trap, Dead End 해결

PageRank Score 오리지널 버전

• PageRank score 심플 버전은, 이웃 노드로부터 들어오는 점수를 받아서 합산하는게 끝이였다.

• 하지만, PageRank Score 오리지널 버전에선, Random Teleport 를 통해, 이웃노드 뿐만 아니라 랜덤한 확률로 다른 노드의 점수 또한 받는다.

• 바뀐 PageRank Score 계산 수식

  • β이웃에게 받은 점수 + (1-β)랜덤으로 받는 점수

• 하지만, 해당 수식은 Power Iteration 에서 Principal Eigen Vector 를 구할 수 있는 포멧이 아니다.

• 따라서, 해당 수식 전체를 A * r = 1 * r 를 만족하는 A 행렬로 만들어준다.

• 이때, A 행렬을 The Google Matrix 라고 한다.

  

• β 를 0.8 로 사용했을 때, 아래와 같은 예제가 가능하다.

  

  • 0.8 * Adjacency List Matrix + 0.2 * Random Teleport Matrix

• 해당 방법을 사용하면, PageRank Score 오리지널 버전에서도, r = A * r 을 통해 Power Iteration 을 사용할 수 있게 된다.