페이지랭크의 배경
웹과 그래프
웹 : 웹페이지(Vertex)와 하이퍼링크(Edge)로 구성된 거대한 directed graph 입니다.
구글 이전의 검색 엔진
- 웹을 거대한 디렉토리로 정리
- 웹페이지의 수가 증가함에 따라 카테고리의 수와 깊이도 무한정 커지는 문제
- 키워드에 의존한 검색 엔진
- 사용자가 입력한 키워드에 대해, 해당 키워드를 포함한 웹페이지를 반환
- 악의적인 웹페이지에 취약하다는 단점
사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 만드는 알고리즘 필요
페이지랭크의 정의
1. 투표 관점
- 각 페이지의 중요도는 해당 웹페이지로의 하이퍼링크가 많을수록 높다고 할 수 있음
- 하지만 들어오는 간선이 많을 수록 신뢰할 수 있다는 뜻은 아님
위의 그림과 같이 인위적으로 만들어 악용될 소지가 있음 -> 가중 투표로 해결
또 하나의 문제점은 위의 식을 통해 페이지랭크가 수렴하지 않는 경우가 발생
위의 문제해결을 위해 임의 보행 관점 도입
2. 임의 보행 관점
임의 보행 관점에서는 웹서퍼의 행동을 다음과 같이 정의
- 현재 윂페이지에 하이퍼 링크가 없다면, 임의의 웹페이지로 순간이동 합니다.
- 현재 윂페이지에 하이퍼링크가 있다면, 앞면이 나올 확률이 a인 동전을 던집니다.
- 앞면이라면, 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭합니다.
- 뒷면이라면, 임의의 웹페이지로 순간이동합니다.
a를 Damping Factor라고 부르며 값은 보통 0.8로 설정
투표의 관점과 임의 보행의 관점을 모두 고려하면 아래와 같은 식이 됩니다.
위 식은 Diagonalization 과정을 거쳐 Markov chain을 통해 값을 구할 수 있음
