Data Science 7.Page Rank
이번 포스트는 Page Rank에 대해 다룬다.
Page Rank
Graph
- 노드(entities)와 엣지(relation) 로 현실 세계를 표현하는 방법
- 예시 ) 소셜 네트워크 , 도로망, 인터넷 등
- 행렬로 표현할 때 2가지
- Directed Graph (방향이 있다.) : 비대칭 행렬
- Undirected Graph (방향이 없다.) : 대칭 행렬
웹 페이지가 수식억 개인데, 어떤 게 더 중요한 페이지 일까?
해결 방법 : 웹 그래프 구조를 분석해 페이지를 순위 매기자
- 많이 연결된 노드(페이지) = 중요한 페이지
- 연결 패턴으로 중요도 측정
- Link = 투표 : 다른 페이지가 나에게 링크를 건다는 것은 이 페이지가 중요하다고 투표하는 것으로 해석하기
- In-coming link : 나를 가리키는 링크 -> 투표를 받는 것
- Out-going link : 내가 가리키는 링크 -> 투표를 주는 것
Q1. 같은 수의 in-coming Links 라면?
- 더 중요한 페이지에서의 투표를 더 가치있다고 판단
Q2. 모든 In-coming Links가 동일한가?
- 중요한 페이지의 링크 > 덜 중요한 페이지의 링크
- 투표의 가중치가 달라야 한다.
PageRank의 Rank Score 정의 \(r_j = \sum_{i \rightarrow j} d_i \, r_i\)
| 기호 | 의미 |
|---|---|
| $r_j $ | 페이지 j의 중요도 점수 |
| $i \to j $ | j를 가리키는 모든 페이지 i |
| $r_i $ | 페이지 i의 중요도 점수 |
| $d_i $ | 페이지 i의 out-going link 수 |
-
Stochastic Adjacency Matrix M
- M은 각 행의 합이 1인 행 확률 행렬
- 초기 r : 모두 동일하게 시작을 하여
- 수렴할 때까지 반복
Random Surfer Model
- 웹 서핑하는 사람 : 현재 페이지 i
- 링크 중 하나를 무작위로 클릭하여 페이지 j로 이동하고, 또 링크 클릭하는 과정을 무한히 반복
- 즉, 장기적으로 각 페이지에 머물 확률을 볼 수 있다. (r이 수렴하게 된다면)
Stationary Distribution : 더 이상 변하지 않는 안정적인 분포인 상황 \(r^{(t+1)} \approx r^{(t)} \iff \sum_i \left| r_i^{(t+1)} - r_i^{(t)} \right| < \varepsilon\)
- 시간 t : 각 페이지에 서퍼들이 분포해 있는 상황
- 시간 t + 1 : 서퍼들이 이동했는데, 변화가 없는 상황 (Stationary)
수렴된 PageRank 벡터 r = M의 주요 고유벡터 (Principal Eigenvector)
- Power Iteration 방법 : Converged Page Rank 벡터 구하기
Step 1. 모든 노드에 동일한 초기값 \(r_i^{(0)} = \frac{1}{n}\) Step 2. 수렴할 때까지 반복 \(r^{(t+1)} = r^{(t)} \cdot M\)
Page Rank의 2가지 문제점
1. Dead End (막힌 곳)
- out-going link가 없는 곳으로 가서 나가는 곳이 없어질 수 있다.
- Not Stochastic (확률 행렬이 아니다.)
-
중요도가 새어나감
- 해결 방법 : Teleportation
- Dead End에 도달하게 되면 랜덤하게 아무 페이지로 순간 이동
- 점수가 사라지지 않고 계속 수렴하게 됨.
2. Spider Trap (순환 덫)
- 서로만 연결된 상태라면 결국 모든 점수를 흡수
- 해결 방법 : 확률적 Teleportation
- 매 스텝마다 서퍼가 2가지를 선택
- 확률 β: 평소처럼 링크 따라가기
- 확률 (1 - β) : 랜덤 페이지로 순간 이동
- 매 스텝마다 서퍼가 2가지를 선택
최종 Page Rank Equation \(r_j = \sum_{i \rightarrow j} \frac{\beta}{d_i} r_i + \frac{1-\beta}{N}\)
- Google Matrix G \(G = \beta M + (1-\beta) \left[ \frac{1}{N} \right]_{N \times N}\)
PageRank = Google Algorithm
\[r = r \cdot G \quad \text{(Power Iteration으로 계산)}\]- G: Google Matrix = β×M + (1-β)×[1/N]
- Power Iteration: 수렴할 때까지 반복
- Teleportation: Dead End + Spider Trap 모두 해결