단지 좋은 논문으로 그치지 않고 실세계에서 널리 영향을 끼치게 된 유명한 알고리즘들은, 대개 practicality와 simplicity라는 두 가지 요건을 모두 만족한다.
우선, 높은 성능이 뒷받침되지 않는다면 애초에 쓰이질 않게 된다는 점에서, practicality는 인기 알고리즘이 되기 위한 필요조건이 된다.
하지만 높은 성능만이 전부는 아니다. 이해하기 어렵고 구현이 복잡한 알고리즘은, 좋은 저널이나 학회에는 실릴 수 있을지 몰라도, 어지간히 성능이 좋지 않은 이상 해당 분야의 연구자들에게조차 외면당하게 된다.

21세기 이후 세상에 가장 큰 영향을 끼친 구글의 PageRank 알고리즘 또한 위의 두 가지 요건을 동시에 만족시킨 좋은 알고리즘이다.
practicality에 관해서는 더 이상 말하면 입이 아플 정도이고,
simplicity 또한 훌륭하여, 최소한의 프로그래밍 관련 지식과 관심을 가진 사람들이라면 이 알고리즘이 어떻게 랭크를 매기는지 남에게 말로 설명할 수 있을 정도로 그 원리가 다음과 같이 널리 알려져있다:

"incoming link, 즉 다른 페이지들로부터 링크가 많이 걸려 있는 페이지는 랭크가 높고,
높은 랭크를 가진 페이지에게 링크된 페이지들 또한 덩달아 랭크가 높아지고,
outgoing link가 많은 페이지는 랭크를 결정하는 데에 거의 영향을 못 미치고..."

위와 같은 설명은 우선 이해하기 쉽고, "구글 검색 엔진이 왜 잘 동작하는가" 라는 이유 또한 잘 나타나 있으며, 실제 PageRank 알고리즘의 랭크를 구하는 아래의 수식 역시, 위 설명과 정확히 일치한다:

[TeX] Rank(p) = \sum_{p_j\rightarrow p} \frac{Rank(p_j)}{Num(p_j\rightarrow .)} [/TeX]

그러나 사실 위 설명은 단지 PageRank의 '수식' 또는 '현상'을 기술한 것일 뿐, '원리'(즉 "어떻게 해서 위와 같은 수식이 나왔는가")를 이야기한 것은 아니다.
PageRank 알고리즘의 핵심 아이디어는 다음과 같다:

"임의의 페이지에서 랜덤 서핑(현재 페이지의 링크 중 아무거나 랜덤하게 클릭, 다음으로 나타난 페이지에서 다시 아무 링크나 랜덤하게 클릭, ...)을 시작하여 마침내 목적지 페이지에 도달할 확률로 점수를 매긴다"

예를 들어 이 세상에 총 N개의 웹 페이지들(p1, p2, ..., pN)이 있다고 했을 때,
이 게시물의 랭크는
p1에서 랜덤 서핑을 시작하여 이 게시물에 도달할 확률
+ p2에서 랜덤 서핑을 시작하여 이 게시물에 도달할 확률
+ ....
+ pN에서 랜덤 서핑을 시작하여 이 게시물에 도달할 확률
이 되는 것이다.

...

차라리 안들으니만 못한 이야기라고 할까,
위 원리를 보면, "아하, 그렇구나!" 하고 뭔가 clear해지는 기분이 드는 것이 아니라 오히려 의문들만 더 샘솟게 된다.
도대체 어떻게! 저 아이디어에서 널리 알려진 설명(incoming, outgoing 어쩌고 하는..)이 유도가 되는 것이며,
웹 페이지 하나의 랭크를 매기기 위해 랜덤 서핑을, 그것도 이 세상의 모든 웹 페이지들에서 일일히 한 번씩 다 해본다니, 참으로 거짓말같은 이야기이지 않는가...

우선 두 번째 의문에 대한 답부터 말하자면, 당연히 랜덤 서핑을 실제로 하지는 않는다. 실제로 랜덤 서핑을 해서 얻은 결과와 "똑같은" 결과를 얻을 수 있는 공식이 있기 때문이다.
(그 공식이 바로, PageRank 알고리즘에서 랭크를 구하는 수식 - 위에 써 놓은 - 인 것이다!)

조금 더 상세한 알고리즘은 다음과 같다:
(이 세상에 총 N개의 웹 페이지들 p1, p2, ..., pN이 있다고 가정했을 때)

1. 페이지 pi의 랭크를 R(pi) 라고 하자.
R(p1), R(p2), ..., R(pN)을 모두 0이 아닌 임의의 값으로 초기화한다.

2. 페이지 pi에 있는 링크(즉 outgoing link)의 개수를 N(pi)라고 하자.
또한 pi에서 pj로 가는 링크가 있을 때, 이것을 pi -> pj 라고 나타내자.
p1부터 pN까지, 각각의 pi에 대해 다음을 계산한다.

[TeX] R(p_i) = \sum_{p_j\rightarrow p_i} \frac{1}{N(p_j)}R(p_j) [/TeX]

3. R(p1), ..., R(pN)이 모두 충분히 수렴할 때까지 2를 반복한다.

수렴된 R(pi) 값이 바로 pi의 랭크 점수가 되므로, 점수가 높은 순서대로 페이지들을 정렬하면 된다.
이때 2~3의 과정은 위와 같이 반복으로 해도 되지만, 다음과 같이 간단한 선형대수식을 계산하여 한 방에 구할 수도 있다.


[TeX] \mathbf{r} = (\mathbf{I} - \mathbf{P}^T)^{-1}\mathbf{u} [/TeX]

위 계산의 결과물은 r이 된다. r은 랭크의 벡터로, i번째 원소의 값이 pi의 랭크 점수가 된다.
I는 단위행렬, u는 원소의 값이 모두 1인 벡터를 의미한다.
P는 행렬인데, 각 (i,j)번째 원소의 값은 pi에서 pj로 가는 링크가 있는 경우 1/N(pi), 링크가 없는 경우 0으로 정의된다.

...

자세한 알고리즘까지 나왔지만, 아직도 많은 부분이 의문 투성이일 것이다.
무엇보다, 애초에 왜 랜덤 서핑이라는 것을 생각했는가 하는 것이 가장 큰 문제이다.
일단 추론을 해 보면, 어떤 페이지의 진정한 가치 또는 정보량이 크면 클 수록 랜덤 서핑을 통해 그 페이지에 도달할 확률도 함께 높아진다는 것 같은데,
정보량과 랜덤 서핑 사이에 도대체 어떤 관계가 있길래 이렇게 가정을 했는지, 이런 가정이 과연 합리적인 것인지 아닌지...

이 모든 의문들은 다음 포스팅에서 밝혀질 것이다.