[22] 페이지랭크(PageRank)

1️⃣ 페이지랭크의 배경

 

웹은 웹페이지와 하이퍼링크로 구성된 거대한 방향성 있는 그래프입니다.

 

웹페이지는 정점에 해당합니다.

웹페이지가 포함하는 하이퍼링크는 해당 웹페이지에서 나가는 간선에 해당합니다.

단, 웹페이지는 추가적으로 키워드 정보를 포함하고 있습니다.

 

첫 번째 시도는 웹을 거대한 디렉터리로 정리하는 것이었습니다.

웹페이지의 수가 증가함에 따라서 카테고리의 수와 깊이도 무한정 커지는 문제가 있습니다.

 

http://www.searchenginehistory.com/

 

두 번째 시도는 웹페이지에 포함된 키워드에 의존한 검색 엔진입니다.

 

사용자가 입력한 키워드에 대해, 해당 키워드를 (여러 번) 포함한 웹페이지를 반환합니다.

 

하지만, 이 방법은 악의적인 웹페이지에 취약하다는 단점이 있습니다.

예를 들어, 성인 사이트에 ‘축구’라는 키워드를 (보이지 않도록) 여러 번 포함하게 되면,

‘축구’를 검색했을 때 해당 성인 사이트가 결과로 나올 수 있습니다.

 

그렇다면 어떻게 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾을 수 있을까요?

 

구글의 창업자인 래리 페이지(Larry Page)와 세르게이 브린(Sergey Brin)은 The PageRank Citation Ranking: Bringing Order to the Web라는 제목의 논문을 통해 PageRank 기법을 이용했습니다.

 

2️⃣ 페이지랭크의 정의

1) 투표

페이지랭크의 핵심 아이디어는 투표입니다.

즉, 투표를 통해 사용자 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾습니다.

웹페이지는 하이퍼링크를 통해 투표를 합니다.

 

사용자 키워드를 포함한 웹페이지들을 고려한다면,

웹페이지 𝑢가 𝑣로의 하이퍼링크를 포함한다면?

𝑢의 작성자가 판단하기에 𝑣가 관련성이 높고 신뢰할 수 있다는 것을 의미합니다.

즉, 𝑢가 𝑣에게 투표했다고 생각할 수 있습니다.

 

즉, 들어오는 간선이 많을수록 신뢰할 수 있다는 뜻입니다.

 

그렇지만 들어오는 간선의 수를 세는 것만으로 충분하지 않습니다.

악용될 소지가 분명히 있기 때문이죠.

웹페이지를 여러 개 만들어서 간선의 수를 부풀릴 수 있습니다.

즉, 관련성과 신뢰도가 높아 보이도록 조작할 수 있습니다

 

이런 악용에 의한 효과를 줄이기 위해, 페이지랭크에서는 가중 투표를 합니다.

즉, 관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주합니다.

반면, 그렇지 않은 웹사이트들의 투표는 덜 중요하게 간주합니다.

악용이 없는 경우에도 사용할 수 있는 합리적인 투표 방법입니다.

 

측정하려는 웹페이지의 관련성 및 신뢰도를 페이지랭크 점수라고 부릅시다.

 

각 웹페이지는 각각의 나가는 이웃에게

 

$$\frac {자신의 페이지랭크 점수} {나가는 이웃의 수}$$

 

만큼의 가중치로 투표를 합니다.

 

아래 그림 예시에서 웹페이지 𝑗는 웹페이지 𝑥, 𝑦, 𝑧에게 각각 가중치 $\frac {𝑟_𝑗} {3}$ 으로 투표를 합니다.

$𝑟_𝑗$는 웹페이지 𝑗의 페이지랭크 점수를 의미합니다.

https://www.edwith.org/bcaitech1

 

각 웹페이지의 페이지랭크 점수는 받은 투표의 가중치 합으로 정의됩니다.

즉, $r_{j}$ = $r_i / 3 + r_k /4$ 로 표현이 가능합니다.

 

따라서 페이지랭크 점수 $r_j$의 정의는 다음과 같습니다.

 

$$r_j = \sum_{i \in N_{in}(j)} \frac {r_i} {d_{out}(i)}$$

 

 

아래 예시에서의 정점 별 페이지랭크 식은 다음과 같습니다.

 

https://www.edwith.org/bcaitech1

 

위 식은 변수가 3개이고, 식이 3개이므로 연립방정식을 통해 풀 수 있습니다.

 

2) 임의 보행 (Random Walk)

임의 보행을 통해 웹을 서핑하는 웹 서퍼를 가정합시다.

즉, 웹서퍼는 현재 웹페이지에 있는 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식으로 웹을 서핑합니다.

 

이 경우 다음과 같은 식이 성립됩니다.

 

• $p_{i}(t)$ : $𝑡$번째 방문한 웹페이지가 웹페이지 $𝑖$일 확률
  
  
• $p_{j}(t+1)$: $t+1$번째 방문한 웹페이지가 웹페이지 $j$일 확률
  
  $p_{j}(t+1)$번째 $j$를 방문하기 위해서는 t번째에는 "$j$에 들어오는 이웃"에 있어야 합니다.
  
  
• $p_{i}(t)$ : t번째에 $j$에 들어오는 이웃이 $i$에 있을 확률
  
  
• $d_{out}(i)$ : ($i$에서 $j$로 이동하는 확률인) $i$의 나가는 연결성
  
  
• $N_{in} (j)$ : $j$에 들어오는 이웃

 

결국, $p_{j}(t+1)$을 구하는 방법은 $j$에 들어오는 이웃 각각에 대해 계산을 해서 더해서 $t+1$번째로 웹페이지 $j$를 방문할 확률을 계산하는 방법입니다.

 

웹서퍼가 이 과정을 무한히 반복하고 나면, 즉 𝑡가 무한히 커지면, 확률 분포는 𝒑(𝒕)는 수렴하게 됩니다( 𝒑(𝒕) = 𝒑(𝒕 + 𝟏) = 𝒑 ). 수렴한 확률 분포 𝒑는 정상 분포(Stationary Distribution)이라고 부릅니다.

 

3) 투표와 임의 보행 관계

투표 관점에서 정의한 페이지 랭크 점수는 임의 보행 관점에서의 정상 분포와 동일합니다.

 

• 투표 관점에서 정의한 페이지랭크 점수 𝒓

 

• 임의 보행 관점에서 정의한 정상 분포 𝒑

 

3️⃣ 페이지랭크의 계산 (반복곱)

1) 반복곱

페이지랭크 점수의 계산에는 반복곱(Power Iteration)을 사용합니다.

 

반복곱은 다음 4단계로 구성됩니다.

---

(1) 각 웹페이지 𝑖의 페이지랭크 점수 $𝒓_{𝒊}^{(0)}$ 를 동일하게 $\frac {1} {웹페이지의 수}$ 로 초기화합니다

 

(2) 아래 식을 이용하여 각 웹페이지의 페이지랭크 점수를 갱신합니다.

(3) 페이지랭크 점수가 수렴 ( $r^{(t)} \approx r^{(t+1)}$ )하였으면 종료합니다. 아닌 경우 (2)로 돌아갑니다.

 

(4) 만약, 충분히 유사해졌을 때 $r^{(t+1)}$을 output으로 반환합니다.

---

예를 들어, 아래와 같은 Graph가 있다고 합니다.

https://www.edwith.org/bcaitech1

각 $r_y, r_a, r_m$의 점수가 1/3, 1/3, 1/3일 때 다음 iteration은 다음과 같습니다.

 

https://www.edwith.org/bcaitech1

 

반복 $0 \approx 1$이 비슷한지, $1 \approx 2$가 비슷한지를 계속 확인했을 때, $j \approx j+1$ 구간에서 아래와 같은 score가 나오게 됩니다.

 

https://www.edwith.org/bcaitech1

 

$r_y = 6/15, r_a = 6/15, r_m = 3/15$가 나오는데 이 값은 $j+1$의 경우에도 같은 값이 나오게 됩니다.

 

https://www.edwith.org/bcaitech1

 

이 경우를 최종 output으로 출력하게 됩니다.

 

2) 수렴하지 않는 경우

반복곱은 항상 수렴하지 않을 수 있습니다.

 

아래 예시의 경우에는 수렴하지 않습니다.

이와 같은 경우는 짝수번의 iteration끼리 모두 동일하고, 홀수번의 iteration끼리 모두 동일한 경우입니다. (번갈아가면서 나옴)

 

https://www.edwith.org/bcaitech1

 

또한 다음 예시의 경우에도 수렴하지 않습니다.

들어오는 간선은 있지만 나가는 간선은 없는 정점 집합인 스파이더 트랩(Spider Trap)에 의한 문제입니다.

 

https://www.edwith.org/bcaitech1

 

또한, 반복곱이 “합리적인” 점수로 수렴하는 것을 보장하지 않는 경우도 있습니다.

들어오는 간선은 있지만 나가는 간선은 없는 막다른 정점(Dead End)에 의한 문제입니다.

 

https://www.edwith.org/bcaitech1

 

4️⃣ 수정된 페이지랭크의 계산

위와 같은 문제 해결을 위해 순간이동(Teleport)을 도입합니다.

 

임의 보행 관점에서, 웹을 서핑하는 웹 서퍼의 행동을 다음과 같이 수정합니다.

 

1. 현재 웹페이지에 하이퍼링크가 없다면, 임의의 웹페이지로 순간이동합니다.
2. 현재 웹페이지에 하이퍼링크가 있다면, 앞면이 나올 확률이 𝛼인 동전을 던집니다.
3. 앞면이라면, 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭합니다.
4. 뒷면이라면, 임의의 웹페이지로 순간이동합니다.

1번과 4번의 임의의 웹페이지는 전체 웹페이지들 중에 하나를 균일 확률로 선택합니다.

순간이동에 의해서 스파이더 트랩이나 막다른 정점에 갇히는 일이 없어졌습니다.

𝛼를 감폭 비율(Damping Factor)이라고 부르며 값으로 보통 0.8 정도를 사용합니다.

 

 

순간이동(Teleport) 도입은 페이지랭크 점수 계산을 다음과 같이 바꿉니다.

---

(1) 각 막다른 정점에서 (자신을 포함) 모든 다른 정점으로 가는 간선을 추가합니다.

 

(2) 아래 수식을 사용하여 반복곱을 수행합니다.

 

 

|𝑉|는 전체 웹페이지의 수를 의미합니다.

파란색 부분은 하이퍼링크를 따라 정점 𝑗에 도착할 확률을 의미합니다.

빨간색 부분은 순간이동을 통해 정점 𝑗에 도착할 확률을 의미합니다.

---

아래 그림은 수정된 페이지랭크 점수 예시입니다.

 

https://www.edwith.org/bcaitech1

 

여기서 숫자(score)는 페이지랭크에 x100을 한 값입니다.

B는 7개의 정점으로부터 투표를 받고 있기 때문에 38.4라는 높은 점수를 갖습니다.

보라색으로 투표하는 정점은 하나도 없지만, score가 0이 아닌 이유는 Teleport를 통해 이 정점에 도달할 확률이 있기 때문입니다.

C는 들어오는 정점이 하나밖에 없지만 점수가 높습니다. 이유는 신뢰가 높은 (점수가 높은) B의 유일한 한 개의 간선이 C를 가리키고 있기 때문입니다.