The PageRank algorithm is an important component for ranking Web pages in Google and other search engines. While many improvements for the original PageRank algorithm have been proposed, it is unclear which variations (and their combinations) provide the “best” ranked results. In this paper, we evaluate the ranking quality of the well-known variations of the original PageRank algorithm and their combinations. In order to do this, we first classify the variations into link-based approaches, which exploit the link structure of the Web, and knowledge-based approaches, which exploit the semantics of the Web. We then propose algorithms that combine the ranking algorithms in these two approaches and implement both the variations and their combinations. For our evaluation, we perform extensive experiments using a real data set of one million Web pages. Through the experiments, we find the algorithms that provide the best ranked results from either the variations or their combinations.
PageRank 알고리즘은 구글(Google)등의 검색 엔진에서 웹 페이지를 ranking하기 위해 사용되는 중요한 컴포넌트이다. Original PageRank 알고리즘의 성능을 향상시키기 위해, 많은 variation들이 제안되었으나, 어떤 variation(혹은 variation들간의 조합)이 “best” ranking 결과를 제공하는지는 명확하지 않다. 본 논문에서는 original PageRank 알고리즘의 잘 알려진 variation들과 그들간의 조합들에 대한 ranking quality를 평가한다. 이를 위해, 먼저 variation들을 웹의 link 구조를 이용하는 Link-based approaches와 웹의 의미 정보를 이용하는 Knowledge-based approaches로 분류한다. 다음으로, 이 두가지 approach에 속하는 알고리즘들을 조합한 알고리즘들을 제안하고, variation과 그들을 조합한 알고리즘들을 구현한다. 백만개의 웹 페이지들로 구성된 real data set에 대한 실험을 통해 PageRank의 variation과 그들간의 조합들로부터 best ranking 결과를 제공하는 알고리즘을 찾는다.