페이지랭크

수치해석 소프트웨어 마지막 수정: 2026-08-01 04:47:22

1. 개요[편집]

페이지랭크 PageRank
제안	Larry Page, Sergey Brin (1998)
분야	그래프 알고리즘 × 수치해석 × 정보검색
수학적 정체	확률행렬의 좌 고유벡터 (고유값 1)
표준 감쇠계수	α = 0.85
계산 방법	거듭제곱법 + 희소 행렬-벡터 곱

페이지랭크(PageRank)는 유향 그래프의 각 노드에 “무작위로 링크를 따라 걷는 서퍼가 그 노드에 머무를 정상상태 확률”을 부여하는 중심성 지표이자, 그 확률벡터를 구하는 계산 절차이다. 1998년 래리 페이지와 세르게이 브린이 웹 페이지 순위 매기기에 도입하면서 유명해졌고¹, 지금은 웹과 아무 상관 없는 분야에서 더 많이 쓰인다.

한 줄로 요약하면 “많이 링크받은 페이지가 중요하고, 중요한 페이지가 링크한 페이지는 더 중요하다” 는 재귀적 정의를 확률행렬의 고유벡터 하나로 못 박은 것이다. 이 문서는 그 모형화 — 무작위 서퍼, 댕글링 노드, 순간이동, 감쇠계수, 개인화·스팸 대응 — 를 다룬다. 이 벡터를 실제로 뽑아내는 반복 알고리즘 자체는 거듭제곱법이, 확률분포에서 표본을 뽑는 일반론은 마르코프 연쇄 몬테카를로가 각각 담당하므로 여기서는 그쪽으로 넘긴다.

2. 무작위 서퍼 모형[편집]

노드 $n$ 개짜리 유향 그래프에서 노드 $i$ 의 외부 링크 수(out-degree)를 $d_i$ 라 하자. 링크를 균일 확률로 하나 고르는 전이행렬은

P_{ij} = \begin{cases} 1/d_i & (i \to j \text{ 링크가 있을 때}) \\ 0 & (\text{그 외}) \end{cases}

이다. 순수하게 이 행렬만 따라 걷는 서퍼의 정상분포는 $\mathbf{r} = P^\top \mathbf{r}$ 를 만족해야 하는데, 웹 그래프에서는 이게 존재하지도 유일하지도 않다. 그래서 실제 페이지랭크는 “ $\alpha$ 의 확률로 링크를 따라가고, $1-\alpha$ 의 확률로 아무 페이지로나 순간이동(teleport)한다”는 서퍼를 정의한다.

\mathbf{r} = \alpha P^\top \mathbf{r} + (1-\alpha)\frac{\mathbf{v}}{n}

여기서 $\mathbf{v}$ 는 성분이 전부 1인 벡터라 $\mathbf{v}/n$ 이 균일분포가 된다. $\mathbf{r}$ 는 합이 1인 확률벡터로 정규화하며, 이 값이 그대로 페이지의 점수다. 감쇠계수(damping factor) $\alpha$ 는 관례적으로 0.85를 쓴다. 서퍼가 평균 $1/(1-\alpha) \approx 6.7$ 번 링크를 클릭한 뒤 지루해져서 주소창에 새 주소를 치는 셈이다.²

같은 식을 노이만 급수로 펼치면 페이지랭크가 모든 경로의 가중합임이 보인다.

\mathbf{r} = \frac{1-\alpha}{n}\sum_{k=0}^{\infty} \alpha^k (P^\top)^k \mathbf{v}

길이 $k$ 짜리 경로는 $\alpha^k$ 만큼 할인된다. 이 급수 표현은 나중에 스팸 분석에서도, 개인화 페이지랭크의 선형성에서도 계속 등장한다.

3. 댕글링 노드와 순간이동이 하는 일[편집]

웹에는 외부 링크가 하나도 없는 페이지가 널려 있다. PDF, 이미지, 아직 크롤링하지 않은 페이지 같은 것들이고 이를 댕글링 노드(dangling node)라 한다. 댕글링 노드에 해당하는 $P$ 의 행은 전부 0이라 $P$ 는 확률행렬이 아니게 되고, 반복을 돌리면 확률질량이 그 구멍으로 줄줄 새어나가 결국 $\mathbf{r} \to \mathbf{0}$ 이 된다. 표준 처방은 그 행을 균일분포로 갈아끼우는 것이다. 댕글링 표시벡터를 $\mathbf{d}$ 라 하면

\bar{P} = P + \frac{1}{n}\mathbf{d}\,\mathbf{v}^\top, \qquad G = \alpha \bar{P} + \frac{1-\alpha}{n}\mathbf{v}\mathbf{v}^\top

이 되고, 이 $G$ 를 구글 행렬(Google matrix)이라 부른다. 여기서 두 수선이 각각 무엇을 고쳤는지가 이 모형의 핵심이다.

댕글링 보정은 $\bar{P}$ 를 진짜 확률행렬로 만든다(모든 행 합 = 1). 확률 보존이 회복된다.
순간이동 항은 $G$ 의 모든 성분을 양수로 만들어 그래프를 강연결로 바꾼다. 즉 $G$ 는 기약(irreducible)이면서 대각 성분이 양수라 비주기(aperiodic)다.

여기까지 오면 페론-프로베니우스 정리를 쓸 수 있다. 양행렬의 스펙트럼 반경은 단순 고유값이고 대응하는 좌고유벡터는 성분이 전부 양수이며 유일하다 — 확률행렬이므로 그 고유값은 정확히 1이다. 결국 정상분포가 존재하고, 유일하며, 모든 페이지가 0보다 큰 점수를 받는다는 것이 순간이동 한 줄로 보장된다. 웹 그래프에는 링크가 들어오기만 하고 나가지 않는 “거미 덫”(spider trap)이 흔한데, 순간이동이 없으면 확률질량이 전부 거기 갇힌다.³

4. 수렴률과 계산[편집]

구글 행렬의 제2 고유값 크기는 정확히 $\alpha$ 로 상계된다(Haveliwala–Kamvar, 2003). 원래 그래프가 강연결 성분을 둘 이상 가지면 $|\lambda_2| = \alpha$ 로 딱 붙는다. 거듭제곱법의 오차는 $|\lambda_2/\lambda_1|^k = \alpha^k$ 로 줄어들므로, 정밀도 한 자릿수를 벌려면

k = \frac{1}{\log_{10}(1/\alpha)} \approx \frac{1}{0.0706} \approx 14.2

즉 약 14회 반복이 필요하다. 웹 규모에서 $10^{-8}$ 수준의 잔차를 원하면 50~100회쯤 돌리면 된다는 계산이 여기서 나온다. 반대로 $\alpha$ 를 0.99로 올리면 한 자릿수당 230회가 되어 비용이 16배로 뛴다. 0.85라는 값이 살아남은 이유의 절반은 이 수렴 속도다.

$\alpha$ 는 수렴 속도만이 아니라 해의 안정성도 지배한다. 선형계 $(I - \alpha\bar P^\top)\mathbf{r} = (1-\alpha)\mathbf{v}/n$ 의 대각우세도가 $1-\alpha$ 라, 링크 몇 개를 바꿨을 때 순위가 얼마나 흔들리는지에 대한 섭동 상계가 $1/(1-\alpha)$ 인자를 달고 나온다. $\alpha=0.85$ 면 증폭이 약 6.7배, $0.99$ 면 100배다 — 스팸 저항성 관점에서도 감쇠계수를 함부로 올리면 안 된다.

구현 관점에서 페이지랭크의 매력은 한 번의 반복이 희소 행렬-벡터 곱 하나로 끝난다는 것이다.

\mathbf{r}^{(k+1)} \leftarrow \alpha P^\top \mathbf{r}^{(k)}, \qquad \mathbf{r}^{(k+1)} \leftarrow \mathbf{r}^{(k+1)} + \frac{1 - \|\mathbf{r}^{(k+1)}\|_1}{n}\mathbf{v}

둘째 줄이 재치 있는 부분이다. 댕글링 보정 $\mathbf{d}\mathbf{v}^\top$ 와 순간이동 $\mathbf{v}\mathbf{v}^\top$ 은 둘 다 랭크 1이라 행렬로 만들 필요가 전혀 없고, 곱한 뒤 새어나간 확률질량을 균일하게 되돌려주면 수학적으로 동일하다. 덕분에 메모리는 링크 수 $\mathrm{nnz}$ 에 선형이고, 밀집 행렬은 어디에도 등장하지 않는다. 반복마다 노드를 순회하는 구조라 병렬 컴퓨팅에도 잘 맞아, 링크 목록을 노드 블록으로 쪼개는 방식이 표준이다.

5. HITS와의 비교[편집]

“중요한 노드가 가리킨 노드가 중요하다”는 재귀 자체는 페이지랭크의 발명품이 아니다. 경로 길이에 $\beta^k$ 감쇠를 주는 카츠 중심성(1953)이 이미 같은 급수 형태였고, 차이는 페이지랭크가 나가는 링크 수로 나눈다는 정규화에 있다. 같은 해에 나온 라이벌 HITS(Kleinberg, 1999)는 각 노드에 허브 $\mathbf{h}$ 와 권위 $\mathbf{a}$ 를 따로 주고 $\mathbf{a} = A^\top \mathbf{h}$ , $\mathbf{h} = A\mathbf{a}$ 를 번갈아 갱신한다. 결국 $\mathbf{a}$ 는 $A^\top A$ 의 주고유벡터, 즉 $A$ 의 특이값 분해의 첫 우특이벡터다.

승부를 가른 것은 질의 독립성이었다. HITS는 검색어마다 부분 그래프를 만들어 그 위에서 반복을 다시 돌려야 하지만, 페이지랭크는 웹 전체에 대해 오프라인으로 한 번 계산해 두고 질의 시점에는 조회만 한다. 응답 시간이 밀리초 단위인 서비스에서 이 차이는 결정적이다.

6. 개인화 페이지랭크[편집]

순간이동 분포를 균일분포 $\mathbf{v}/n$ 대신 특정 노드 집합에 몰아준 것이 개인화 페이지랭크(personalized PageRank, PPR)다. 서퍼가 지루해질 때마다 “내가 좋아하는 페이지”로 돌아가므로, 점수는 그 시드 근처를 중심으로 재분배된다. 시드가 노드 하나면 그 노드에서 본 국소 중심성이 되고, 이것이 추천 시스템·친구 추천·지식그래프 질의의 기본 도구다.

핵심 성질은 선형성이다. 순간이동 분포 $\mathbf{u}$ 에 대한 해를 $\mathbf{r}(\mathbf{u})$ 라 하면 $\mathbf{r}(a\mathbf{u}_1 + b\mathbf{u}_2) = a\,\mathbf{r}(\mathbf{u}_1) + b\,\mathbf{r}(\mathbf{u}_2)$ 가 성립한다. 시드 하나짜리 해들을 미리 계산해 두면 임의의 조합은 덧셈으로 얻는다는 뜻이라, 실시간 질의가 가능해진다. 물론 노드 $10^{10}$ 개짜리 그래프에서 전부 미리 계산할 수는 없어서 실무에서는 몬테카를로(짧은 무작위 보행 표본), 국소 푸시(잔차가 큰 노드만 밀어내는 Andersen–Chung–Lang 방식) 같은 근사가 쓰인다. 이 국소 푸시 기법은 시드 주변의 낮은 컨덕턴스 절단을 찾아내는 데도 쓰여서, 피들러 벡터 기반 스펙트럴 이분과 목적이 겹친다.

7. 링크 스팸과 그 대응[편집]

점수가 돈이 되는 순간 게임이 시작된다. 페이지랭크가 경로의 할인 합이라는 사실은, 자기 페이지로 향하는 경로를 인공적으로 대량 생산하면 점수가 오른다는 뜻이기도 하다. 대표적인 구조가 링크 팜(link farm)이다. 수천 개의 껍데기 페이지가 서로 촘촘히 링크하며 확률질량을 가둬두다가, 정해진 목표 페이지 하나로만 흘려보낸다. 상호 링크 교환, 댓글·위키 스팸, 만료 도메인 매입도 모두 같은 원리를 노린다.

방어의 고전이 TrustRank(Gyöngyi 외, 2004)다. 사람이 직접 검수한 소수의 신뢰 시드 집합을 순간이동 분포로 쓰는 개인화 페이지랭크를 돌린다. 신뢰는 링크를 따라 감쇠하며 전파되므로, 신뢰 사이트에서 몇 홉 이상 떨어진 링크 팜은 트러스트랭크가 바닥에 깔린다. 여기서 파생된 지표가 스팸 질량(spam mass) — 일반 페이지랭크와 트러스트랭크의 차이가 크면 “링크는 많이 받았는데 그 출처가 죄다 수상하다”는 신호다. 반대 방향으로 스팸 시드에서 출발해 전파하는 Anti-TrustRank, 링크 대신 rel=“nofollow” 속성으로 아예 전이를 끊는 방식도 함께 쓰인다.

덧붙이면 오늘날 검색 순위에서 페이지랭크는 수백 개 신호 중 하나로 축소됐고, 툴바 페이지랭크 공개 수치는 2016년에 완전히 폐기됐다. 그럼에도 알고리즘 자체는 여전히 살아 있다.⁴

8. 웹 밖의 응용[편집]

그래프와 “중요도”라는 개념이 있는 곳이면 어디든 이식된다. 링크가 무엇을 의미하는지만 바꾸면 되기 때문이다.

분야	노드 / 링크	이름·비고
생물정보	유전자 / 공발현·상호작용	GeneRank, 발현 데이터를 시드로 쓴 개인화 PR
단백질체	단백질 / 상호작용	재시작 무작위 보행(RWR), 질병 유전자 우선순위화
학술	논문·저널 / 인용	Eigenfactor, CiteRank — 단순 인용수의 자기참조 보정
소프트웨어	함수·패키지 / 호출·의존	핵심 모듈 식별, 취약점 파급 범위 추정

수치해석 쪽에서 보면 페이지랭크는 결국 $(I - \alpha \bar{P}^\top)\mathbf{r} = (1-\alpha)\mathbf{v}/n$ 이라는 거대 희소 선형계다. 계수행렬이 대각우세라 조건수가 얌전하고( $\alpha$ 가 작을수록 좋아진다), 크리로프 부분공간법이나 다중격자법류의 가속을 얹으려는 시도가 꾸준히 나왔다. 다만 반복 하나가 이미 너무 싸서, 정직한 거듭제곱법을 이기는 게 생각보다 어렵다는 게 이 분야의 오랜 농담이다.

9. 관련 문서[편집]

이름의 유래가 “웹 페이지(page)의 순위”가 아니라 래리 페이지의 성이라는 것이 이 분야 최고의 말장난. 특허(US 6285999)는 스탠퍼드 대학이 보유하고 구글이 독점 라이선스를 받았으며, 대가로 받은 구글 주식을 2005년에 처분해 대학이 3억 달러 이상을 챙겼다. 지도교수 잘 만나는 것보다 대학원생 잘 받는 게 남는 장사다. ↩
왜 하필 0.85인지에 대한 원논문의 유도는 없다. “잘 되더라”에 가깝다. 다만 뒤에 나오는 수렴률 논의를 보면 이 값이 정확도와 반복 횟수 사이의 꽤 합리적인 타협이라는 사후 정당화는 가능하다. 수치해석에서 상수의 출처가 “경험적”인 경우는 이것 말고도 많다. ↩
순간이동이 없는 웹 그래프에 거듭제곱법을 돌리면 확률질량이 몇 개의 흡수 집합으로 전부 빨려 들어가 나머지 페이지가 전부 0점이 된다. 초기 크롤러 시절 “우리 사이트 점수가 0인데요”라는 문의의 상당수가 이 현상이었다. ↩
그래서 SEO 업계는 툴바 수치가 사라진 뒤로 도메인 오소리티(DA) 같은 제3자 대체 지표를 만들어 팔고 있다. 원본이 사라지면 근사를 팔면 된다 — 대리 모델의 정신이 마케팅에도 적용되는 셈이다. ↩