링크가 던지는 표, PageRank
많이 인용된 페이지가 중요하고, 중요한 페이지에게 인용되면 더 중요합니다. 이 돌고 도는 정의를 반복 계산으로 풉니다.
이번 회차, 내 속도로.
기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 18로 돌아옵니다.
난이도·관심 주제 고르기
1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.
이렇게 다녀와요 1단계 · 약 12분
- 출발 · DAY 18PageRank·반복 계산
- 1. 관심 주제근접 중심성·평균 거리추가 07 · 새 추가 수업
- 복귀 · DAY 18원래 회차 이어가기
- 근접 중심성·평균 거리 · 16·17회차에서 차수와 매개 중심성을 본 뒤, 프리먼이 정리한 세 번째 중심성인 ‘가까움’을 계산합니다.
선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.
핵심 개념
PageRank는 브린과 페이지(Brin & Page, 1998)가 구글 검색 엔진을 소개한 논문에서 설명한 점수입니다. 각 페이지는 자기 점수를 나가는 링크 수로 똑같이 나눠 링크한 페이지들에 건넵니다. 그래서 링크를 많이 받을수록, 점수가 높은 페이지에게서 받을수록 점수가 커지고, 링크를 많이 거는 페이지가 던지는 표 하나하나는 그만큼 작아집니다.
논문은 이것을 무작위 서퍼(random surfer)로 설명합니다. 서퍼는 링크를 무작위로 따라가다가 가끔 지루해져 아무 페이지로나 이동합니다. 링크를 따라갈 확률이 감쇠 계수(damping factor) d이고, 논문은 보통 d=0.85로 둔다고 적었습니다. 남은 1−d=0.15의 확률로는 N개 페이지 중 하나로 무작위 이동합니다. 오래 돌아다녔을 때 서퍼가 각 페이지에 머무는 비율이 PageRank이므로 점수의 합은 1입니다.
식으로 쓰면 PR(v) = (1−d)/N + d × Σ PR(u)/out(u)이고, 합은 v로 링크를 건 모든 u에 대해 계산합니다. 모든 노드를 1/N에서 시작해 이 식을 되풀이하면 값이 일정하게 수렴합니다. 원 논문의 식은 앞 항을 (1−d)로 적었지만, 여기서는 합이 정확히 1이 되도록 N으로 나눈 형태를 씁니다. 나가는 링크가 없는 노드의 점수는 보통 모든 노드에 고르게 나눠 주는 방식으로 따로 처리합니다.
PageRank는 링크 구조만 봅니다. 점수가 높다는 것은 많이, 또 중요한 곳에서 인용됐다는 뜻이지 내용이 정확하다는 뜻은 아닙니다. 링크를 인위적으로 만들어 점수를 올리려는 시도가 있을 수 있다는 점도 해석할 때 고려해야 합니다.
작은 예제로 따라가기
팔로우 그래프 A→B, A→C, B→C, C→A, D→C에서 N=4, d=0.85입니다. 모두 0.25에서 시작하고, 무작위 이동 몫은 0.15÷4=0.0375입니다.
1회 반복: C는 A의 절반(0.125)과 B·D의 전부(0.25+0.25)를 받아 0.0375+0.85×0.625≈0.569, A는 C의 전부를 받아 0.0375+0.85×0.25=0.25, B는 0.0375+0.85×0.125≈0.144, 아무도 링크하지 않는 D는 0.0375입니다. 합은 1.00입니다.
반복을 계속하면 C≈0.39, A≈0.37, B≈0.20, D≈0.04로 수렴합니다. A는 받는 링크가 하나뿐이지만 점수가 높은 C의 표를 통째로 받아 2위입니다.
직접 실험해 보기
d=0.85에서 ‘한 번 반복’을 눌러 1회 결과가 예제와 같은지 확인한 뒤 ‘10번 반복’으로 수렴값을 보고, d를 0.50과 0.95로 바꿔 D의 점수와 순위가 어떻게 변하는지 비교하세요.
반복할수록 점수가 자리 잡는 PageRank
엣지 숫자 = 다음 반복에서 보내는 몫 d × PR(보내는 계정) ÷ 진출 링크 수.
| 회차 | A | B | C | D | 합 |
|---|---|---|---|---|---|
| 0 | 0.250 | 0.250 | 0.250 | 0.250 | 1.000 |
d를 바꾸면 지금까지의 반복 횟수를 새 d로 처음부터 다시 계산합니다. D는 받는 링크가 없어 늘 (1−d)/4만 받습니다.
이번에는 직접 풀어 보세요
정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.
힌트 보기
무작위 이동 몫은 0.15÷3=0.05입니다. Z는 링크가 2개라 자기 점수의 절반씩을 X와 Y에 줍니다.
풀이와 비교하기
X=0.05+0.85×(1/6)≈0.192, Y=0.05+0.85×(1/3+1/6)=0.475, Z=0.05+0.85×(1/3)≈0.333이고 합은 1.000입니다. 링크 두 개를 받는 Y가 가장 높습니다.
풀이와 확인 표시는 이 브라우저에 저장됩니다.
오늘 이해한 것과 다시 볼 것
계산이 달라진 이유, 헷갈린 개념, 다음에 확인할 질문을 남겨 보세요.
메모는 이 브라우저에 저장됩니다. 홈에서 전체 기록을 내려받을 수 있습니다.오늘의 이해 확인
감쇠 계수 d를 0.85에서 0.50으로 낮추면, 아무도 링크하지 않는 노드의 PageRank는?
완료 조건: 확인 퀴즈 정답 · / 직접 풀기 0/1
더 깊이 읽기
예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.
The anatomy of a large-scale hypertextual Web search engineBrin & Page (1998)이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.