페이지랭크

지난 글 : [알고리즘/알고리즘 도감] - 소수 판별법

 

페이지랭크(PageRank)는 검색 사이트에서 검색 결과의 순위를 결정하기 위해 사용되는 알고리즘이다. 

 

1

페이지랭크는 페이지 간의 링크 구조로부터 페이지의 가치를 산출하는 알고리즘이다. 산출까지의 구체적인 과정을 보자.

          페이지
       /    |    \
   페이지  페이지  페이지

위 그림에서 세 개의 페이지가 하나의 페이지를 링크하고 있다. 페이지랭크에서는 링크된 수가 많을 수록 중요한 페이지라고 판단한다. 위 표에서는 상위에 있는 페이지가 가장 중요한 페이지라 판단한다. 실제로는 각 페이지의 중요도가 계산에 의해 수치화된다. 기본적인 계산 방법을 보자.

 

2

          페이지
       /    |    \
      1     1     1

링크되지 않은 페이지의 점수를 1이라 하자.

            3
       /    |    \
      1     1     1

링크돼 있는 페이지의 점수는 링크를 하고 있는 페이지의 점수를 합한 것이 된다.

         0.5     0.5
           \     /
              1

단, 링크가 여러 페이지로 나누어지는 경우 링크 점수를 균등하게 배분한다.

 

3

        페이지(4)
            |    \
        페이지(3)  페이지(1)
       /    |    \
 페이지(1)페이지(1)페이지(1)

페이지랭크에서는 링크를 모으고 있는 페이지로부터 링크되는 경우 큰 가치를 지닌다. 최상단에 있는 페이지는 점수가 3인 페이지가 링크하고 있어 큰 점수를 부여받는다. 

 

4

하지만 위 방법에서는 링크가 원형을 이루는 경우 문제가 발생한다.

          2  -  2
          |  \  |
          1    1

각 페이지의 점수를 순서대로 계산하다 보면 무한 루프가 돼 루프 내의 페이지 점수가 계속 증가하게 된다. 

 

5

루프 문제는 '랜덤 서퍼 모덴(Random Surfer Model)'이라는 계산 방법으로 해결할 수 있다. 인터넷 서핑을 하는 사용자가 페이지를 열람하는 흐름을 보자.

1. 우연히 본 TV에서 재미있는 사이트가 소개돼 접속하려 한다.
2. 왼쪽 아래의 페이지에서 출발해 링크를 따라 다른 페이지로 이동한다.
        2(도착)- 2
          |  \  |
        1(출발) 1
3. 몇 개의 페이지를 방문하다 흥미가 떨어져 일단 서핑을 중단한다.
4. 그리고 며칠 후 친구가 추천해준 다른 페이지를 통해 인터넷 서핑을 시작한다.
          2 - 2(도착)
          |  \  |
          1  1(출발)
5. 여기서도 링크를 따라 다른 페이지로 이동하다 재미가 없어지면 서핑을 중단한다. 이처럼 어떤 페이지에서 
	열람을 시작해 몇 페이지 이동한 후 종료하는 동작이 반복된다.
6. 인터넷 공간으로 시점을 옮겨 이 동작을 보면, 인터넷 서핑을 하고 있는 사람은 페이지들을 정해진 횟수 없이
	이동한 후 다른 페이지로 이동하기를 반복하는 것처럼 보인다.
7. 인터넷 서핑을 하는 사람의 동작을 정의하면 확률 1 - a로 지금 있는 페이지의 링크 중 하나를 선택한다.
	확률 a로 다른 페이지로 이동한다.
8. 이동하는 확률인 a를 여기서는 15%라 하자. 이 정의에 따라 페이지 간 전이를 시뮬레이션 한다.
          0  -  0
          |  \  |
          0     0
	각 페이지 상의 숫자는 인터넷 서핑을 한 사람이 페이지를 방문한 수다. 현재는 시뮬레이션 전이므로
    모든 숫자가 0이다.
9. 정의에 따라 시뮬레이션을 하면 페이지당 방문 횟수의 차가 나온다.
          0  -  0
          |  \  |
          1     0
             |
          2  -  1
          |  \  |
          1     0
             |
         332 - 320
          |  \  |
         38    310
         
         페이지의 방문 횟수가 합계 1,000에 도달할 때까지 시뮬레이션을 했더니 위 같은 결과가 됐다.
10. 이것을 비율로 바꾸면 아래처럼 된다.
         33% - 32%
          |  \  |
         4%    31%
         이 값은 '특정 시점에 해당 페이지를 열람할 확률'을 나타낸다 볼 수 있다. 이것을 그대로 페이지의
         점수로 사용하는 것이 랜덤 서퍼 모델이다.

 

6

마지막으로, 페이지랭크의 값이 처음 설명한 링크의 가중치 계산과 일치하는지 확인한다.

           3
        /  |  \
       1   1   1
   =================        
          0.5
        /  |  \
   0.17  0.17  0.17

각 값을 반올림하고 있어 모두 합하면 1이 되지 않지만, 앞서 본 것과 비슷한 비율이란 것을 알 수 있다. 앞서 본 또 다른 링크 구조에서도 점수를 계산해보자.

            4
            | \
            3  1
          / | \
         1  1  1
    ==================
           0.36
             |   \
          0.27    0.09
       /    |   \
     0.09  0.09  0.09

여기서도 앞의 비율과 비슷한 비율이 나온다.

 

참고 서적 :