구글의 핵심 알고리듬인 페이지랭크 (PageRank)를 설명

구글의 핵심 알고리듬인 페이지랭크


(PageRank)를 설명해준 구글 개발자 세르게이 브린의 논문 번역입니다

Abstract
웹 페이지의 '중요성'은 본질적으로 주관적인 문제여서, 읽는 사람의 관심사나 지식 그리고 태도등에 의존하는 문제이다. 하지만 웹 페이지의 상대적 중요성에 관해서는 객관적으로 얘기할 수 있는 부분이 많다. 이 논문은 "PageRank"라는, 웹 페이지를 객관적이고도 기계적으로 순위를 매겨서 읽는 사람의 관심이나 기울이는 주의를 효과적으로 측정할 수 있는 수단을 설명한다. 우리는 PageRank를 이상적인 랜덤 웹 써퍼(random web surfer; 무작위로 선택된 웹 써퍼)에 비교해 볼 것이며, 많은 웹페이지에 있어서 어떻게 PageRank를 능률적으로 계산할 수 있는지를 설명할 것이다. 그리고 어떤 방식으로 PageRank를 검색이나 사용자 네비게이션에 응용할 수 있는지를 보여주고자 한다.

1. 도입과 동기 (Introduction and Motivation)
월 드와이드웹(World Wide Web; www)은 정보 인출 (Information Retrieval)에 새로운 과제를 안겨 주었다. 웹은 매우 매우 거대하며 이질적(heterogenous)이다. 현재 추산으로도 약 1억 5천만 페이지 이상이 웹에 존재하며, 이 숫자는 매년 적어도 두 배씩 커지고 있다. 보다 중요한 점은 웹 페이지들은 극단적으로 다양해서, 예를들면 "철수가 오늘 점심 때 뭘 먹었지?"와 같은 질문이 있는가 하면 정보 인출에 관한 전문적 논문집이 있기도 하다. 이러한 주된 도전 과제들 외에도 웹에는 익숙하지 못한 초보 사용자들 그리고 검색 엔진의 순위 매기는 기능(ranking function)을 교묘히 이용하려는 많은 웹 페이지들로부터 비롯되는 문제점이 있다.

그러나 웹은 다른 "평면적"인 문서 모음(flat document collections)과 달리 하이퍼텍스트라는 것이 있다. 이 하이퍼텍스트(hypertext)는 웹 페이지 자체의 텍스트 외에 링크 구조(link structure)나 링크 텍스트(link text) 같은 상당한 수준의 부가적인 정보를 제공한다.

이 논문에서 우리는, 모든 웹 페이지를 보편적 "중요도" 순으로 순위 매기기 위해 웹의 링크 구조를 사용하였다. 이 랭킹은 페이지랭크(PageRank)라 하며, 검색엔진 또는 웹 사용자가 월드와이드웹이라는 거대한 이질적 세계를 빠르게 이해할 수 있게 도와준다.

1.1 웹 페이지의 다양성 (Diversity of Web Pages)
학 술적 인용(academic citation)을 분석한 문헌은 이미 많이 존재하지만 웹 페이지와 학술 출판물 사이에는 많은 중요한 차이가 있다. 학술 논문은 철두철미하게 리뷰되지만 웹 페이지는 '품질 관리'나 '출판 비용' 없이 늘어난다. 단순한 프로그램 하나만으로도 엄청난 숫자의 페이지를 손쉽게 만들어 낼 수있으며 인위적으로 인용 횟수를 쉽게 부풀릴 수 있다. 웹 환경속에는 그 속에서 이익을 찾는 많은 벤쳐들이 있기 때문에 이들이 사용자의 주의를 끌어오는 전략 역시 검색 엔진 알고리듬의 발달에 맞춰서 함께 진화되어 왔다. 이러한 이유로 복제가능한 특징을 세는 방식으로 웹페이지를 평가하려는 전략은 손쉽게 악용될 수 있다. 게다가, 학술 논문의 경우는 그 갯수를 정확히 셀 수 있을 뿐만 아니라 사실상 질적인 면 및 인용 횟수 등에서 유사하고 그 목적 역시 비슷하다. (대개 '지식의 몸체'를 키우기 위한 목적으로 만들어진다) 하지만 웹 페이지는 질적인 면에서나 사용적인 측면, 인용, 길이 등에 있어서 학술 논문보다 훨씬 더 다양하다. IBM 컴퓨터에 관한 애매한 질문들을 모아놓은 것은 IBM 홈페이지와 매우 다르다. 운전자에게 휴대폰이 미치는 영향에 관해서 연구한 논문은 특정 휴대폰 회사의 광고와 매우 다르다. 사용자가 읽은 웹 페이지의 평균적인 질은 평균적인 웹 페이지의 질보다 높다. 그것은 웹 페이지를 만들고 퍼블리슁 하는 것이 매우 쉽기 때문에 웹 상에는 사용자들이 읽지 않으려하는 많은 저품질의 웹 페이지가 있기 때문이다.

웹페이지는 여러가지 분화될 수 있는 요소가 많이 있다. 이 논문에서 우리는 그 중의 하나 - 웹 페이지의 상대적 중요성을 어떻게 추산할 것인가 - 라는 문제를 주로 다룬다.

1.2 페이지랭크 (PageRank)
웹 페이지의 상대적 중요성을 측정하기 위해 우리는 페이지랭크 라는 웹을 그래프로 표현한 것을 기반으로 모든 웹 페이지를 순위매김(ranking)하는 방식을 제안한다. 페이지랭크는 검색이나 브라우징, 트래픽 추산등에 적용될 수 있다. 섹션 2에서는 페이지랭크의 수학적인 기술을 다룰 것이며 그것의 직관적인 정당화(intuitive justification)를 얘기할 것이다. 섹션 3에서는 5억1800만개에 이르는 하이퍼링크에 대해 어떻게 효율적으로 페이지랭크를 계산할 수 있는지 보여주고자 한다. 페이지랭크의 유용성을 테스트 해보기 위해 우리는 구글(Google)이라는 웹 검색 엔진을 구축했다. 이것은 섹션 5에서 다룬다. 섹션 7.3 에서는 페이지랭크가 어떻게 브라우징을 도울 수 있는지를 보여주고자 한다.

2. 웹상의 모든 페이지의 순위 매기기 (A ranking for every page on the Web)
2.1 관련 자료
학술 인용 분석에 관해서는 엄청나게 많은 연구가 이미 존재한다. Goofman은 과학 커뮤니티에서 일종의 유행병처럼 정보 흐름이 퍼져 나간다는 것을 주장한 흥미로운 이론을 발표하기도 했다.

웹 과 같은 대형 하이퍼텍스트 시스템에서 어떤 방식으로 링크 구조(link structure)를 이용할 수 있는지에 관해서도 최근 상당한 연구가 이뤄지고 있다. Pitkow는 최근 다양한 방식의 링크 기반 분석을 설명한 "월드와이드웹 생태계의 특징"이라는 제목의 박사 학위 논문을 완성했다. Weiss는 링크 구조를 감안한 클러스터링 방식에 대해서 논했다. Spertus는 여러가지 적용사례에 있어서 링크 구조로 부터 얻어낼 수 있는 정보에 관해 발표했다. 좋은 시각화를 위해서는 하이퍼텍스트에 부가적인 구조가 필요하다는 연구도 있었다. 최근 Kleinberg는 웹을 서로 서로 인용하는 행렬로 보고 그 고유벡터(eigenvector)를 계산하는 방식을 기반으로 "헙과 오또리티"(Hubs and Authorities) 모델"이라는 흥미로운 모델을 개발했다. 마지막으로, 도서관 커뮤니티쪽에서는 웹의 "질"이라는 것에 대해 관심을 갖고 있기도 하다.

일반적인 인용 분석 테크닉을 웹의 하이퍼텍스트적 인용 구조에 적용하고자 시도하는 것은 너무도 자연스러운 것이다. 즉 단순하게 웹 페이지에 있는 링크 하나하나를 학술적 인용처럼 생각해볼 수 있는 것이다. 그러므로 야후!같은 메이져 페이지의 경우는 야후!를 가르키는 수만, 수십만개의 백링크(backlinks) 또는 인용을 갖고 있는 것이 된다.

야후! 홈페이지가 아주 많은 백링크를 갖고 있다는 사실은 야후! 홈페이지가 매우 중요하다는 사실을 함축한다. 사실 많은 웹 검색엔진들은 어떤 페이지가 얼마나 중요한가 내지는 높은 질을 갖고 있는가를 판단할 때 백링크 숫자를 세어서 이를 바탕으로 가중치를 주고 있다. 하지만 단순히 백링크의 갯수를 세는 것은 많은 문제점을 갖는다. 이 문제점들은 학술 인용 데이타베이스에서는 존재하지 않는 웹만의 특징과 관련이 있는 것들이다.

2.2 웹의 링크 구조 (Link Structure of the Web)
약간의 편차는 있지만 현재 웹에는 약 1억5천만 페이지와 17억개의 링크가 있다고 알려져 있다. 이를 그래프 이론(graph theory)으로 표현하자면 웹이라는 그래프는 약 1억5천만개의 노드(node)와 17억 개의 엣지(edge)를 갖고 있는 것이다. 각각의 웹페이지는 그 페이지로부터 밖으로 나가는 링크(forward link; outedges)와 그 페이지를 가르키는 백링크(backlink; inedges)를 갖는다. 어떤 페이지의 모든 백링크를 다 찾아낸다는 것은 불가능 하지만 포워드링크는 알 수 있다.


웹 페이지가 백링크를 몇 개나 갖느냐는 매우 다양하다. 예를들어 우리가 갖고 있는 데이타베이스에 따르면 넷스케잎 홈페이지는 62804개의 백링크를 갖는데 반해 대개의 페이지들은 단지 몇 개의 백링크만을 갖는다. 일반적으로 링크가 많이 된 페이지일수록 그렇지 못한 페이지보다 더 "중요하다". 학술 인용에서도 인용의 갯수를 세는 단순한 방법이 미래의 노벨상 수상자를 예측하는데 사용될 수 있다. 페이지랭크는 인용 횟수를 세는 방식 이상의 훨씬 더 정교화된 방법을 제시한다.

페이지랭크가 흥미로운 이유는 단순히 인용 횟수만 세는 경우 일반적인 의미의 중요성이라는 개념과 일치하지 않는 경우가 매우 많기 때문이다. 예를들어 어떤 웹페이지가 야후!에 링크가 되어 있다면 그 페이지는 오직 하나의 백링크 밖에 없지만 그 링크는 매우 중요한 링크다. 야후!에 링크된 그 페이지는 다른 별볼일 없는 여러 곳에서 링크된 페이지 보다 더 높은 순위를 가져야 한다. 페이지랭크는 링크 구조만을 사용해서 어떻게 "중요성"을 정확히 추정해낼 수 있을까를 시도한 것이다.

2.3 링크를 통한 랭킹의 전파 (Propagation of Ranking though Links)
위 의 논의를 기초로, 우리는 페이지랭크에 대한 직관적 기술을 다음과 같이 할 수 있다: 어떤 페이지가 높은 순위(랭크)의 백링크를 많이 가지면 가질수록 그 페이지의 순위(랭크)도 올라간다. 이것은 어떤 페이지가 많은 백링크를 갖는 경우와 몇 개의 높은 순위 백링크를 갖는 경우 모두를 포괄하게 된다.


출처 http://www.web-biz.pe.kr/tech/google_pagerank_citation_ranking.html
출처 : 우 린친구닷컴블로그 - 구글의 핵심 알고리듬인 페이지랭크 (PageRank)를 설명 - http://urin79.com/zb/?mid=blog&search_target=title_content&search_keyword=page+rank&document_srl=550418
by 디케