> For the complete documentation index, see [llms.txt](https://riverallzero.gitbook.io/summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://riverallzero.gitbook.io/summary/data-mining/page-rank.md).
# Page Rank
### 1. Matrix Formulation
$$\tilde{A}=D^{-1}A$$
* $$A$$: adjacency matrix
* $$D$$: outdegree matrix(diagonal)
* $$D^{-1}$$: $$\frac{1}{outdegree}$$ matrix(diagonal)
#### **example**
1. calculate matrix
* $$A = \begin{bmatrix} 1 & 1 & 0 \ 1 & 0 & 1 \ 0 & 1 & 0 \end{bmatrix}, D = \begin{bmatrix} 2 & 0 & 0 \ 0 & 2 & 0 \ 0 & 0 & 1 \end{bmatrix}, D^{-1} = \begin{bmatrix} 0.5 & 0 & 0 \ 0 & 0.5 & 0 \ 0 & 0 & 1 \end{bmatrix}$$
* $$\tilde{A} = \begin{bmatrix} 0.5 & 0 & 0 \ 0 & 0.5 & 0 \ 0 & 0 & 1 \end{bmatrix} @ \begin{bmatrix} 1 & 1 & 0 \ 1 & 0 & 1 \ 0 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 0.5 & 0.5 & 0 \ 0.5 & 0 & 0.5 \ 0 & 1 & 0 \end{bmatrix}$$
* $$\tilde{A}^T = \begin{bmatrix} 0.5 & 0.5 & 0 \ 0.5 & 0 & 1 \ 0 & 0.5 & 0 \end{bmatrix}$$
2. power iteration
1. init $$r^{(0)} = \begin{bmatrix} \frac{1}{3} \ \frac{1}{3} \ \frac{1}{3} \end{bmatrix}$$
2. $$r^{(1)}=\tilde{A}^Tr^{(0)} = \begin{bmatrix} 0.5 & 0.5 & 0 \ 0.5 & 0 & 1 \ 0 & 0.5 & 0 \end{bmatrix} @ \begin{bmatrix} \frac{1}{3} \ \frac{1}{3} \ \frac{1}{3} \end{bmatrix} = \begin{bmatrix} \frac{1}{3} \ \frac{1}{2} \ \frac{1}{6} \end{bmatrix}$$
3. 수렴할때까지 반복
4. $$r=\begin{bmatrix} \frac{2}{5} \ \frac{2}{5} \ \frac{1}{5} \end{bmatrix}$$
### 2. Random Walk Interpretation
* 어떤 노드에서 다른 노드로 이동할때 random하게 이동하는 것
* time $$t$$에 node $$i$$로 도착할 확률을 $$P^{(t)}\_i$$로 나타내며 값이 클수록 자주 방문된 노드임을 의미
* $$p^{(t+1)}=\tilde{A}p^{(t)}$$로 표현 가능, $$t \rightarrow \infty$$이면 $$p^{(t+1)} \approx p^{(t)}$$해져서 $$p=\tilde{A}p$$ 즉, $$r=\tilde{A}r$$과 유사해짐
#### **conditions**
$$t=0$$ 시점의 초기 확률 분포가 무엇이든지:
* random node에서 다른 어느 node로 이동 가능해야함
* 이동하는 패턴이 주기적으로 반복되면 안됨
* stationary distribution이 고유해야함($$p^{(t)} \approx p^{(t+1)} \approx p$$)
### 3. Google Formulation
* 기존 방식은 데이터에서 **deadend**(이동할 노드가 없는 경우 → column stochastic하지 않음)나 **spider trap**(갇히게 됨)이 발생하면 rank 계산에 있어 문제가 발생함
* solution:
* deadend: $$\frac{1}{n}$$ 로 값을 초기화해 해결함
* spider trap: teleport를 이용해 random node로 jump하여 벗어남
$$r=Gr$$
* $$G=\beta\tilde{B}^T+(1-\beta)\[\frac{1}{n}]\_{n\times n}$$
* $$\tilde{B}^T$$: $$\tilde{A}^T$$에서 column-stochastic(열의 합=1)하지 않은 열에 대해 각 값을 $$\frac{1}{n}$$ 으로 초기화
* $$\beta \in \[0.8, 0.9], default=0.85$$
* $$r\_j=\beta\sum\_{i\in N\_j}\frac{r\_i}{d\_i}+(1-\beta)\frac{1}{n}$$
* random walk: $$\beta\sum\_{i\in N\_j}\frac{r\_i}{d\_i}$$
* teleport: $$(1-\beta)\frac{1}{n}$$
### 4. Top Specific Page Rank
* teleport로 random work할때 query의 topic과 관련된 page들의 집합 $$S$$안에서만 골라 이동
$$r\_s=\beta\tilde{B}^Tr\_s+(1-\beta)q\_s$$
* random walk: $$\beta\tilde{B}^Tr\_s$$
* topic specific teleport: $$(1-\beta)q\_s$$
* $$q\_s$$: $$S$$안에 있는 요소인 경우 $$\frac{1}{|S|}$$, 그외는 $$0$$
#### **example**
$$S={1,2}, \beta=0.8$$
1. calculate matrix
* $$A = \begin{bmatrix} 0 & 1 & 1 & 0 \ 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{bmatrix}, D = \begin{bmatrix} 2 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 \end{bmatrix}, D^{-1} = \begin{bmatrix} 0.5 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 \end{bmatrix}$$
* $$\tilde{A}=\begin{bmatrix} 0.5 & 0 & 0 & 0 \ 0 & 1 & 0 & 0 \ 0 & 0 & 1 & 0 \ 0 & 0 & 0 & 1 \end{bmatrix} @ \begin{bmatrix} 0 & 1 & 1 & 0 \ 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 0 & 0.5 & 0.5 & 0 \ 1 & 0 & 0 & 0 \ 0 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{bmatrix}$$
* $$\tilde{A}^T=\begin{bmatrix} 0 & 1 & 0 & 0 \ 0.5 & 0 & 0 & 0 \ 0.5 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{bmatrix} = \text{column stochastic} = \tilde{B}^T$$
* $$q\_s=\begin{bmatrix} 0.5 \ 0.5 \ 0 \ 0 \end{bmatrix}$$
2. power iteration
1. init $$r^{(0)}\_s = \begin{bmatrix} 0.25 \ 0.25 \ 0.25 \ 0.25 \end{bmatrix}$$
2. $$r^{(1)}\_s = 0.8 \times \begin{bmatrix} 0 & 1 & 0 & 0 \ 0.5 & 0 & 0 & 0 \ 0.5 & 0 & 0 & 1 \ 0 & 0 & 1 & 0 \end{bmatrix} @ \begin{bmatrix} 0.25 \ 0.25 \ 0.25 \ 0.25 \end{bmatrix}+0.2 \times \begin{bmatrix} 0.5 \ 0.5 \ 0 \ 0 \end{bmatrix}=\begin{bmatrix} 0.3 \ 0.2 \ 0.3 \ 0.2 \end{bmatrix}$$
3. 수렴할때까지 반복
4. $$r=\begin{bmatrix} 0.26 & 0.20 & 0.29 & 0.23 \end{bmatrix}$$
### Algorithm
지금까지의 Page Rank 방식에서 발생하는 $$G$$가 fully dense한 문제점에 대해 아래 2가지 해결책을 제시
#### 1. Sparse Matrix Formulation
* $$\tilde{D}^T$$: deadend를 해결하기 위해 $$\frac{1}{n}$$ 로 값을 설정한 부분을 따로 정의
* $$\tilde{B}^T = \tilde{A}^T + \tilde{D}^T$$
* $$\tilde{A}^T = \begin{bmatrix} 0.5 & 0.5 & 0 \ 0.5 & 0 & 0 \ 0 & 0.5 & 0 \end{bmatrix}$$
* $$\tilde{D}^T = \begin{bmatrix} 0 & 0 & \frac{1}{3} \ 0 & 0 & \frac{1}{3} \ 0 & 0 & \frac{1}{3} \end{bmatrix}$$
* $$G=\beta\tilde{B}^T+(1-\beta)\[\frac{1}{n}]*{nxn} \rightarrow \beta\tilde{A}^T+\beta\tilde{D}^T+(1-\beta)\[\frac{1}{n}]*{nxn}$$
* 하지만 여전히 $$\tilde{A}^T$$는 sparse함(real world에서 90\~99% sparse) → CSR(Compressed Sparse Row)와 같은 sparse matrix format을 사용
* 또 deadend가 많이 발생하면 $$\tilde{D}^T$$도 sparse함 → injection leaked score를 사용
* $$r^{(t+1)}=\beta\tilde{A}^Tr^{(t)}+(1-S)\[\frac{1}{n}]\_{n\times 1}$$
* $$S=sum(\beta\tilde{A}^Tr^{(t)})$$, $$1-S$$: leaked score의 총합
#### 2. Block Based Update Algorithm
graph(data)에 edge가 너무 많아서 memory에 올라가지 못하는 경우 adjacency matrix인 $$\tilde{A}$$를 source node, degree, destination nodes를 포함한 list로 표현
| source node | degree | destination nodes |
| :---------: | :----: | :---------------: |
| 0 | 4 | 0, 1, 3, 5 |
| 1 | 2 | 0, 5 |
| 2 | 2 | 3, 4 |
**o Basic**
하나의 source node씩 읽으면서 PageRank 값을 업데이트
1. 디스크에서 $$r^{old}$$ (이전 PageRank 값)과 $$\tilde{A}$$ (인접 행렬)를 읽음
2. 새로운 PageRank 값 $$r^{new}$$를 계산하여 디스크에 저장
$$cost=2|r|+|\tilde{A}|$$
**o Block Based**
$$r^{new}$$를 $$K$$개의 블록으로 나누고 각 블록을 읽으면서 수행
1. $$r^{old}$$와 $$\tilde{A}$$를 $$K$$번 스캔
2. 각 블록을 디스크에 저장하여 새로운 PageRank 값 $$r^{new}$$를 계산
$$cost=K(|\tilde{A}|+|r|)+|r|$$
**o Block Stripe Based**
$$\tilde{A}$$를 stripe 단위로 나누고, 각 stripe는 $$r^{new}$$의 블록에 대응되는 destination node만 포함해 수행, 한 번 읽은 파일을 다시 읽지 않아도 됨
1. $$r^{new}$$의 각 블록을 디스크에 저장하고, $$r^{old}$$를 $$K$$번 스캔
2. $$\tilde{A}$$의 stripe를 읽어 $$r^{new}$$를 업데이트, stripe의 크기는 $$(1+\epsilon)|\tilde{A}|$$이며, $$\epsilon$$은 $$K$$보다 작은 값
$$cost=(1+\epsilon)|\tilde{A}|+(1+K)|r|$$
