Page Rank
검색엔진에서의 그래프 사용에 관함
웹과 그래프
- 웹은 웹페이지와 하이퍼링크로 구성된 거대한 방항성 있는 그래프라고 볼 수 있다.
- 웹 페이지는 정점이다.
- 웹페이가 포함하는 하이퍼링크는 해당 웹페이지에서 나가는 간선에 해당한다.
- 단, 웹페이지는 추가적으로 키워드 정보를 포함하고 있다.
페이지 랭크의 출현의 이유
기존의 검색엔진 방식
- 웹을 디렉토리(directory)로 정리함.
- 카테고리와 그 수가 너무 깊어짐.
- 카테고리 구분이 모호하다.
- 키워드에 의존한 검색엔진
- 사용자가 입력한 키워드에 대해, 해당 키워드를 (여러 번) 포함한 웹페이지를 반환.
- 악의적인 웹페이지에 취약.
페이지랭크
따라서, 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾기위한 방법으로 고안됌
페이지 랭크 정의
두가지 관점이 존재한다.
- 투표 관점
- 임의보행 관점
1. 투표관점
- 투표를 통하여 사용자의 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾는다.
- 투표 주체 : 웹페이지
- 투표 방법 : 하이퍼링크를 통하여 투표
- 어떤 웹페이지가 하이퍼링크를 포함할 때, 하이퍼링크에 걸린 웹페이지를 신뢰한다는 것을 의미
- 하이퍼링크에 연결된 웹페이지에 한 표를 투표한다고 생각하자.
해석방법
- 들어오는 간선의 수가 많다 ? -> 신뢰도가 높다는 뜻
문제점
- 들어오는 간선의 수를 세는것이 악용될 소지가 있음.
- 웹페이지를 인위적으로 많이 만들어 들어오는 간선의 수 조작이 가능하다.
해결책
- 약용 효과를 줄이기 위하여, 페이지랭크는 가중 투표를 한다.
- 즉, 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주한다. 반면, 그렇지 않은 웹사이트들의 투표는 덜 중요하게 간주한다. 악용이 없는 경우에도 사용할 수 있는 합리적인 투표 방법이다.
- → 좀 더 믿을만한 웹페이지의 가중치를 더 높게 측정하는 것이다.
투표 관점 간단한 식 정리
- 측정하려는 웹페이지의 관련성 및 신뢰도를 페이지랭크 점수라고 부르자.
- 각 웹페이지는 각각의 나가는 이웃에게 자신의 페이지랭크 점수 만큼의 가중치로 투표를 한다.
- (자신의 페이지랭크 점수)/(나가는 이웃의 수) 만큼의 가중치로 투표한다.
- 각 웹페이지의 페이지랭크 점수는 (이웃들에 의해) 받은 투표의 가중치 합으로 정의된다.
2. 임의 보행 관점
- 페이지랭크는 임의 보행(Random Walk)의 관점에서도 정의할 수 있다.
- 임의 보행을 통해 웹을 서핑하는 웹서퍼를 가정하자.
- 즉, 웹서퍼는 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식으로 웹을 서핑한다.
- 웹서퍼가 𝑡번째 방문한 웹페이지가 웹페이지 $i$일 확률을 $p_i (t)$ 라고 하자.
그러면 𝒑(𝒕)는 길이가 웹페이지 수와 같은 확률분포 벡터가 된다. 그러면 아래 식이 성립한다.
![임의 보행]()
- $p(t)$는 벡터가 되고, v개의 p값이 존재한다.
- $p_i (t)$ 는 $i -> j$ 확률을 $j$에 들어오는 각각에 계산.
- $p_i (t+1)$ 는 $t+1$번 째 방문한 웹페이지가 $j$일 확률
- $p(t) = p(t+1) = p$가 수렴한다는 것은 $t$가 충분히 커서, 각각 $p_i,p_j$가 된다.
페이지 랭크 점수
페이지랭크의 계산 : 반복곱
- 문제점
- 반복곱이 항상 수렴함을 보장 할 수 없음.
- 들어오는 간선은 있지만 나가는 간선이 없는 정점 집합인 스파이더 트랩인 경우
- 반복곱이 합리적인 점수로 수렴하는 것을 보장할 수 없다.
- 들어오는 간선은 있지만 나가는 간선은 없는 막다른 정점(Dead End)에 의한 문제
- 페이지랭크 점수가 0에 수렴할 수 있음
- 반복곱이 항상 수렴함을 보장 할 수 없음.
- 해결책
- 순간이동
![순간이동]()
![순간이동2]()
- 결과
![결과]()
- 가장 투표를 많이받은 정점은 신뢰할 수 있는 정점이 되므로, 신뢰할 수 있는 정점이 가리키는 C라는 정점에 대한 신뢰도도 높아지는 것을 볼 수 있다.
