PageRank란?
PageRank는 Google 창업자들이자 Stanford 대학원생이던 Larry Page와 Sergey Brin이 개발한 알고리즘으로 검색 결과 페이지들을 랭킹할 때 사용된다. 그 외 SNS 사용자 랭킹 알고리즘으로도 활용할 수 있다.
핵심 아이디어는 다른 웹사이트로에서 많은 참조 링크를 받으면 중요한 웹사이트라는 것이다. 예로, 대부분의 검색 결과에서 위키피디아가 상단에 뜨는 이유는 많은 웹사이트들이 참조하기 때문이다. PageRank는 '중요한 페이지로부터 링크를 받은 페이지는 중요하다'라는 개념을 활용한다. 즉, 중요한 페이지가 주는 링크에 더 높은 점수를 주는 것이다. 결국 링크의 양과 질 모두 고려하는 알고리즘이다.
본 글에서 다루는 PageRank는 Points Distribution Method과 Random Walk Method 기반이다.
PageRank는 페이지의 중요도를 나타내며 0과 1 사이 값이다. 처음에는 각 페이지에 PageRank를 부여하는데, 그 방법은 모두 동일하게 1/N을 주거나 1-hop 차수를 사용하거나 임의의 값이다. PageRank 알고리즘은 어떤 유동적 흐름이 Page들에 분배되는 것이라 생각하면 쉽다. 이 흐름이 Page에 얼만큼 분배되느냐가 PageRank이다. 즉, 물을 어떤 복잡한 구조의 파이프에 넣었는데 물이 가장 많이 흐르는 부분이 파이프의 핵심 부분으로 볼 수 있다. 모든 페이지의 PageRank 값의 총합은 1이다.
Points of Distribution 방식
Basic PageRank(Simplified PageRank)
지금부터 살펴볼 것은 실제 PageRank의 이해를 도울 기초 PageRank이다. 기초 PageRank는 간소화된 PageRank이다.
위 수식은 페이지 u의 PageRank를 계산하며 u를 가리키는 이웃 노드들에 의해 결정된다. 정확히는, u를 가리키는 이웃 노드들의 각 PR 값을 각각의 outgoing edge 수로 나눈 뒤 합치는 것이다. 이는 한 영향력 있는 페이지 A가 다른 페이지를 가리킬 때 A의 온전한 영향력이 전달되는 것이 아니라 가리키는 링크가 많을수록 약화되는 것이다. 예로, 트위터에서 버락 오바마가 50만명을 팔로잉하는데 오바마의 PR 값을 이 사람들에게 온전히 전달할 경우, 중요하지 않은 사용자까지 고평가되는 걸 방지한다.
위 수식으로 그래프를 순회(Iteration)하는데 다음 단계들로 구성된다.
Iteration 0 단계: 모든 페이지의 PageRank를 1/(총 페이지 수)로 초기화한다.
Iteration 1 단계: 페이지 u의 PageRank는 incoming 페이지(v)들의 이전 단계 PageRank를 페이지 별 outgoing 링크 수로 각각 나눈 값의 총합이다.
PageRank가 끝나는 기준은 "수렴"인데 추후 다시 설명하겠다.
하지만 위 예시와 달리 모든 페이지의 PR 합이 1이 되지 못하는 경우도 있다. 아래 예시가 그렇다.
위에 언급 iteration에 따르면 4개의 페이지는 각각 1/4로 초기화 되고 incoming edge가 존재하는 페이지는 A 밖에 없으므로 A의 PR이 1/4+1/4+1/4로 계산되어 3/4가 될 것이다. 그런데 B, C와 D는 가리키는 페이지가 없기 때문에 PR이 0이 될 것이다. 결국 모든 페이지의 PR 합이 1이 안된다. 이것이 Basic PageRank를 사용하지 않는 이유이다. 이제 실제 PageRank를 살펴보겠다.
Real PageRank(Old PageRank)
이제 진짜 PageRank를 살펴보겠다. 예전에 구글에서 사용하던 검색 엔진 알고리즘이다. 지금 구글에서 쓰이는 PageRank는 많은 것이 바뀌었고 사내 기밀이다. 그래서 아무도 모른다. 지금 설명하는 건 우리가 알고 있는 PageRank로 아직까지 논문에서 활용되는 PageRank의 형태이다.
많은 것이 달라보이지만 Basic PageRank에 근간하며 몇 가지 조정만 했을 뿐이다. 수식 상 d는 damping factor, N은 총 페이지 개수이고 그 외는 위 수식에서 변수명만 바뀌었을 뿐이다. 그래프 알고리즘을 사용해 본 사람이라면 한번쯤 마주했을 사이클(cycle) 또는 무한 루프가 있다. 이 또한 PageRank에서 반드시 고려해야 할 사안이다. 그래서 PageRank는 damping factor라는 것을 도입해 언급된 문제들을 방지했다. d, 즉 Damping factor,는 상상속의 surfer(잉여 인간)가 링크 타고 웹페이지 간 이동해나갈 확률을 의미한다. d는 일반적으로 0.85로 설정하며, 이는 성능 상 가장 무난하다고 한다.
각 알고리즘 단계마다 노드의 PageRank 값을 이웃들에게 d 비율만큼 보낸다. 그리고 모든 페이지의 PageRank에 (1-d)/N씩 더한다. (1-d)/N를 더하는 이유는 모든 페이지들의 PR 합이 1이 되기 위함이다. 이는 incoming link가 하나도 없는 페이지도 매 단계마다 (1-d)/N만큼의 PageRank를 얻음을 말한다. 결국 페이지의 PageRank는 이웃들의 PageRank로 결정되며 d는 감쇄 역할을 한다.
Sink(Dangling Nodes/Pages)
Outgoing link가 없는 페이지를 Sink(싱크) 또는 Dangling Node라고 부른다. 이는 surfer가 하이퍼링크를 따라 웹페이지들을 이동하다가 결국 싱크에서 멈추게 되는 현상과 동일하다.
그래프 내 싱크가 존재할 경우 다른 페이지들의 PageRank가 싱크에서 막혀 쌓이기만 하고 분배가 되지 못한다. 결국 모든 페이지의 PageRank는 0 또는 1 밖에 없는 사단이 난다. 싱크 페이지들의 점수도 다른 페이지들에 할당되어져야 하는데 이에 대한 해결책은 2 가지 있다.
1) 싱크에서 다른 모든 페이지로 outgoing 간선을 추가하거나
2) 싱크의 페이지랭크를 다른 모든 페이지들에 동등하게 분배하거나
Sink 문제를 해결하려면 iteration마다 싱크 처리 기능을 구현해야 한다. 그 알고리즘은 아래와 같다.
1) 각 싱크마다, 이전의 싱크 rank를 전체 페이지 수로 나눈 값으로 계산하고 모든 싱크들의 재계산된 랭크를 합산한다.
2) 그래프 내 모든 페이지의 PageRank가 재계산된 싱크들의 rank 합계가 되도록 설정.
3) Random Walk 방식 PageRank는 임의의 정점에서 다시 출발한다.
Convergence
PageRank는 iteration마다 변하기 때문에 한 번의 iteration만으로 페이지가 얼마나 중요한지 가늠하기 어렵다. PageRank는 여러 iteration을 거쳐 갱신되면서 각 페이지마다 이전과 현재 PR 값의 차이가 margin of error(설정 가능, 0.01) 보다 작은 경우나 K-Means처럼 100번의 iteration을 수행한 경우 멈춘다.
댓글