더북(TheBook)

랜덤 서퍼가 두 번 움직여 페이지 i에서 페이지 j로 이동할 확률은 얼마일까? 먼저 중간 페이지 k로 이동하므로 모든 k에 대해 i에서 k로 이동하고 나서 k에서 j로 이동할 확률을 구해 모두 더한다. 예를 들어 두 번 움직여 1에서 2로 이동할 확률은, 1에서 0으로 이동하고 난 후 2로 이동(이제부터 간단히 ‘1-0-2 이동’이라고 설명하겠다)할 확률(0.02 × 0.02), 1-1-2 이동 확률(0.02 × 0.38), 1-2-2 이동 확률(0.38 × 0.02), 1-3-2 이동 확률(0.38 × 0.02), 1-4-2 이동 확률(0.20 × 0.47)을 모두 더한 값 0.1172이다. 다른 페이지로 이동하는 것도 동일한 과정으로 계산할 수 있다. 이렇게 곱해서 더하는 계산은 이미 앞에서 보았다. 행렬 A와 행렬 B를 곱해 행렬 C를 계산할 때, C의 ij열 요소는 A의 i행과 B의 j열의 스칼라곱이다. 즉 p[][] 행렬에 자기 자신을 곱하면 랜덤 서퍼가 두 번 움직여 i에서 j로 이동할 확률을 가진 행렬이 된다. 우리 모델에서 두 번 이동해 움직일 확률 행렬을 차분히 살펴보면 랜덤 서퍼의 행동을 더 많이 이해할 수 있다. 예를 들어 제곱 행렬에서 2행 0열 요소의 값이 가장 큰데, 페이지 2에는 페이지 3으로 가는 링크가 하나만 있고, 페이지 3에는 페이지 0으로 가는 링크 하나만 있음을 잘 반영한다. 따라서 페이지 2에서 시작한 랜덤 서퍼가 두 번 움직여 페이지 0에 도착할 확률이 가장 크다. 두 번 움직이는 다른 경우는 가지 수는 많고 확률은 낮다. 여기에서 주의할 점은 추정 확률을 계산하기 위해 아주 많이 반복해 시뮬레이션하는 randomsurfer.py와 달리, 이 값들은 (파이썬의 실수 정밀도 한계 내에서) 확률을 곱해 정확히 계산된 값이라는 점이다.

제곱 기법 제곱 행렬에 p[][]를 한 번 더 곱하면 세 번 움직여 이동할 확률, 여기에 한 번 더 p[][]를 곱하면 네 번 움직여 이동할 확률을 계산할 수 있다. 그러나 행렬의 곱셈은 비싼 연산이며, 실제 우리가 알고자 하는 것은 벡터-행렬 계산이다. 예를 들어 랜덤 서퍼가 페이지 0에서 시작하는 경우를 생각해보자. 각 페이지로 이동할 확률은 다음 벡터와 같다.

[1.0 0.0 0.0 0.0 0.0]

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.