[그래프] 3. 페이지랭크

페이지랭크의 배경

---

1. 웹과 그래프

웹 : 웹페이지와 하이퍼링크로 구성된 거대한 방향성 있는 그래프

• 웹페이지 = 정점
• 웹페이지가 포함하는 하이퍼링크 = 웹페이지에서 나가는 방향성 있는 간선
• 이때, 웹 페이지는 추가적으로 키워드 정보를 포함 

---

2. 구글 이전의 검색 엔진

방법 1 : 웹을 거대한 디렉토리로 정리하는 것

• 웹페이지 수 증가 → 카테고리 수 & 깊이가 무한히 커짐
• 카테고리 구분이 모호한 경우가 많음 → 저장과 검색에 어려움

방법 2 : 웹페이지에 포함된 키워드에 의존한 검색 엔진 

• 방법 : 사용자가 입력한 키워드에 대해 해당 키워드를 (여러번) 포함한 웹페이지 반환
• 단점 : 악의적인 웹페이지에 취약 (악성 키워드를 보이지 않게 여러 번 포함한다면?)

 

 

---

페이지랭크의 정의

---

1. 투표 관점의 정의

페이지랭크의 핵심 아이디어는 투표.
투표를 통해 키워드와 관련성이 높고 신뢰할 수 있는 웹페이지를 찾음

• 투표의 주체 : 웹페이지
• 웹페이지는 하이퍼링크를 통해 투표함

• 웹페이지 u가 v 로의 하이퍼 링크를 포함하는 경우 ≒ u의 작성자가 판단하기에 v 가 관련성이 높고 신뢰 할 수 있다는 것을 의미
• 이것은 들어오는 간선이 많을수록 신뢰할 수 있다는 뜻 (e.g., 논문 인용)

Q. 들어오는 간선의 수를 세는 것만으로 충분할까? 
A. No, 악용될 소지가 있음
웹페이지를 여러 개 만들어서 간선의 수를 부풀릴 수 있음. 즉, 관련성과 신뢰도가 높아 보이도록 조작할 수 있음

Q. 이런 악용을 어떻게 막을 수 있을까?
A. 악용 효과를 줄이기 위해 페이지 랭크에서는 가중 투표를 사용
관련성이 높고 신뢰할 수 있는 웹사이트의 투표를 더 중요하게 간주. 

Q. 관련성과 신뢰성은 투표를 통해 측정하는 것 아닌가? 가중 투표의 설명대로라면 출력을 입력으로 사용하는 것인가?
A. Yes, 재귀(Recursion), 즉 연립방정식 풀이를 통해 가능함

페이지 랭크 점수

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

• 각 웹페이지는 나가는 이웃에게 자신의 페이지랭크 점수 / 나가는 이웃의 수만큼의 가중치로 투표함
• $r_j$은 웹페이지 j의 페이지랭크 점수를 의미

페이지 랭크 점수의 정의

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

각 웹페이지가 받은 투표의 가중치합을 의미한다.

산식에 따라 위 그림에서 웹페이지 j의 페이랭크 점수 $r_j$는 아래와 같이 계산할 수 있음.
$r_j = \frac{r_i}{3} + \frac{r_k}{4}$

 

---

2. 임의 보행 관점에서의 정의

임의 보행을 통해 웹을 서핑하는 웹 서퍼를 생각해 보았을 때 웹 서퍼는 현재 웹페이지의 하이퍼링크 중 하나를 균일한 확률로 클릭하는 방식으로 웹을 서핑

• $p_i(t)$ : 웹 서퍼가 t번째 방문한 웹페이지가 웹페이지 i일 확률
• $p(t)$ : 길이가 웹페이지 수와 같은 확률분포 벡터 (벡터의 길이가 정점의 수와 같음)

즉, 다음과 같은 식이 성립됨

$p_{j}(t+1) = \sum_{i \in N_{in}(j)} \frac{p_{i}(t)}{d_{out}(i)}$

분자에는 t 번째 j로 들어오는 확률이고, 분모에는 i에서 j로 이동하는 확률이다. 다시 말해 t 시점에 i에서 t+1 시점에 j로 옮겨올 확률을 말한다.

웹 서퍼가 웹서핑을 무한히 반복한다면? 즉 t가 무한히 커진다면?

$p(t) = p(t+1) = p$가 성립하게 됨. 수렴한 p는 정상분포(Stationary Distribution)라고 부름. 따라서 위의 수식을 다음과 같이 바꿀 수 있음.

$p_{i} = \sum_{i \in N_{in}(j)} \frac{p_i}{d_{out}(i)}$

임의 보행 관점의 정상 분포는 페이지 랭크 정의 처음에 다뤘던 투표 관점의 페이지 랭크 점수와 동일하다!

투표 관점에서 겅의한 페이지랭크 점수 r	임의 보행 관점에서 정의한 정상분포 p
$r_j = \sum_{i \in N_{in}(j)} \frac{r_i}{d_{out}(i)}$	$p_j = \sum_{i \in N_{in}(j)} \frac{p_i}{d_{out}(i)}$

 

---

페이지랭크의 계산

---

1. 페이지랭크의 계산 : 반복곱

반복곱(power iteration)은 다음 세 단계로 구성된다.

1. 각 웹페이지 i의 페이지 랭크 점수 $r_{i}^{0}$를 동일하게 $\frac{1}{웹페이지의 수}$로 초기화

2. 아래 식을 이용해 각 웹페이지의 페이지랭크 점수를 갱신
$r_j^{(t+1)} = \sum_{i \in N_{in}(j)} \frac{r_i^{(t)}}{d_{out}(i)}$

3. 페이지 랭크 점수가 수렴하면 종료, 그렇지 않으면 2로 돌아감

 

예제

1. 페이지 랭크 점수 초기화
$r_y = \frac{1}{3}$ (총 페이지가 3개이므로)
$r_a = \frac{1}{3}$
$r_m = \frac{1}{3}$

2. 페이지 랭크 점수 갱신

반복	0	1	2	...	t
$r_y$	$\frac{1}{3}$	$\frac{\frac{1}{3}}{2} + \frac{\frac{1}{3}}{2} = \frac{1}{3}$	$\frac{\frac{1}{3}}{2} + \frac{\frac{3}{6}}{2} = \frac{5}{12}$		$\frac{6}{15}$
$r_a$	$\frac{1}{3}$	$\frac{1}{3} + \frac{\frac{1}{3}}{2} = \frac{3}{6}$	$\frac{\frac{1}{3}}{2} + \frac{1}{6} = \frac{1}{3}$		$\frac{6}{15}$
$r_m$	$\frac{1}{3}$	$\frac{\frac{1}{3}}{2} = \frac{1}{6}$	$\frac{\frac{3}{6}}{2} = \frac{1}{4}$		$\frac{3}{15}$

---

2. 문제점과 해결책

문제점

Q1. 반복곱이 항상 수렴하는 것을 보장할 수 있나?
A. No, 아래와 같은 경우 페이지 랭크 점수는 수렴하지 않음 
 들어오는 간선은 있지만 나가는 간선이 없는 정점 집합인 스파이더 트랙(Spider Trap) 문제

반복	0	1	2	...	t
a	$\frac{1}{3}$	0	0		0
b	$\frac{1}{3}$	$\frac{2}{3}$	$\frac{1}{3}$		-
c	$\frac{1}{3}$	$\frac{1}{3}$	$\frac{2}{3}$		-

 

Q2. 반복곱이 "합리적인"점수로 수렴하는 것을 보장할 수 있나?
A. No, 들어오는 간선은 있지만 나가는 간선은 없는 막다른 정점(Dead End) 문제

반복	0	1	2	3	...	t
a	$\frac{1}{2}$	0	0	0		0
b	$\frac{1}{2}$	$\frac{1}{2}$	0	0		-

b에 들어오는 간선은 있지만 0으로 수렴함

 

해결책

순간이동(Teleport)을 도입

웹 서퍼의 행동을 다음과 같이 수정한다.
1. 현재 웹페이지에 하이퍼링크가 없다면 → 임의의 웹페이지로 순간이동.
2. 현재 웹페이지에 하이퍼링크가 있다면 → 앞면이 나올 확률이 $\alpha$인 동전을 던짐
3. 앞면 → 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭
4. 뒷면 → 임의의 웹페이지로 순간이동

($\alpha$ : 감폭 비율(Damping Factor), 하이퍼링크를 따라갈 확률. 보통 0.8 정도를 사용)

즉, 페이지 랭크 점수 계산을 다음과 같이 바꾸게 된다.

1. 막다른 정점에서 모든 다른 정점으로 가는 간선 추가
2. 아래 수식을 사용한 반복곱 수행
$r_{j} = $$\sum_{i \in N_{in}(j)}(\alpha \frac{r_{i}}{d_{out}(i)})$ + $(1 - \alpha )\frac{1}{|V|}$
- |V| : 전체 웹 페이지의 수를 의미
- 앞쪽 수식 : 하이퍼링크를 따라 정점 j에 도착할 확률
- 뒤쪽 수식 : 순간 이동을 통해 정점 j에 도착할 확률

 

 

---

edwith의 그래프와 추천 시스템 강의를 듣고 정리 한 내용입니다.

https://www.edwith.org/ai211/joinLectures/316864

그래프와 추천 시스템 강좌소개 : edwith