구글 검색 엔진 알고리즘

이번 글에서는 구글 검색 엔진 초창기 때부터 사용되어왔고, 최근에도 구글 검색 엔진의 뼈대가 되는 PageRank알고리즘을 다룹니다. 또한, PageRank알고리즘의 개발자인 세르게이 브린의 논문을 많이 참고/인용해 글을 작성하였습니다.

도입

PageRank알고리즘은 웹 상에 있는 페이지들에게 랭크(Rank)를 부여해서 사람들이 관심을 기울이거나 중요도가 높은 페이지를 검색 엔진의 상단에 표시할 수 있게 도와주는 알고리즘입니다.
논문의 초록을 인용하자면,
웹은 다른 평면적인 문서 컬렉션(flat document collections)과는 달리 링크 구조(link structure)나 링크 텍스트(link text) 등의 제공하는 하이퍼 텍스트(hypertext)가 있어 웹 페이지 자체의 텍스트 외에도 여러가지 부가 정보를 얻을 수 있습니다.
그래서 이 알고리즘에서는 모든 웹 페이지를 웹의 링크 구조를 이용해 “중요도” 순으로 순위를 매겼습니다. 이 순위를 페이지 랭크(PageRank)라고 합니다.
그리고 이 알고리즘의 유용성은 google이라는 검색 엔진을 통해 이미 증명이 되어 있습니다.

작동 과정

이 알고리즘은 그래프 이론(Graph Theory)을 기반으로 하며 마르코프 체인(Markov Chain)과 아이디어가 유사합니다.
각각의 웹 페이지는 해당 페이지로부터 뻗어나가는 포워드 링크(forward link, outedge)와 그 페이지로 들어오는 백 링크(back link, inedge)를 갖고 있습니다.
웹 페이지가 얼마나 많은 링크를 갖고 있느냐는 매우 다양합니다. 수 만 개의 링크를 갖는 페이지가 있는데 반해, 몇 개의 링크만 갖는 페이지도 매우 많습니다.
일반적으로 링크가 많이 인용된 페이지는 더 중요하다고 할 수 있습니다. 학술 인용 측면에서도 인용의 횟수를 이용해 노벨상 수상자를 예측하기도 합니다.
그러나 PageRank알고리즘은 인용 횟수를 세는 방식 이상의 정교한 방법을 제안합니다.

한 가지 예를 들어봅시다. 어떤 페이지가 naver 메인 최상단에 링크되었다고 가정합시다.
그 페이지는 백 링크가 하나도 없지만, 많은 사람들이 들어올 수 있기 때문에 상당히 중요한 페이지입니다.
naver 메인 최상단에 링크된 페이지는 다른 별 볼일 없는 몇 개의 페이지에 링크된 페이지보다 더 높은 순위를 가져야 합니다.
PageRank알고리즘은 단순히 인용 횟수를 세는 방식에 비해 이런 경우에서 더 좋은 결과를 냅니다.

링크를 통한 랭킹의 전파(Propagation if Ranking through Links)

위의 글을 토대로 PageRank알고리즘을 직관적으로 간단히 구상해봅시다.
어떤 페이지가 높은 랭크의 백 링크를 많이 가질수록 해당 페이지의 랭크도 올라간다고 할 수 있습니다.
이렇게 함으로써 위에서 들었던 예시의 경우에도 비교적 정확한 결과를 도출해낼 수 있습니다.

PageRank의 정의

어떤 웹 페이지를 u, 해당 페이지가 가리키는 페이지들의 집합을 Fu, u 페이지를 가리키는 페이지의 집합을 Bu라고 합시다.
Nu = |Fu| 라면, 이것은 u 페이지로부터 뻗어나가는 링크의 개수를 의미합니다. 그리고 정규화(normalization)에 사용되는 인수(factor)를 c라고 합시다. (전체 웹페이지의 랭크들의 총 합을 일정하기 위해 정규화 과정을 거칩니다.)
일단 단순하게 랭크 Ru를 정의합시다.

c는 1보다 작아야 합니다. 포워드 링크가 적은 페이지들의 가중치가 시스템 속에서 사라지는 현상을 방지하기 위해서 c < 1을 만족하게 합니다.
c를 조금 더 자세히 정의해봅시다.
c = 1-d로 정의를 하고 d는 damping factor입니다. damping factor란, 마구잡이로 웹서핑을 하는 사람이 그 페이지에 만족을 못하고 다른 페이지로 가는 링크를 클릭할 확률입니다. 보통 d를 0.85로 설정한다고 합니다.