D.S

sungsoo.github.io

PageRank Algorithm

PageRank Algorithm Better Motivation, Different Thinking Sung-Soo Kim's Blog Home Tags Categories Archive PageRank Algorithm Tags algorithms 7 29 April 2014 Article Source Title: ‘쉽게 설명한’ 구글의 페이지 랭크 알고리즘 PageRank Algorithm “Google”이라는 230조원짜리 회사 가 처음 시작된 곳이 바로 이 세르게이 브린과 래리 페이지가 쓴 논문(The Anatomy of a Large-Scale Hypertextual Web Search Engine) 이었다는 것을 생각하면 한 번 시간을 들여 배워볼 만한 의미가 있지 않을까? 이 논문은 1998년에 쓰여졌으나, 논문에서 소개된 PageRank 알고리즘은 14년이 지난 지금에도 구글 검색 엔진의 핵심을 이루고 있다. 오늘날의 구글을 만든, 페이지랭크(PageRank) 알고리즘을 소개한 논문 에 포함되어 있던 세르게이 브린과 래리 페이지의 사진. 참 앳된 두 대학원생의 모습이다. 논문은 이렇게 시작한다. Our main goal is to improve the quality of web search engines. In 1994, some people believed that a complete search index would make it possible to find anything easily. (우리의 주요 목표는 검색 엔진의 품질을 향상시키는 것입니다. 1994년 당시, 사람들은 검색 인덱스를 완성하고 나면 무엇이든 쉽게 찾을 수 있을 것이라고 생각했습니다.) However, the Web of 1997 is quite different. Anyone who has used a search engine recently, can readily testify that the completeness of the index is not the only factor in the quality of search results. “Junk results” often wash out any results that a user is interested in. (하지만, 1997년의 웹은 사뭇 다릅니다. 최근에 검색 엔진을 사용해 본 사람이라면 누구나 인덱스를 완성하는 것만으로는 좋은 품질의 검색 결과를 얻을 수 없다는 것을 압니다. ‘쓰레기 정보’가 종종 사용자들이 진정 관심있어하는 정보를 가려버립니다.) One of the main causes of this problem is that the number of documents in the indices has been increasing by many orders of magnitude, but the user’s ability to look at documents has not. People are still only willing to look at the first few tens of results. (그러한 이유 중 하나는, 인덱스되는 문서의 숫자는 엄청난 속도로 성장하고 있지만, 사람들이 그 문서들을 볼 수 있는 능력은 같은 속도로 성장하지 않기 때문입니다. 사람들은 여전히 검색 결과중 처음 몇십 개 정도만 살펴볼 뿐입니다.) Because of this, as the collection size grows, we need tools that have very high precision. Indeed, we want our notion of “relevant” to only include the very best documents since there may be tens of thousands of slightly relevant documents. (그렇기 때문에, 인터넷이 성장할수록, 우리에게 더 정밀한 도구가 필요합니다. 사실, 우리는 ‘관련 있는 페이지’가 수만 개라도, 그 중 최고의 웹 페이지만을 정확하게 찾아주기를 원합니다.) There is quite a bit of recent optimism that the use of more hypertextual information can help improve search and other applications. In particular, link structure and link text provide a lot of information for making relevance judgments and quality filtering. Google makes use of both link structure and anchor text. (하이퍼텍스트 정보를 이용하면 검색 결과를 많이 향상할 수 있다는 최근의 연구 결과가 있습니다. 특히, 웹 페이지 사이의 연결 관계가 상당히 유용한 정보를 제공해줄 수 있습니다. 구글은 바로 이러한 링크 구조와 링크 달린 텍스트를 이용합니다.) 그리고, 페이지랭크 알고리즘을 다음과 같이 소개한다. Academic citation literature has been applied to the web, largely by counting citations or backlinks to a given page. This gives some approximation of a page’s importance or quality. PageRank extends this idea by not counting links from all pages equally, and by normalizing by the number of links on a page. (학술지 인용 방식은 그동안 웹에 적용되어 왔습니다. 특히, 특정 페이지를 인용하는 다른 페이지가 얼마나 많이 있느냐를 세는 방식으로요. 이렇게 하면 특정 페이지가 얼마나 중요한 지 알 수 있스니다. PageRank는 이러한 아이디어를 연장하는데, 즉, 다른 페이지에서 오는 링크를 같은 비중으로 세는 대신에, 그 페이지에 걸린 링크 숫자를 ‘정규화(normalize)’하는 방식을 사용합니다.) 말이 좀 어려운데, 아래 수식을 한 번 보자. PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)) PR은 PageRank의 줄임말이고, PR(A)는 ‘A’라는 웹페이지의 페이지 랭크를 의미한다. T1, T2, … Tn은 그 페이지를 가리키는 다른 페이지들을 의미한다. 그리고  PR(T1)는 당연히 T1이라는 페이지의 페이지 랭크값이다. d는 ‘Damping Factor’라고 하는데, 설명이 길어질 수 있으니 조금 후 설명하겠다. C(T1)는 T1이라는 페이지가 가지고 있는 링크의 총 갯수를 의미한다. d에 연연하지 않고(즉 d=1이라고 가정하고) 위 수식을 가만히 보면 사실 매우 간단하다. ‘어떤 페이지 A의 페이지 랭크는 그 페이지를 인용하고 있는 다른 페이지 T1, T2, T3, .. 가 가진 페이지 랭크를 정규화시킨 값의 합‘이다. 다시 말해 페이지 A의 페이지 랭크는 A라는 페이지를 가리키고 있는 다른 페이지의 페이지 랭크값이 높을수록 (즉, 더 중요할수록) 더 높아진다. 여기서 ‘정규화시킨 값의 합‘이라는 말을 굳이 쓴 이유는, 페이지 랭크의 단순 합산이 아니기 때문이다. 예를 들어, T1의 페이지 랭크가 높다고 하더라도, 그 페이지에서 링크를 수천 개 달아놓았다면(즉, C(T1)값이 높다면) 그 페이지가 기여하는 비중은 낮아진다. 이 수식을 그림으로 한 번 표현해보겠다. PageRank 알고리즘을 그림으로 표현한 것. Dampen Factor가 있기 때문에 이것과 똑같지는 않지만, 간단하게 표현하면 위와 같다. 위 그림에서 웹 페이지 A를 가리키는 페이지는 T1, T2, T3, T4, T5의 다섯 개가 있고, 이들을 정규화해서 합한 값이 0.34이므로, A의 ‘페이지 랭크’는 0.34가 된다. 이 페이지랭크 값은 A가 가리키는 또 다른 페이지의 PageRank를 계산하는 데 쓰일 것이다. 그럼 T1의 페이지 랭크는 어떻게 구했나? 마찬가지로 T1을 가리키는 다른 페이지들의 PageRank값으로부터 구한다. 이렇게 해서 파고 내려가면 무한히 가게 될 것 같은데, ‘제한 조건’을 걸면 언젠가는 계산이 끝이 난다. 이러한 방법으로 계산하는 것을 컴퓨터 과학에서는 ‘recursive(재귀적)‘이라고 한다. 즉, PageRank는 재귀 호출 알고리즘이다. 이제 d, 즉 Damping Factor에 대해 생각해 보자. 위 수식을 다시 한 번 보자. PR(A) = (1-d) + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn)) d 값은 0과 1 사이에서 정해지는데, d값이 커져서 1이 되면 앞의 (1-d)는 0이 되고, 뒤 수식의 합이 그대로 A의 PageRank가 된다. 이것이 바로 위 그림에서 가정한 상황이다. 반대로 d값이 작아져서 0이 되면, 뒤 수식의 합은 0이 되고, A의 PageRank는 1이 된다. d가 0이면 모든 페이지의 PageRank는 1이 되므로 아무 의미가 없어진다. 그래서 d는 실험을 통해 0과 1 사이의 어떤 값에서 정해지는데, 논문에서는 보통 0.85로 설정해놓았다고 되어 있다 . 논문에 따르면 damping factor란 ‘어떤 마구잡이로 웹서핑을 하는 사람이 그 페이지에 만족을 못하고 다른 페이지로 가는 링크를 클릭할 확률‘이다. 즉, damping factor가 1이면, 무한히 링크를 클릭한다는 뜻이고, 0이면 처음 방문한 페이지에서 무조건 멈추고 더 이상 클릭하지 않는다는 뜻이다. 0.85이면, 85%의 확률로 다른 페이지를 클릭해볼 것이라는 뜻이다. 이 경우 15%의 확률에 걸리는 순간 클릭을 멈추고 그 페이지를 살펴본다. 논문에 따르면, 모든 웹페이지의 페이지랭크 값을 합산한 값은 1이 된다고 한다. 그러나 이 수식을 보면 그렇게 되어 있지 않다. 예를 들어 d가 0이면 PR(A)는 1이 되고, 모든 웹페이지의 PageRank가 1이 되기 때문에 PageRank의 합산은 모든 페이지의 숫자(N)이 된다. 위키피디아에 따르면 , 세르게이와 래리가 논문을 쓸 때 실수한 것 같다며, 올바른 수식은 아래와