구글 검색 엔진의 핵심인 페이지 랭크 알고리즘은 1998년 Sergey Brin 과 Lawrence Page의 논문 'The Anatomy of a Large-Scale Hypertextual Web Search Engine'에서 등장했습니다.
논문에서는 design goal을 소개하면서 94년도와 97년도의 웹 검색을 비교합니다. 94년에는 검색 인덱스로 빠르고 정확하게 찾을 수 있는 반면에 97년에는 검색 인덱스로 좋은 결과를 찾을 수 없다고 말합니다. 종종 '쓰레기 값'들이 사용자가 원하는 정보를 가린다고 불편함을 소개하고 있습니다.
In 1994, some people believed that a complete search index would make it possible to find anything easily. However, the Web of 1997 is quite different. Anyone who has used a search engine recently, can readily testify that the completeness of the index is not the only factor in the quality of search results. "Junk results" often wash out any results that a user is interested in.
그리고 페이지랭크 알고리즘을 소개합니다.
페이지 \(A\)가 \(T_1, T_2, \ldots, T_n\)개의 포인트를 가지고 있다고 가정합니다. 쉽게 말해 \(T_1, T_2, \ldots, T_n\) 페이지는 A의 링크를 가지고 있습니다. (즉, 인용(citation)입니다.)
변수 \(d\)는 damping factor라고 하며 0에서 1사이의 값을 가집니다. 논문에서는 0.85를 사용하였습니다.
기호 \(C(A)\)는 페이지 A가 가지고 있는 링크의 수를 의미합니다. 논문에서는 \(C(A)\)라고 표현하지만 글에서는 \(L(A) \)로 표현하겠습니다.
\(A\)의 페이지랭크는 다음과 같이 정의됩니다.
$$PR(A) := (1-d) + d(PR(T_1)/C(T_1) + \cdots + PR(T_n)/C(T_n)).$$
그리고 모든 웹 페이지의 페이지랭크 값은 1이라고 말합니다.
Note that the PageRanks form a probability distribution over web pages, so the sum of all web pages' PageRanks will be one.
하지만 위키피디아에서 정의된 수식이 잘못되었다고 말하여 수정한 수식을 알려줍니다. 이는 아래에서 보도록 하겠습니다.
예를 들어, A, B, C, D 4개의 웹 페이지가 있고 B, C, D 페이지가 A의 링크를 가지고 있다고 가정합니다. 그리고 B, C, D의 페이지랭크를 0.25라고 가정하면 A의 페이지랭크는 다음과 같이 구할 수 있습니다. A의 페이지랭크는 0.75입니다. A를 이용하여 다른 페이지랭크를 계산할 수 있습니다.
$$PR(A) = PR(B) + PR(C) + PR(D).$$
이번에는 조금 더 추가해 봅시다. B가 A와 C의 링크를 가지고, C가 A의 링크를 가지고 D가 A, B, C의 링크를 가진다고 가정합니다.
| 웹 페이지 | 가지는 링크 |
| B | A, C |
| C | A |
| D | A, B, C |
다음과 같이 계산할 수 있습니다.
$$PR(A) = \frac{PR(B)}{2} + \frac{PR(C)}{1} + \frac{PR(D)}{3}.$$
계산을 하면 A의 페이지랭크는 0.125+0.25+0.083으로 0.458입니다. 그리고 상기 식을 기호 \(L\)를 사용하여 다음과 같이 표현할 수 있습니다.
$$PR(A) = \frac{PR(B)}{L(B)} + \frac{PR(C)}{L(C)} + \frac{PR(D)}{L(D)}.$$
일반화하면 다음과 같이 표현할 수 있습니다.
$$PR(u) = \sum_{v\in B_u}\frac{PR(v)}{L(v)}.$$
이와 같이 계산하여 얻은 페이지랭크를 다른 페이지랭크 계산에 사용할 수 있습니다. 반대로 A를 가리키는 B의 페이지랭크는 B를 가리키는 페이지로부터 계산됩니다. 이런 식으로 계속 내려가다 보면 끝이 없을 겁니다. 여기에 조건을 걸어 반복적인 과정을 종료합니다. 페이지랭크 알고리즘은 재귀 알고리즘입니다.
Damping factor
논문에서 Damping factor를 random surfer가 현재 페이지에서 다른 페이지로 이동할 확률이라고 정의합니다.
the d damping factor is the probability at each page the "random surfer" will get bored and request another random page.
따라서 \(d\)가 1이면 계속 페이지를 이동하는 것이고 0이면 현재 페이지에서 이동하지 않는 것을 의미합니다. (논문에서는 0.85를 사용하였습니다.)
\( d\)를 고려하여 정의를 다시 보면 페이지랭크의 총합이 1이 아닌 것을 확인할 수 있습니다. 위키피디아에서는 Brin과 Page가 실수한 정의를 수정하여 제공하고 있습니다. 다음은 수정된 페이지랭크 정의입니다.
$$PR(A) := \frac{1-d}{N} + d\left(\frac{PR(T_1)}{C(T_1)} + \cdots + \frac{PR(T_n)}{C(T_n)}\right).$$
페이지랭크에 대한 내용을 알아보았습니다. 큰 단점으로는 아쉽지만 가장 최신글에 대해서는 검색을 보장하지 못합니다.
위키의 예시를 더 보겠습니다. 페이지랭크 계산 시 링크가 없는 페이지는 모두 균등하게 다른 페이지로 연결되는 것으로 가정합니다. 수식은 다음과 같습니다.
$$PR(p_i) := \frac{1-d}{N} + d\sum_{p_j \in M(p_i)} \frac{PR(p_j)}{L(p_j)},$$
where \(N \)은 전체 페이지 수, \( p_1, p_2, \ldots, p_N \)은 페이지, \(M_{p_i} \)는 \( p_i \)로 링크하는 집합, \(L(p_j)\)는 \(p_j\)의 링크 수를 의미합니다. 일반화했던 모습과 비슷하네요.
\( PR(p_i) \)를 계산하기 위해 해를 다음과 같이 \(R \)로 표현합니다.
$$ R = \begin{bmatrix} PR(P_1) \\ PR(P_2) \\ \vdots \\ PR(P_N) \end{bmatrix}. $$
상기 식을 이용하여 다음과 같이 계산할 수 있습니다.
$$ R = \begin{bmatrix} (1-d/N) \\ (1-d)/N \\ \vdots \\ (1-d)/N \end{bmatrix} + d \begin{bmatrix} PR(p_1)/ L(p_1) & PR(p_1)/L(p_1) & \cdots & PR(p_1)/ L(p_N) \\ PR(p_2)/L(p_1) & PR(p_2)/ L(p_2) & \cdots & PR(p_2)/L(p_N)\\ \vdots & \vdots & \ddots & \vdots \\ PR(p_N)/L( p_1) & PR(p_N)/L(p_2) & \cdots & PR(p_N)/L(p_N) \end{bmatrix} R. $$
\(d\)가 붙어 있는 행렬을 보면 인접성 행렬(adjacency matrix)을 변경한 모습입니다. 선형방정식계를 계산하여 값을 구할 수 있습니다.
다음은 위키의 소스 코드를 조금 수정하여 가져왔습니다.
"""PageRank algorithm with explicit number of iterations.
Returns
-------
ranking of nodes (pages) in the adjacency matrix
"""
import numpy as np
def pagerank(M, num_iterations: int = 100, d: float = 0.85):
"""PageRank: The trillion dollar algorithm.
Parameters
----------
M : numpy array
adjacency matrix where M_i,j represents the link from 'j' to 'i', such that for all 'j'
sum(i, M_i,j) = 1
num_iterations : int, optional
number of iterations, by default 100
d : float, optional
damping factor, by default 0.85
Returns
-------
numpy array
a vector of ranks such that v_i is the i-th rank from [0, 1],
v sums to 1
"""
N = M.shape[1]
v = np.random.rand(N, 1)
v = v / np.linalg.norm(v, 1)
M_hat = (d * M + (1 - d) / N)
for i in range(num_iterations):
v = M_hat @ v
return v
M = np.array([[0, 0, 0, 1],
[1, 0, 0, 0],
[1, 0, 0, 0],
[0, 1, 1, 0],
[0, 0, 1, 1]])
v = pagerank(M, 100, 0.85)
print(v)참고 자료
infolab.stanford.edu/~backrub/google.html
'개발 > 문서 요약' 카테고리의 다른 글
| TF-IDF(Term Frequency - Inverse Document Frequency) (0) | 2021.01.11 |
|---|---|
| 텍스트랭크 알고리즘(TextRank Algorithm) (0) | 2020.12.25 |
| pytube 설치 (0) | 2020.12.02 |
