Page Ranks and Random Walks in Graph (3rd page 계산 추가)

WWW를 그래프 G=(V, E)를 표현해보자

웹 페이지를 정점(vertex)으로, 하이퍼링크를 간선(edge)으로 표현한다.

만약 페이지 v1이 페이지 v2에 대한 하이퍼링크를 가지고 있다면 E는 엣지 (v1, v2)를 가지고 있다.

만약 특정 페이지 v에 outgoing 링크가 없다면, E에 self-loop (v, v) - 자기 자신으로 가는 간선을 추가한다.

 

랜덤 서핑 알고리즘

1. 초기 페이지 u에서 시작하는데, 우리가 방문하고 있는 페이지이다.

2. 동전을 던져 앞면이 나오는 확률을 alpha라 한다.

3. 만약 앞면이 나왔다면, u의 랜덤한 아웃링크를 따라서 다음 페이지로 이동한다.

4. 만약 뒷면이 나왔다면, 그래프의 임의의 페이지로 이동한다. -> 이걸 리셋이라고 한다.

5. step 1에서부터 다시 반복한다.

 

Page Rank

특정 정점(vertex)의 page rank는 t가 무한으로 갈 때 해당 페이지가 방문될 확률을 뜻한다.

그럼 우리가 생각해볼 것은,

1. 모든 정점에 대해, t가 무한대로 갔을 때의 확률은 수렴할 것인가?

2. 수렴 속도는 얼마나 빠른가?

3. 초기 페이지 선택이 page rank에 영향을 미치는가?

4. page rank를 어떻게 계산할 수 있는가?

 

그럼 예시를 들어 보겠다.

첫 페이지는 v1로 정해졌고, alpha는 4/5이다. 이때 두 번째 페이지가 v3일 확률은?

 

일단 동전이 앞면이 나온 경우를 생각해보자.

그럼 v1에 연결된 아웃링크로 연결될 것인데, 그건 v3와 v5가 있다.

그럼 앞면이 나왔을 때 v3로 갈 확률은 4/5 * 1/2 로 구하면 된다.

 

이제 동전이 뒷면이 나온 경우를 생각해보자.

그럼 그냥 v1~v5 다섯 가지 노드 중 랜덤하게 하나의 노드가 선택될 것이다.

그럼 뒷면이 나왔을 때 v3로 갈 확률은 1/5 * 1/5 로 구하면 된다.

 

그럼 결과는, 4/5 * 1/2 + 1/5 * 1/5를 계산한 11/25가 된다.

 

오잉 근데 3rd page 계산하는 건 이해 안 감

 

Random Walks

만약,

벡터 P의 각 요소가 0과 1 사이의 값이고, 모든 P의 합이 1이라면? n*1 벡터인 P는 확률벡터이다.

만약 저 n*1 vec가 n개 모인 n*n 행렬이 있다면 그것은 확률 행렬이다.

 

모든 확률 행렬 M은 random walk를 정의한다.

정점들로 이루어진 directed 그래프인 G_markov를 만들자. M의 원소 중 모든 0이 아닌 원소의 값을 엣지에 넣는데,

만약 0이 아닌 원소가 G_markov의 M[j, i]라면 edge (vi, vj)에 그 값을 대입한다.

임의의 정점을 처음 멈추는 지점으로 선택하고,

유도적으로, t번째 멈추는 것이 vi라고 가정하고, t+1번째로 vj에 갈 때, M[j, i]의 확률을 기반으로 움직인다.

이 과정을 마코프 체인이라고도 부른다.

 

이것은 만약 Gmarkov의 노드들이  서로 도달 가능하면 irreducible(줄일 수 없다?)하고,

만약 다음이 사실이라면 [Gmarkov의 모든 정점은 충분히 큰 t0에 대해 모든 t0보다 큰 t에서 방문될 확률이 0이 아님] 비주기적이다. 

 

만약 M이 irreducible하고 aperiodic한 확률 행렬이면, 다음의 것들은 사실이다.

P=MP를 만족시키는 유일한 확률 벡터 P가 있고,

t가 무한으로 가면, vi가 t번째 방문한 노드일 확률은 정지 확률 벡터 P의 i번째 성분과 같다.

 

Random surfing process = random walk의 일종

vi가 현재 정지 지점으로 주어졌을 때, 우린 vj의 확률을 본다.

만약 vi에서 vj로 연결이 없다면 (1-alpha)/n이고,

다른 경우에는 (1-alpha)/n + alpha/outdeg(vi) 이다.

 

P(t) = [p(v1, t) p(v2, t) .. p(vn, t)]' 일 때,

P(t+1) = M*P(t)이며, 만약 P(t+1)=P(t)라면 P(t)는 P=MP에서의 유일한 P를 의미하고, t가 무한으로 갈 때 P(t)는 P로 수렴한다.

 

최종적으로, 우리는 얼마나 빠르게 P(t)가 P에 수렴하는지 분석할 것이다.

우리의 분석은 또한 P(t)의 수렴에 대한 또다른 증명으로 사용될 것이다.

 

Power Method

P(t)를 계산하는 다음의 알고리즘을 생각해보자. 

이제 이 알고리즘이 빠르게 수렴하는 것을 보일 것이다.

ri를 vi의 page rank라고 하자. 그럼 Page rank 계산의 정확도를 아래와 같이 측정할 수 있다.

그럼 이런 식을 정의할 수 있고, 이는 Err(t)가 alpha^t * Err(0)보다 작거나 같다는 것을 의미한다.

이건 t = O(log(1/epsilon)) 이후 Err(t)는 충분히 작은 오차인 epsilon에 도달다는 것을 보인다.