웹페이지 랭킹 알고리즘: HITS vs PageRank

웹 정보검색 시스템을 구축했을 때, 사용자가 요청한 어떤 검색(질의, query)에 대해서 최상의 결과를 보여주기 위한 방법을 끝없이 고민해야 한다.

 

 

 

이런 시스템을 구축하기 위해선, 인터넷의 정보를 굉장히 많이 수집(Crawling)해서 잘 저장하고 인덱싱을 함으로써, 어떤 단어가 포함된 문서를 빠르게 찾을 수 있게 정리를 해두어야 한다.

 

이 때 이용하는 것이 Inverted Index 방법인데, 수많은 문서들이 있을 때 어떤 단어가 어떤 문서에 몇 개 들어있는지 테이블로 기록해두는 것이다. [ "tistory": { (문서1, 10개), (문서2, 21개) },  "google": { (문서2, 20개), (문서4, 12개) } ] 이런 식으로 말이다.

 

그리고 분산 저장을 위해서는 구글에서 만든 GFS(Google File System)이라는 분산 저장 기술이 쓰이고, 이를 Java로 구현해 오픈소스화한 것이 하둡의 HDFS(Hadoop Distributed File System)이다.

 

 

 

하지만 위처럼 잘 저장해서 단어 검색을 빠르게 할 수 있게 정리를 하더라도, 사용자의 검색어가 포함된 문서들을 검색했을 때 무엇이 가장 질 좋은 문서인지는 알기 어렵다. 예를 들어, 앞의 예시에서 tistory라는 단어가 문서 1은 10개, 문서 2는 21개 들어있지만, 사용자가 tistory라고 검색했을 때 꼭 문서 2가 더 좋은 페이지라고 주장하기는 어렵다. 그 단어가 많이 나왔다는 이유로 질 좋은 데이터라고 보기에는, 상관이 전혀 없지는 않겠지만 이것만으로는 합리적이지 못하다.

 

그래서 텍스트 정보를 이용하는 대신, 웹페이지 간의 링크(이런 거)로 연결된 관계를 이용해 페이지의 가치를 메기는 Link Analysis 방식이 쓰이게 된다. 가치가 높은 페이지 A가 링크를 통해 페이지 B를 가리킨다면, B 또한 가치가 높을거라는 아이디어에서 착안한 것이다. 즉, 페이지 A에 있는 링크가 페이지 B를 가리킬 때, A를 Hub 페이지, B를 Authority 페이지라고 부르는데, Hub의 가치가 높을수록 Authority의 가치 또한 높을 거라는 것이다.

 

Hub 페이지의 가치가 높으면, 이것이 가리키는 Authority 페이지의 가치 또한 높다고 본다.

 

이런 가설을 이용해 만들어진 대표적인 두 알고리즘이 바로 HITS와 PageRank이다. 특히 PageRank는 구글 검색엔진의 최초 시스템에서부터 이용된 알고리즘으로 유명하다.

 

이 두 알고리즘은, 먼저 모든 페이지의 초기 랭크를 임의로 정하고(모두 같게 정하든, 랜덤으로 정하든 상관없다), 각 페이지의 랭크 계산을 여러 번의 iteration을 거쳐 계산하면, 페이지들의 랭크가 점점 수렴해서 최종 랭크값을 얻을 수 있다. 초기값에 상관없이 같은 결과값에 수렴한다. 이 때 랭크를 계산하는 알고리즘이 HITS, PageRank 등 여러가지가 있는 것이다.

 

 

링크로 연결해 구성한 페이지들이 있을 때, 각 페이지의 랭크 값을 나름대로 초기화하고

 

계산을 반복하면 최종 랭크 값에 수렴한다.

 

 

1. HITS (Hyperlink-Induced Topic Search)

 

HITS 알고리즘은, 각 페이지가 2개의 랭크 값을 갖는다. Hub 페이지로서의 랭크와, Authority로서의 랭크 값이다.

 

1) Hub로서의 랭크 h는, 자신이 가리키는 Authority들의 랭크 값의 합이다.

2) Authority로서의 랭크 a는, 자신을 가리키는 Hub들의 랭크 값의 합이다.

3) h와 a를 한번 계산할 때마다 normalization 한다. 단순 합이기 때문에, 계산을 반복하면 무한히 늘어나기 때문이다.

    h의 제곱들의 합 = a의 제곱들의 합 = 1 이 되게 하는, L2 normalization을 이용한다.

 

위 1)~3)을 반복하다보면, 각 페이지의 h와 a가 같아지고 수렴하게 된다. 이 때의 값을 최종 랭크 값으로 한다.

 

HITS 수식

 

2. PageRank

 

PageRank 알고리즘은, 각 페이지의 랭크를 계산할 때 자신을 가리키는 Hub 페이지들의 랭크에서, 그 Hub 페이지가 가진 링크(out-going link) 개수로 나눈 것의 합을 이용한다.

 

PageRank 수식

 

예를 들어, 아래 그림처럼 Authority 페이지의 랭크를 계산할 때, 자신을 가리키는 Hub A의 랭크가 0.3이고 링크를 3개 가졌다면 (0.3 / 3), 또 Hub B의 랭크가 0.5이고 링크를 2개 가졌다면 (0.5 / 2)로 계산해서, 이것들의 합 (0.3/3 + 0.5/2)을 구하는 것이다.

 

 

 

또, 링크를 통하지 않더라도 페이지에 접근하는 방법은 많다. 주소창에 URL을 직접 칠 수도 있고, 메일이나 카톡 등을 통해 URL을 전달하는 경우도 많으니까. 이러한 경우를 Random Jump라고 부르고, 이를 1/#page(=페이지의 총 개수) 로 계산한다.

 

이렇게 해서, "링크를 이용한 계산식"과 "Random Jump 계산식" 2개의 합을 이용하는데, 전자에는 c를 곱하고, 후자에는 (1-c)를 곱한다. 즉 c가 높을 수록, Random Jump를 통한 이동보다, 링크를 통한 이동을 더욱 비중있게 보겠다는 의미이다. c는 [0,1] 사이의 값으로, 극단적으로 c=1이라면 (1-c = 0) 이 되어서 Random Jump를 전혀 고려 안하고 링크를 통한 관계로만 랭크를 계산하겠다는 의미이다. 하지만 Random Jump의 경우가 실제로 많이 있으므로, 이를 고려하는 것이 더 좋다.

 

앞에서, HITS를 설명하기 직전에 봤던 이 그림이 PageRank를 계산한 결과이다. 모든 페이지의 랭크를 1로 초기화해서 계산을 시작해서, 계산을 12회 반복하면 이런 결과에 도달한다.

 

 

계산을 반복하면 최종 랭크 값에 수렴한다. (PageRank, 12회 반복)

 

 

3. HITS vs PageRank

 

이 둘을 비교하면 어느 것이 더 성능이 좋을까? 정답은, 더 많은 것을 고려해 랭크를 계산하는 PageRank 방법이다. 크게 두 가지의 차이를 볼 수 있다.

 

첫째는, Hub 페이지의 랭크 값에서 그 페이지의 링크 개수로 나눈다는 것이다. 예를 들어 A가 B를 가리킬 때(A=hub, B=authority), 랭크가 높은 A가 단 한 개의 링크를 가지는데 그것이 B를 가리키고 있다면 B 또한 가치가 높다고 볼 수 있다. 하지만 A가 가진 링크가 1000개가 있고 그 중 하나가 가리키는 것이 B일 뿐이라면, A가 아무리 가치가 높아도 그것이 B에게 미치는 영향은 적다. PageRank는 이런 경우에 hub의 랭크를 1000으로 나눔으로써 그 영향이 적어짐을 고려한다. HITS는 단순히 hub의 랭크를 합하기만 하기 때문에 이를 고려하지 못한다. 현실에서의 상황을 상식적으로 생각했을 때 PageRank의 방법이 더 합리적이라고 볼 수 있다.

 

둘째는, Random Jump를 고려한다는 점이다. PageRank 설명에서도 얘기했지만, 꼭 링크를 통해서만 페이지에 접근하는 것이 아니다. 주소창에 URL을 직접 치거나, 메일이나 카톡 등으로 URL을 주고받거나, 워드 파일 등의 URL을 보고 접근하거나 등등 웹사이트에 접근하는 방법은 다양하다. 이러한 점이 현실과 더 가깝기 때문에, 이를 고려한 PageRank의 성능이 더 좋다고 볼 수 있다.