‘쉽게 설명한’ 구글의 페이지 랭크 알고리즘

네이버 검색엔진의 문제점을 처음 지적한 글을 썼던 2년 전부터 이 블로그에 언젠가 한 번 써보고 싶었던 주제가 하나 있었다. 구글의 PageRank 알고리즘을 설명하는 것이다. 원리는 간단하지만 알고리즘을 설명하려고 하면 말이 길어질 것 같고 쉽게 설명할 수 있을까 싶어 블로그에 쓸까 말까 망설였는데, 그냥 한 번 시작해보려고 한다. “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)이 된다.

위키피디아에 따르면, 세르게이와 래리가 논문을 쓸 때 실수한 것 같다며, 올바른 수식은 아래와 같다고 한다.

PR(A) = (1-d)/N + d (PR(T1)/C(T1) + … + PR(Tn)/C(Tn))

이렇게 하면 전체 페이지의 PageRank를 합산한 값이 1이 된다.

페이지랭크와 그 관계를 도식화한 그림. A, B, C 등은 페이지를 나타내고, 숫자는 PageRank를 의미한다. C의 경우 B에서 링크를 걸었다는 것만으로도 PageRank값이 높게 책정됨을 볼 수 있다. (출처: Wikipedia)

이게 다이다. 이렇게 해서 온 세상의 모든 페이지를 PageRank 등수에 따라서 미리 정렬을 해 두면, 누군가가 검색어를 입력하는 순간, 그 검색어가 포함된 페이지들을 순위별로 나열하기만 하면 끝이다. 구글의 검색 엔진팀에 있는 지인의 말에 따르면, 지금의 구글 검색 알고리즘은 엄청나게 많은 다른 요소를 고려하고, 튜닝을 했기 때문에 이것보다 훨씬 복잡하다고 한다. 그러나 앞에서 말했듯, ‘영향력 있는 페이지가 인용할수록 페이지랭크가 올라간다‘는 근본적인 알고리즘은 그대로 남아 있다.

구체적 예를 들면 이와 같다. 내 블로그를 인용한 다른 블로그들이 있다. 그 중 아마 가장 사람들에게 신뢰를 얻고 인기 있는 블로그 중 하나가 ‘에스티마의 인터넷 이야기‘일 것이다. 또한 그 블로그를 상당수의 사람들이 인용했을 것이므로 구글 검색 순위가 높을 것이다. 이런 상황이라면, ‘에스티마의 인터넷 이야기’에서 내 블로그로의 링크를 거는 순간 내 블로그의 PageRank는 많이 올라갈 수 있다. 마찬가지 이유로 인기가 있는 다른 웹사이트에서 내 블로그로 링크를 걸면 PageRank가 올라간다. 그러나 만약 그 사이트에서 나 뿐만 아니라 엄청나게 많은 블로그로 링크를 걸고 있다면 (예를 들어, 단순히 수만개의 블로그 주소를 나열한 경우), 그 사이트가 아무리 인기 있다 해도 내 블로그의 검색 순위는 크게 상승되지 않는다.

또 한가지 예로, Stanford.edu와 같은 사이트의 경우 조회수가 엄청나게 높다. 따라서 이 사이트에서 누군가에게 링크를 걸어주면, 구글 검색 순위가 바로 상승할 수 있다. 예전에 Stanford.edu를 관리하는 사람이 돈을 받고 특정 사이트에 링크를 걸어주는 사업을 한 적이 있다고 MBA 수업 시간에 교수님이 이야기한 적이 있다. 물론, 구글이 이를 가만히 놔두지 않았기 때문에 그런 방식은 더 이상 통하지 않는다.

여기에서 덧붙일 말이 있다. 이렇게 훌륭한 알고리즘이지만, 소위 ‘불펌’이 만연하는 곳에서는 이 알고리즘은 바보가 된다는 사실이다. 글을 ‘퍼가기’ 하면서 원문의 링크를 걸지 않는다면, 이 알고리즘에 따르면 아무리 많은 사람들이 퍼가도 웹사이트의 순위는 올라가지 않는다. 한국 인터넷에서는 싸이월드, 또는 그 이전 시절부터 출처 없이 ‘퍼가기’가 참 유행했다. 네이버 블로그가 생기고, 이렇게 글을 퍼가기 해서 많이 쌓아둘수록 블로그 순위가 올라가자 사람들은 더욱 정신없이 ‘퍼가기’를 했다. 그 결과 인터넷은 지저분해지고, ‘내리와 인성의 IT 이야기‘라는 인기 웹툰에서 밝혔듯 원본 문서는 찾기가 힘들어졌다. 이런 상황에서 구글이 한국 시장에 진입했으니, 처음에 구글 검색 결과가 네이버에 비해 훨씬 뒤쳐져 있었던 것은 당연하다. 다행히 요즈음엔 이런식의 ‘펌 문화’가 많이 잦아들었고, 원본의 링크를 다는 ‘건전한 문화’가 많이 정착되면서 원글을 찾기도 쉬워졌고, 구글 검색의 품질도 좋아졌다.

PageRank, 구글이 야후보다 월등히 좋은 검색 결과를 낼 수 있었던 비결이었고, 결국 야후를 꺾고 검색 엔진의 대명사로 등극한 출발점이었다.

29 thoughts on “‘쉽게 설명한’ 구글의 페이지 랭크 알고리즘

  1. 평소 의미 있고 좋은 글 잘 읽고 있습니다. 포스트를 읽다가 궁금한 점이
    있어 문의 드립니다.

    본문 중에 “A 페이지랭크는 A를 가리키고 있는”에서 가리키고 있다는 의미가
    단순히 A의 내용을 언급하거나 인용하는 것과 링크를 포함한 것인지,
    아니면 정확하게 링크나 출처가 연결되어 있어야 한다는 의미인지 알고 싶습니다.

    즉 A페이지랭크값을 구할 때 A를 가리키는 다른 페이지들의 랭크값과 링크값에
    영향을 받는데, “A를 가리킨다”는 의미가 정확하게 무엇인지 궁금합니다.
    링크로 연결이 안 되어 있고 A페이지의 본문 내용 일부를 언급하거나 인용만 해도
    “A를 가리킨다”라고 이야기할 수 있는 건지요?

    감사합니다.^^

  2. 저도 최근에 우연히 PageRank 논문을 다시 읽어 보았는데, 수학적으로 쉽고 간결해서 아름답고 참 재밌는 논문이라는 생각을 했습니다 😀 성문님이 쉽게 설명해 주셔서 재밌게 읽었습니다..
    그런데 마지막줄에 “PageRank, 구글이 야후보다 월등히 좋은 검색 결과를 낼 수 있었던 비결이었고, 결국 야후를 꺾고 검색 엔진의 대명사로 등극한 출발점이었다.” 라고 했는데, 이건 약간 이견의 여지가 있다고 생각합니다. 옛날 어느 논문에서 IR의 질을 좌우하는 것은 샘플의 갯수이지, 알고리즘은 중요한 영향을 끼치지 않는다는 말을 했던 것으로 기억합니다.
    저는 이 주장에 체감상 꽤 동의합니다. 예를들어 구글이 지금 세계 최고 수준의 음성인식기술을 갖고 있는데, 지난 몇 년간 구글이 한 것은 알고리즘을 발전시킨 게 아니라 체집하는 샘플의 갯수를 엄청나게 많이 구했기 때문이라고 알고 있습니다. 실제로 아는 한 구글러^^ 의 말에 의하면 학습 알고리즘은 완전 단순한 것을 사용한다고 들었습니다. 물론, 구글같은 경우는 웹페이지를 많이 채집하는게 정확도를 높이기도 하고 보여줄 수 있는 페이지를 많이 얻는다는 의미도 있겠지만요..
    그래서 구글이 성공할 수 있었던 요인은 알고리즘도 있지만, 그보다 GFS, MapReduce 등 클라우드 컴퓨팅이라고 보는 게 좋지 않을까요?

  3. 예전에 무심코 보고 넘어갔던 포스트인데, 이번 학기에 수강하는 강의에서 이 내용을 다루고 있어서 이해에 많은 도움이 되었습니다. 감사합니다! 🙂

  4. Part of your description of PageRank is very incorrect.

    1. The reason why the algorithm converges is not because the web graph has limited size, but because of its probabilistic property. Just google with “PageRank convergence proof” to figure out.
    2. Your description of the damping factor is wrong. The random surfer model is such that with some probability (d, the damping factor) the surfer clicks a link in the current page, and with probability 1-d, the surfer starts from a random page (that is not related to the current page). “Stop clicking” (in wikipedia page) does not mean that the surfer is satisfied with the current page, but it means the surfer enters a random page instead of clicking.

    While the rest of your description looks good, I thought the above are important details that the readers of this blog should be aware of. The damping factor is required for the algorithm to converge.

    1. Hi Jay,

      Thank you for the comments. I had this verified by a search engineer at Google before posting it, so I was surprised to hear that part of the description is incorrect. I read the thesis again. You are right.
      1. PageRank convergence: You’re right. PageRank converges because the user behavior resembles Marcov chain. Frankly, I did not completely understand why PageRank converges due to its probabilistic property. Anyway, I believe it’s beyond the purpose of this article to explain why PageRank converges.
      2. Damping factor: According to the thesis, the d damping factor is defined as “the probability at each page the ‘random surfer’ will get bored and request another random page”. I have over-interpreted the word “bored”, and put the antonym “satisfied” for the case where ‘d=0’. But you are right. It does not necessarily mean that the surfer is satisfied.

      I made some corrections to the article. Again, I really appreciate it!

      1. Thanks for mentioning about Markov chain. After learning about the concept from other sources I got much better understanding about PageRank. I think your tutorial can deliver much more if you would go more in detail about Markov Chain. 🙂

  5. 승승장구하던 페이스북이 주춤거리는 느낌을 줍니다. 지난 5월 기업공개 후 안좋은 얘기가 종종 나오고

  6. 좋은내용의 글 잘읽었습니다. 감사합니다~
    궁금한점이 하나있는데요 페이지랭크가 높은 블로그에서 내블로그와 수많은 다른블로그들의 주소를 나열하면 내블로그의 페이지랭크는 크게 영향을 받지 않는다고 하는데 내블로그의 링크하나는 어짜피 정규화를 해도 38.4/1 로 38.4의 높은 패이지랭크값을 내블로그도 갖게되는게 맞지 않나요? 제가 이해를 잘못한건지… 궁금합니다.

  7. I am really impressed with your writing skills as well as with
    the layout on your blog. Is this a paid theme or did you customize it yourself?
    Either way keep up the nice quality writing, it’s rare to see
    a nice blog like this one these days.

  8. page rank의 공식의 의미를 시각적으로 잘 표현해주셔서 이해가 잘 되었습니다.
    감사합니다~

  9. 성문님의 이 포스팅은 지금(2014.6)읽어봐도 구글 검색 알고리즘을 가장 쉽고 정확하게 보여주는 포스팅인것 같습니다. Two thumbs up!

  10. Text Retrieval 공부하는데 정말 도움이 되는 포스팅이네요.
    그런데 위의 Jay님의 피드백에 따라 포스팅을 수정하신 것 같은데 어느 부분을 수정하셨는지 말씀해 주시면 좀 더 잘 이해할 수 있을 것 같습니다.
    감사합니다 🙂

Leave a Reply to Sungmoon Cancel reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s