[Stanford/CS224W] 4. PageRank(1) : 페이지 랭크

스탠포드 강의를 듣고 정리한 내용입니다.

 

지난 포스팅에서는 전체 그래프 임베딩에 대해서 알아봤습니다.

이번 포스팅에서는 구글의 아주 유명한 알고리즘인 페이지랭크에 대해서 배워보겠습니다. 

 

PageRank

페이지 랭크 알고리즘은 구글의 랭킹 알고리즘으로도 유명하죠. 

그런데 그래프 이야기를 하다가 왜 갑자기 페이지 랭크 알고리즘이 나왔을까요?

페이지 랭크는 말 그대로 페이지 간의 랭크를 구하는 것인데 말이죠. 

 

그렇다면 그림을 하나 보여드리도록 하겠습니다.

왼쪽은 우리가 지금까지 공부한 그래프이고, 오른쪽은 페이지와 그들간의 링크(하이퍼링크)를 연결한 것입니다. 

그래프와 굉장히 유사하죠? 

 

따라서 그래프와 웹은 비슷한 형태를 가진다고 할 수 있습니다. 

그래프의 노드는 페이지로, 링크는 하이퍼링크로 연결될 수 있습니다. 

 

※ 하이퍼링크가 왜 그래프의 링크가 되나요?

이 페이지를 읽으시는 분들도 하나의 '페이지'에 접속해 있다고 할 수 있습니다. 

자 그럼 제 글의 맨 위를 보시죠! "스탠포드 강의를 듣고  정리한 내용입니다."라는 글귀에 "스탠포드 강의"부분에 스탠포드 홈페이지로 가는 하이퍼 링크가 걸려있습니다.

따라서 지금 보시는 이페이지는 스탠포드 홈페이지에 연결되어있다라고 할 수 있습니다. 

 

페이지 랭크 알고리즘에서는 한 가지 더 생각해야할 것이 있는데요. 바로 페이지의 중요도입니다. 

100개의 페이지가 있는데, 이 100개의 페이지 모두 A라는 페이지의 링크를 가지고 있다고 하면, A라는 페이지는 중요한 페이지가 되겠죠?

그만큼 많이 참조를 하고 있다는 것이기 때문에, 당연히 중요도가 올라갑니다. 그리고! 또 한가지!

이 중요도가 높은 페이지가 참조하는 페이지가 있다면? 그 페이지 또한 중요한 페이지가 될것입니다. 

가치있는 페이지에서 참조하는 페이지는 당연히 가치가 있을 것이기 때문이죠. 

 

페이지 랭크와 비슷한 류의 알고리즘은 두 가지가 더 있는데요. 

• Personalized PageRank(PPR)
• Random Walk with Restars

먼저 페이지 랭크 알고리즘에 대해서 알아보고, 뒤에서 위의 두개 알고리즘을 살펴보도록 하겠습니다. 

 

정의

페이지 랭크는 앞에서도 말씀드린 것 처럼 '페이지의 중요성'을 고려한 알고리즘입니다. 

즉, 많은 페이지가 참조하는 페이지라면 그 페이지는 중요해진다는 뜻이죠. 

 

예를 들어 스탠포드 웹페이지는 23,400개의 페이지에서 언급되고있고, A라는 사이트는 1개의 사이트에서 언급되고 있다면, 당연히 스탠포드 웹페이지가 더 중요할 것입니다. 

 

그리고 중요한 또 한가지 개념은 각 페이지마다 중요도가 다르기 때문에, 각 페이지로부터 받는 가중치도 다릅니다. 

이 부분은 페이지 랭크 알고리즘이 실행되는 과정을 직접 보면서 이해해보도록 하죠!

 

자 위와 같이 그래프가 있습니다. 그래프에 뭐가 많이 적혀있죠? 

i, k, j는 각각 노드의 이름이라고 하고, r이 붙은 것은 노드의 '중요도'입니다. 

 

그럼 j의 중요도는 어떻게 계산될까요?

계산은 정말정말 쉽습니다! 

j에게 들어오는 노드를 보면, i, k 가 있죠. i노드는 총 3개의 페이지를 가지고 있고, k는 총 4개의 페이지를 가지고 있습니다. 

본인이 가진 중요도를 본인이 언급한 페이지 수로 나눠줍니다.

 

따라서 i, k는 다른 페이지에게 영향을 줄 수 있는 수치가 각각 r_i/3과 r_k/4입니다.

 

j는 i, k로부터 받은 중요도를 합산하여 j의 중요도로 갱신합니다. 

 

마찬가지로 j는 본인이 언급한 페이지들이 총 3개이기 때문에 r_j/3의 중요도를 나눠줄 수 있습니다.

 

이를 수식으로 일반화 하면 아래와 같습니다. 

지금까지의 강의는 대부분 직관적으로 표현했습니다. 

이번에는 행렬을 이용하여 수식을 보겠습니다.  

 

여기서 stochastic adjacency matrix라는 개념이 등장합니다. 

이것이 무엇이냐면! 각 노드간의 관계를 나타내는 adjacency matrix가 확률로 표현되어 있는 것을 뜻합니다. 

위와 같이 adjacency matrix M이 있을 때, j 열은 총 3개의 노드와 인접해있다면(언급을 했다면), j열의 합은 3일 것입니다.

j열의 모든 합으로 각 인자를 나눠주면 됩니다. 

 

한가지 예를 들어보겠습니다. 

이렇게 생긴 그래프가 있다고 가정해봅시다. 

이 노드의 중요도는 각각 r_y, r_a, r_m일것입니다.

그렇다면 이제 각 노드들을 갱신시켜보겠습니다.

이렇게 식을 만들 수 있죠. 

 

이 식을 우리가 아까 만들었던 stochastic adjacency matrix로 표현할 수 있습니다. (M이라고 칭하겠습니다.)

위의 그래프에서 M을 구해보면 아래와 같습니다.

각 열의 합은 1이 됩니다. 

 

그렇다면 이제 각 노드의 중요도도 행렬로 나타내면 M과의 곱이 가능해집니다!

따라서 위와 같은 식을 얻을 수 있습니다. 

행렬 곱을 수행하면 우리가 초기에 설정했던 식을 그대로 얻을 수 있습니다. 

 

정말 간단하죠?

 

Connection to Random Walk

지난 3강에서 우리는 랜덤 워크에 대해서 알아봤었죠. 

페이지 랭크는이 랜덤워크의 개념과도 연결시킬 수 있습니다.

 

여기서는 인터넷을 떠돌아 다니는 web surfer가 있다고 해봅시다. 이 web surfer는 정말 랜덤하게 웹페이지를 돌아다닙니다. 

t시간에 페이지 i에 머물러 있다면, t+1은 i페이지에서부터 나가 또 다른 페이지에 있을 것입니다. 다음 페이지 또한 랜덤하게 고릅니다. 

랜덤하게 고를 때, 그 확률은 i페이지에 연결된 페이지의 수겠죠? 

 

t시점에 i페이지에 있다면, 그 때 특정 페이지에 머무를 수 있는 확률을 p(t)라고 하겠습니다. 이것은 각 페이지의 확률 분포로 볼 수 있습니다. 

 

그렇다면 p(t+1)은 아래와 같이 표현할 수 있습니다. 

무한히 반복하다 보면 결국에는 수렴하여 아래와 같은 수식을 얻을 수 있습니다. 

앗! 어디서 많이 본 수식이죠? 

바로 페이지 랭크의 수식인 r = M*r과 같습니다. 

 

따라서 랜덤 r은 랜덤 워크의 stationary distribution라고 할 수 있습니다. (페이지랭크는 랜덤워크의 최종 목적지와 같다고 할 수 있습니다.)

 

※ stationary distribution가 뭔가요?

각 노드사이를 계속 이동하다 보면 방문 횟수의 비율이 일정한 값으로 수렴하게 됩니다. 

각 방문 횟수들이 특정 확률 분포로 수렴하게 되는데 이 것을 stationary distribution라고 합니다. 

 

Eigenvector Formulation

고유 벡터는 어떠한 스칼라 λ에 대하여 식 λc = Ac를 만족하는 0이 아닌 벡터 c를 의미합니다. 

여기서! r = M * r을 위의 식과 유사하게 볼 수 있는데요. 

 

1*r = M*r로 볼 경우입니다. 바로 고유값 방정식이 완성되죠? 

 

여기서 web surfer가 무한히 페이지를 옮겨다니면 마치 katz방법 처럼 무한하게 M이 곱해지게 되고, 결국에는 아래의 식을 만족하게 될 것입니다. 

r은 고유값이 1인 M의 주 고유 벡터(가장 큰 값을 가지는 고유 벡터)가 될것입니다.