구글의 페이지랭크(PageRank) 알고리즘

---

전체코드 및 결과에 대한 내용은 아래 GitHub 에 PDF 로 올려두었으니 참고해 직접 작성해보면 도움될 듯하다.

• GitHub주소: 
  github.com/pjh5672/Machine_Learning/blob/master/Mathematics_for_Machine_Learning/PageRank.pdf
  

---

< 구현내용 >

선형대수 개념을 바탕으로 구글의 페이지랭크(PageRank) 알고리즘을 구현해볼 수 있다.

 

 

만약 위의 그림과 같이  A, B, C, D, E, F 의 6개 사이트만 존재하는 네트워크망이 있고 각 사이트에서 다른 사이트로 이동할 확률 매트릭스 L 를 아래와 같이 결정하면, (1) 고유값 분해를 통한 방법, (2) Power-iteration 방법으로 각 사이트에 대해 중요도가 높은 순으로 가중치를 재평가할 수 있다. 

 

 

(1) 고유값 분해를 통한 방법

L 매트릭스에 대해 eigenvalue(고유값)와 eigenvector(고유벡터)를 구하고, 첫번째로 큰 고유값에 대응하는 고유벡터를 정규화하여 각 사이트의 중요도를 구한다. 

 

# 각 사이트 지점에서 다른 사이트로 이동할 확률 매트릭스 L
L = np.array([[0,   1/2, 1/3, 0, 0,   0 ],
              [1/3, 0,   0,   0, 1/2, 0 ],
              [1/3, 1/2, 0,   1, 0,   1/2 ],
              [1/3, 0,   1/3, 0, 1/2, 1/2 ],
              [0,   0,   0,   0, 0,   0 ],
              [0,   0,   1/3, 0, 0,   0 ]])

# L에 대한 eigenvalue, eigenvector 계산
eigen_vals, eigen_vecs = la.eig(L)

# eigenvalue 내림차순으로 정렬
order = np.absolute(eigen_vals).argsort()[::-1]

# 정렬순서에 따라 eigenvalue, eigenvector 재정렬
eigen_vals = eigen_vals[order]
eigen_vecs = eigen_vecs[:,order]

# 첫번째 eigenvalue 에 대한 eigenvector 추출 및 비중확인 
r = eigen_vecs[:, 0] 
print(100 * np.real(r / np.sum(r)))

[ 출력값 ]
[16. 5.33333333 40. 25.33333333 0. 13.33333333]

 

(2) Power-iteration 방법

임의 접속자들이 사이트를 무작위로 접속한다고 가정하고, 주어진 경로로 이동할 확률 매트릭스 L 을 통해 재귀적으로 업데이트를 수행하여 각 사이트의 접속자 수가 특정 임계치 이하로 수렴할 때까지 반복하여 사이트별 중요도를 근사한다. 

 

# 100명이 접속한다고 가정했을때, 초기 접속률은 모든 사이트마다 동일하게 구성
r = 100 * np.ones(6) / 6
lastR = r
r = L @ r

i = 0
while la.norm(lastR - r) > 0.01 : # 0.01 임계점까지 수행
    lastR = r
    r = L @ r
    i += 1
    
print(f"{str(i)} iterations to convergence.")
print(r)

[ 출력값 ]
18 iterations to convergence.
[16.00149917 5.33252025 39.99916911 25.3324738 0. 13.33433767]

 

하지만 실제로는 사이트가 굉장히 많기 때문에, 매트릭스 L은 굉장히 크고 희소(Sparse)할 것이며 고유값 분해를 하기에는 계산비용이 많이 든다. 따라서 현실적인 부분을 고려하면 (2)의 방법을 주로 사용할 수 있다.

 

 

또한 위의 그림에서 "G"와 같이 순환하는(cyclic) 사이트가 존재하는 경우, 해당 사이트에 접속하게되면 갇히는 현상이 발생하는데 예외처리로 무작위성을 추가하여 방지할 수 있고, 이를 damping parameter 라고 한다. 이를 추가하여 구현한 코드는 아래와 같다.

 

# 각 사이트 지점에서 다른 사이트로 이동할 확률 매트릭스 L
L = np.array([[0,   1/2, 1/3, 0, 0,   0, 0 ],
               [1/3, 0,   0,   0, 1/2, 0, 0 ],
               [1/3, 1/2, 0,   1, 0,   1/3, 0 ],
               [1/3, 0,   1/3, 0, 1/2, 1/3, 0 ],
               [0,   0,   0,   0, 0,   0, 0 ],
               [0,   0,   1/3, 0, 0,   0, 0 ],
               [0,   0,   0,   0, 0,   1/3, 1 ]])


< Damping parameter 가 없을 경우 > 

# 100명이 접속한다고 가정했을때, 초기 접속률은 모든 사이트마다 동일하게 구성
r = 100 * np.ones(7) / 7
lastR = r
r = L2 @ r
i = 0
while la.norm(lastR - r) > 0.01 : # 0.01 임계점까지 수행
    lastR = r
    r = L2 @ r
    i += 1
print(f"{str(i)} iterations to convergence.")
print(r)

[ 출력값 ] 
131 iterations to convergence.
[ 0.03046998 0.01064323 0.07126612 0.04423198 0. 0.02489342
 99.81849527]

# G 사이트에서 빠져나오지 못하고 머무를 확률 99.8% 비중



< Damping parameter 추가 > 

d = 0.5 # 각 사이트에 랜덤으로 방문할 수 있는 확률
M = d * L2 + (1-d)/7 * np.ones([7, 7]) # 기존 방문확률에 가산

r = 100 * np.ones(7) / 7
lastR = r
r = M @ r
i = 0
while la.norm(lastR - r) > 0.01 :
    lastR = r
    r = M @ r
    i += 1
print(f"{str(i)} iterations to convergence.")
print(r)

[ 출력값 ] 
8 iterations to convergence.
[13.68217054 11.20902965 22.41964343 16.7593433 7.14285714 10.87976354
 17.90719239]

# G 사이트에서 빠져나와 다른 사이트도 균등하게 방문하는 것을 확인

 

마지막으로 (2)의 방법을 함수로 작성하여, 6개의 사이트가 아닌 100개의 사이트를 가진 네트워크망에 대한 각 사이트별 가중치를 평가해보면 4 , 66, 69 번째 사이트가 사용자 접속률이 높게 나온 것을 확인할 수 있다. 

 

def pageRank(linkMatrix, d) :
    n = linkMatrix.shape[0]
    M = d * linkMatrix + (1-d)/n * np.ones([n, n]) 
    r = 100 * np.ones(n) / n
    lastR = r
    r = M @ r
    i = 0
    while la.norm(lastR - r) > 0.01 :
        lastR = r
        r = M @ r
        i += 1
    print(f"{str(i)} iterations to convergence.")
    return r
    
r = pageRank(generate_internet(100), 0.9)
plt.figure(figsize=(7, 4))
plt.bar(arange(r.shape[0]), r)

[ 출력값 ]
36 iterations to convergence.

 

---