페이지랭크

페이지랭크(PageRank)는 구글이 1998년 공동 창업자 래리 페이지와 세르게이 브린이 개발한 웹 페이지의 중요도를 평가하는 알고리즘이다. 웹 그래프에서 각 페이지를 노드, 하이퍼링크를 간선으로 모델링하여, 페이지 간의 상호 연결성을 기반으로 가중치를 부여한다. 페이지랭크 값은 검색 결과 정렬에 활용되며, 이후 다양한 분야의 순위 산정 및 그래프 분석에 응용되고 있다.

개념

페이지랭크는 무작위 서퍼 모델(random surfer model) 을 전제로 한다. 서퍼가 현재 페이지에서 임의의 하이퍼링크를 따라 이동할 확률(보통 85 %~90 %)과, 아무 페이지든 무작위로 점프할 확률(보통 10 %~15 %)을 조합하여 각 페이지의 장기 체류 확률을 계산한다. 이 확률이 바로 페이지랭크 점수이며, 값이 높을수록 해당 페이지가 “중요하다”고 판단한다.

역사

원리 및 수식

기본 식

페이지랭크 $ PR(i) $는 다음과 같이 정의된다.

$$ PR(i)=\frac{1-d}{N}+d\sum_{j\in M_{i}}\frac{PR(j)}{L(j)} $$

• $ N $ : 전체 페이지 수
• $ d $ : 댐핑 팩터(damping factor, 일반적으로 0.85)
• $ M_{i} $ : 페이지 $ i $로 링크되는 페이지 집합
• $ L(j) $ : 페이지 $ j $가 가지고 있는 아웃링크 수

위 식을 모든 페이지에 대해 행렬 형태로 표현하면 고정점 문제로 볼 수 있다. 전통적으로 전력법(power iteration)을 이용해 수렴시킨다.

수렴 조건

• 초기값은 보통 모든 페이지에 동일한 값 $ \frac{1}{N} $을 할당한다.
• 반복 계산 후 $|PR^{(k+1)}-PR^{(k)}|_1 < \epsilon$ (보통 $\epsilon=10^{-6}$)이면 수렴으로 판단한다.

적용 분야

1. 검색 엔진 : 구글을 비롯한 여러 검색 서비스가 초기 순위 산정에 활용.
2. 소셜 네트워크 분석 : Influence 모델링, 사용자 영향도 측정.
3. 추천 시스템 : 아이템 간 연관성을 그래프 기반으로 평가.
4. 학술 인용 분석 : 논문 인용 네트워크에서 영향력 있는 논문 선정.
5. 웹 스팸 탐지 : 비정상적인 링크 구조를 식별해 스팸 페이지를 차단.

비판·한계

관련 알고리즘 및 변형

• HITS (Hyperlink-Induced Topic Search) : “허브·권위” 점수를 동시에 계산.
• SALSA (Stochastic Approach for Link-Structure Analysis) : HITS와 PageRank의 혼합형.
• TrustRank : 신뢰도 기반 스팸 필터링 알고리즘.
• Personalized PageRank : 사용자별 선호를 반영해 초기 벡터를 개인화.
• Topic‑Sensitive PageRank : 특정 주제에 맞는 가중치를 부여.

참고문헌

1. Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, “The PageRank Citation Ranking: Bringing Order to the Web”, Technical Report, Stanford University, 1999.
2. Amit Singhal, “Search Engine Optimization (SEO) and PageRank”, Google Research Blog, 2005.
3. Soumen Chakrabarti, “Mining the Web: Discovering Knowledge from Hypertext Data”, Morgan Kaufmann, 2002.

외부 링크

• 구글 학술 검색 – PageRank 논문
• Wikipedia – PageRank (영문)

이 항목은 2026년 2월 현재의 정보를 기반으로 작성되었으며, 최신 연구 동향에 따라 내용이 업데이트될 수 있다.