1996년의 검색 문제에서 PageRank를 도출하는 최소 구현과 수렴 원리

뒤늦게 보면 누구나 할 수 있었다고 말하기 쉽지. 데이미언 허스트가 "그럼 네가 상어를 절였냐, 내가 했지"라고 답한 게 떠오름.

루스벨트의 '경기장에 선 사람' 연설도 같은 얘기임. 비평가보다 실제로 시도하고 실패도 감수한 사람에게 공이 간다는 말이지.

1996년엔 난 어린애였어서 못 했을 듯. 링크 수를 검색 관련성과 묶는 발상은 지금 단순해 보여도 당시엔 새로웠음.

오늘날 웹에서는 PageRank만으로는 안 돌아감. 링크 조작이 없던 당시 환경에서 통했던 여러 순위 산정법 중 하나였고, 현대 인터넷용 알고리즘을 새로 만드는 건 별개 문제임.

'오늘날 작동하지 않는다'는 말은 너무 과함. 잡음 많고 희소한 쌍대 비교에서 한쪽이 다른 쪽을 보증한다고 보고 그래프 전체에 PageRank를 풀면 전역 순위를 만들 수 있음. 난 엉성한 책 쌍대 비교만으로 연간 목록을 만들 때 썼음.

비적대적 상황에서는 예전만큼 잘 작동함. 애초에 보안을 목적으로 만든 알고리즘이 아니니 링크를 조작하면 깨지는 게 당연하고, 적대적 환경에서도 통하는 PageRank류 방법은 여전히 미해결 문제임.

구글은 기억하기로 2006년에 PageRank 사용을 멈췄음. 링크 농장 때문이라기보다 웹 규모에서 정확한 행렬 풀이가 O(N^3)라서였고, 원래 PageRank로 고른 약 1,000개 시드에서 반복 그래프 순회를 하는 방식으로 바꿨다는 얘기임.

아이디어가 설명하기 쉬운 것과 실제로 발명하고 배포하는 건 다름. 1996년에 그래프로 웹을 보려면 그 사고방식이 필요했고, 당시 Python 성능이나 4MB RAM 같은 운영 제약도 넘어야 했음.

그래프 관점에서는 간단히 유도됨. 페이지를 노드, 링크를 방향 간선으로 둔 전이 행렬에서 랜덤 워커의 정상 확률분포를 구하는 것이고, 선형대수의 파워 메서드로 지배 고유벡터를 구하는 것과 같음.

당시 AltaVista를 하루에도 수십 번 썼는데 별로였음. 그래도 난 이런 발상을 못 했고, Million Dollar Homepage도 떠올리지 못했지. 당시엔 Gopher, Archie, Veronica가 이미 있어서 WWW도 처음엔 유행 못 할 거라 생각했음.

수십억 페이지가 순환 링크를 가지면 실제 계산이 바로 어려워지는 것 아닌가? 아이디어 다음에 닥칠 문제는 그 규모 아닌지 궁금함.

그건 문제가 아님. 링크 영향은 감쇠되고 수렴할 때까지 반복하면 됨. 수렴하는 무한급수를 더하는 것과 같은데, 원 논문 PDF를 무료로 찾기 어려운 건 이상하더라.

DARPA와 NASA 지원을 받았더라면 나도 했을지 모름.

브린은 PageRank 공동 발명자가 아니었다고 봄. 미국 특허 US7058628B1에는 Larry Page만 발명자로 적혀 있음.