인터넷 검색 엔진 비밀 : Page Rank와 그 수학 이야기 9

오늘날 우리는 궁금한 것이 생기면 반사적으로 인터넷 검색 엔진을 켜고 정보를 찾습니다. 수많은 웹페이지 중에서 어떻게 내가 원하는 정보가 담긴 페이지가 상위에 노출될까요? 이 마법 같은 검색 결과 뒤에는 복잡하면서도 우아한 수학적 원리가 숨어 있습니다. 바로 구글 검색 엔진의 핵심 알고리즘 중 하나인 **페이지 랭크(PageRank)**입니다.

페이지 랭크는 1990년대 후반 래리 페이지(Larry Page)와 세르게이 브린(Sergey Brin)이 스탠퍼드 대학교에서 개발한 알고리즘으로, 웹사이트의 중요도를 평가하는 데 사용됩니다. 당시의 검색 엔진들은 단순히 키워드가 많이 포함된 페이지를 보여주는 방식이었기에, 검색 결과의 품질이 낮았습니다. 페이지 랭크는 웹페이지를 단순한 문서 뭉치가 아닌, 서로 연결된 거대한 네트워크로 바라보며, 링크의 구조를 통해 각 페이지의 '권위'를 수학적으로 측정하는 혁신적인 접근법을 제시했습니다.

 

1. 웹을 거대한 그래프로 이해하기 (그래프 이론)

페이지 랭크의 기본 개념은 **그래프 이론(Graph Theory)**에서 시작됩니다.

• 정점 (Vertex): 웹페이지 하나하나가 그래프의 '정점'이 됩니다.
• 간선 (Edge): 한 웹페이지에서 다른 웹페이지로 연결되는 하이퍼링크가 '간선'이 됩니다. 이때 간선은 방향을 가지는데, 링크를 거는 페이지에서 링크를 받는 페이지로 향하는 '방향성 간선(Directed Edge)'입니다.

이렇게 웹 전체를 거대한 방향성 그래프(Directed Graph)로 모델링하면, 우리는 어떤 페이지가 다른 페이지들과 어떻게 연결되어 있는지 한눈에 파악할 수 있습니다.

 

2. 권위의 전이와 투표의 개념 (선형대수학)

페이지 랭크 알고리즘의 핵심 아이디어는 "다른 웹사이트로부터 많은 링크를 받는 웹사이트는 중요하고 권위 있는 웹사이트일 것이다"라는 가정에 있습니다. 여기서 '링크'는 일종의 '추천' 또는 '투표'의 의미를 가집니다.

• 링크의 가치: 단순히 많은 링크를 받는 것만이 중요한 것이 아니라, 권위 있는 페이지로부터 받는 링크는 더 큰 가치를 가진다는 원리입니다. 마치 중요한 인물의 추천서가 더 큰 힘을 가지는 것과 같습니다.

이러한 '권위의 전이' 개념을 수학적으로 표현하기 위해 **선형대수학(Linear Algebra)**이 활용됩니다.

• 인접 행렬 (Adjacency Matrix): 웹페이지 간의 링크 관계는 '인접 행렬'이라는 행렬로 표현할 수 있습니다. 예를 들어, N개의 웹페이지가 있다면 N x N 크기의 행렬을 만들고, i번째 페이지에서 j번째 페이지로 링크가 있으면 해당 행렬 요소를 1로, 없으면 0으로 표시합니다.
• 전이 행렬 (Transition Matrix): 페이지 랭크에서는 인접 행렬을 변형한 '전이 행렬'을 사용합니다. 이 행렬은 특정 페이지에서 링크를 클릭하여 다른 페이지로 이동할 확률을 나타냅니다. 만약 어떤 페이지가 k개의 외부 링크를 가지고 있다면, 각 링크를 통해 이동할 확률은 1/k가 됩니다. 이 전이 행렬은 각 페이지의 랭크 값을 업데이트하는 데 사용됩니다.
• 반복 계산과 고유 벡터 (Eigenvector): 각 웹페이지의 페이지 랭크 점수(권위 값)는 초기값을 설정한 후 전이 행렬을 곱하는 과정을 반복하여 업데이트됩니다. 이 반복 계산을 통해 페이지 랭크 값들은 점차 안정화되어 수렴하게 됩니다. 이 수렴된 페이지 랭크 벡터는 사실상 전이 행렬의 가장 큰 **고유값(Eigenvalue)**에 해당하는 **고유 벡터(Eigenvector)**를 구하는 문제와 동일합니다. 즉, 페이지 랭크는 웹 그래프의 구조를 분석하여 각 페이지의 중요도를 나타내는 고유 벡터를 찾아내는 과정이라고 할 수 있습니다.

3. 댐핑 팩터 (Damping Factor)와 임의 보행 (Random Walk)

페이지 랭크 알고리즘에는 중요한 보정 장치인 **댐핑 팩터(Damping Factor)**가 포함됩니다. 이는 두 가지 문제를 해결하기 위해 도입되었습니다.

• 링크 단절 페이지 (Dangling Nodes): 외부로 나가는 링크가 전혀 없는 페이지가 있을 경우, 이 페이지에 도달한 가상의 웹 서퍼는 더 이상 다른 페이지로 이동할 수 없게 됩니다.
• 링크 함정 (Rank Sink): 특정 그룹의 페이지들이 서로만 링크하고 외부로 나가지 않는 경우, 랭크 점수가 이 그룹 안에 갇혀버리는 현상이 발생합니다.

댐핑 팩터는 가상의 웹 서퍼가 링크를 따라 이동하다가, 일정 확률(보통 0.15)로 링크를 클릭하는 대신 임의의 다른 웹페이지로 '순간 이동'한다고 가정합니다. 이 '순간 이동' 확률이 바로 1에서 댐핑 팩터를 뺀 값 (1-d)입니다. 댐핑 팩터 'd'는 일반적으로 0.85가 사용됩니다.

페이지 랭크 공식은 다음과 같이 표현됩니다:
PR(A) = (1 - d) + d * (PR(T1)/C(T1) + ... + PR(Tn)/C(Tn))

• PR(A): 페이지 A의 페이지 랭크 점수
• d: 댐핑 팩터 (보통 0.85)
• T1, ..., Tn: 페이지 A로 링크를 거는 페이지들
• C(Ti): 페이지 Ti가 가지고 있는 외부 링크의 총 개수
• PR(Ti): 페이지 Ti의 페이지 랭크 점수

이 공식은 각 페이지의 랭크가 "임의로 다른 페이지에 도달할 확률 (1-d)"과 "링크를 따라 도달할 확률 (d * 링크를 거는 페이지들의 랭크 합계)"의 합이라는 것을 의미합니다. 이는 '웹을 임의로 탐색하는 가상의 웹 서퍼가 어떤 페이지에 머무를 확률'이라는 확률론적 해석을 제공합니다.

 

4. 페이지 랭크의 한계와 진화

페이지 랭크는 검색 엔진 역사에 한 획을 그었지만, 몇 가지 한계점도 가지고 있습니다.

• 시간 지연: 웹의 변화를 반영하는 데 시간이 걸립니다.
• 링크 조작: 랭크를 높이기 위한 인위적인 링크 생성(백링크 조작) 시도가 발생할 수 있습니다.
• 컨텐츠의 질 무시: 단순히 링크 구조만을 보기 때문에 컨텐츠의 최신성이나 직접적인 관련성은 반영하기 어렵습니다.

이러한 한계점 때문에 구글을 비롯한 현대의 검색 엔진들은 페이지 랭크를 기반으로 하되, 수백 가지의 다른 요소(키워드 관련성, 컨텐츠의 신선도, 사용자 행동 데이터, 모바일 친화성 등)를 결합한 훨씬 복잡한 알고리즘을 사용하고 있습니다. 하지만 페이지 랭크는 여전히 웹페이지의 근본적인 '권위'를 측정하는 중요한 지표 중 하나로 기능하며, 웹의 복잡한 연결망을 수학적으로 분석하는 강력한 도구임을 증명했습니다.

결론적으로, 우리가 매일 사용하는 검색 엔진은 단순히 텍스트를 매칭하는 것을 넘어, 그래프 이론, 선형대수학, 확률론 등 다양한 수학적 개념들이 정교하게 결합된 시스템입니다. 페이지 랭크는 이 복잡한 시스템의 핵심을 이루는 아름다운 수학적 발명품이며, 덕분에 우리는 광활한 인터넷 세상 속에서 원하는 정보를 효율적으로 찾아낼 수 있습니다.