brunch

라이킷 5 댓글

You can make anything
by writing

C.S.Lewis

계정을 잊어버리셨나요?

by 디이프 Jan 30. 2023

[데이터과학] PageRank 알고리즘

Editor's Note

여러분은 궁금한 게 있거나 리서치를 해야 할 때 어떤 검색 엔진을 사용하시나요?

보통 일반적으로 구글이나 네이버를 사용하게 되는데요,

구글 검색창에 궁금한 키워드나 내용을 입력하면 관련 내용을 포함한 페이지들이 리스트 형식으로 나열됩니다. 그리고 보통 첫 번째 페이지의 상단에 있는 페이지 3~4개를 클릭하게 되죠. 상단에 있는 페이지가 그만큼 관련성이 높거나 검색한 키워드를 많이 포함하고 있기 때문인데요.

오늘은 구글이 이 페이지들의 순서를 정하는 알고리즘을 알아보도록 하겠습니다.

우리는 구글에서 관심 키워드 입력 시, 관련 페이지들이 순서대로 나열되어 보여주는 것을 확인할 수 있습니다. 여기서 구글은 어떤 방식으로 관련된 페이지들의 순서를 정할까요?

이에 대한 대답은 구글 창립자인 Sergey Brin의 1998년 논문 “The Anatomy of a Large-Scale Hypertextual Web Search Engine”에서 소개하고 있습니다.

월드 와이드 웹과 같은 하이퍼링크 구조를 가지는 문서에 상대적 중요도에 따라 page에 rank값을 부여하여 높은 rank의 웹 페이지를 우선으로 보여주는 방식으로 검색됩니다.

구체적으로 PageRank 알고리즘이 동작하는 방식은 다음과 같습니다.

A, B, C, D 페이지 간의 아래의 그림과 같이 하이퍼링크를 가진다고 했을 때, A 페이지의 PageRank(PR) 값은 A 페이지를 인용하고 있는 다른 페이지가 가진 페이지 순위를 정규화시킨 값의 합으로 구할 수 있습니다. 다시 말하면 A의 PR 값은 A 페이지를 가리키고 있는 다른 페이지의 순위 값이 높으면 A의 PR 값은 높아지게 됩니다.

그림 1 웹페이지 하이퍼링크 예시

PR 구하는 수식은 다음과 같습니다.

PR : PageRank 함수

d : damping factor

N : 전체 페이지 수

L(Pj) : Pj의 outlink 수

PR(A)를 구해보면, 우선 A 페이지의 초기 PR 값이 필요합니다. A 페이지의 초기 PR 값은 1/(전체 페이지 개수 or 노드의 수) 구할 수 있으며, B-D의 초기 PR 값 또한 동일하게 구할 수 있습니다. 즉, 초기 PR 값은 모든 페이지가 같은 값을 가지게 됩니다.

PR(A) = 1/4

PR(B) = 1/4

PR(C) = 1/4

PR(D) = 1/4

위 수식에서 damping factor는 “웹 서핑을 하는 사람이 현재 페이지에서 다른 페이지로 이동할 확률”을 의미합니다. 논문에서는 damping factor를 0.85로 설정 하였다고 합니다. 동일하게 적용하여 A 페이지의 rank 값을 적용하면 다음과 같이 구해집니다.

그림 2 A 페이지의 하이퍼링크

PR(A) = (1-DF)/(전체 페이지 수 or 전체 노드 수) + DF * ((A로 향하는 페이지의 현재 Pr값/ A로 향하는 페이지의 out link 개수) 들의 합)

Pr(A) = (1-DF)/4 + DF * (Pr(C)/3)

Pr(A) = (1-0.85)/4 + 0.85*(0.25/3) = 0.10833333

B 페이지의 rank 값 또한 A와 같은 방식으로 rank 값을 구할 수 있습니다. B 페이지의 경우는 B로 향하는 페이지가 A, C 두 개이므로 아래와 같이 계산되어 rank 값이 구해집니다.

Pr(B) = (1-DF)/(전체 페이지 수 or 전체 노드 수) + DF * ((B로 향하는 페이지의 현재 Pr값/ B로 향하는 페이지의 out link 개수) 들의 합)

Pr(B) = (1-DF)/4 + DF * (Pr(A)/2 + Pr(C)/3)

Pr(B) = (1-0.85)/4 + 0.85*(0.25/2 + 0.25/3) = 0.214583333

PR은 이와 같은 방법을 통해 페이지 간 rank 값을 주고받는 것을 반복하다 보면, 전체 웹 페이지가 특정한 페이지 rank 값을 수렴한다는 사실을 통해 각 페이지의 최종 PR을 계산합니다. 이 과정에서 구글 행렬(Google Matrix)을 통해 PageRank를 구할 수 있습니다. 수식은 아래와 같습니다.

M : Adjacency Matrix

1/N : Random Teleport Matrix