Day 19 · 출발점을 정한 PageRank

A SMALL DETOUR

이번 회차, 내 속도로.

기초를 더 짚거나 궁금한 주제로 잠깐 넓혀 보세요. 최대 3단계를 거쳐 DAY 19로 돌아옵니다.

난이도·관심 주제 고르기

이번 회차는 어느 속도로 볼까요?기초부터새 보충 수업부터 짚어요현재 수준으로관심 주제부터 살펴봐요한 걸음 더새 심화 수업까지 넓혀요

더 살펴볼 주제 1~2개 선택근접 중심성·평균 거리추가 07 · 새 수업 · 16·17회차에서 차수와 매개 중심성을 본 뒤, 프리먼이 정리한 세 번째 중심성인 ‘가까움’을 계산합니다.허브 점수·권위 점수추가 08 · 새 수업 · 18회차의 PageRank가 점수 하나로 중요도를 잰다면, HITS는 ‘잘 가리키는 노드’와 ‘잘 가리켜지는 노드’를 따로 잽니다.차수 중심성DAY 16 · 차수 중심성의 계산법과 한계를 알면 다른 중심성이 왜 필요한지 설명할 수 있습니다.매개 중심성DAY 17 · 두 무리 사이의 길목을 매개 중심성으로 찾아, 차수가 같은 노드의 역할 차이를 구분합니다.PageRank·반복 계산DAY 18 · 점수를 링크로 나눠 건네는 PageRank 반복 계산을 손으로 검산할 수 있게 됩니다.HippoRAG·개인화 PageRankDAY 91 · 질문 속 엔티티에서 개인화 PageRank를 돌려 근거 문단을 찾는 HippoRAG에서 이 챕터의 계산이 그대로 쓰입니다.

1/2개 선택 · 새 보충·심화 수업과 본과정 다시 읽기를 선택할 수 있어요.

이렇게 다녀와요 1단계 · 약 12분

출발 · DAY 19개인화 PageRank
1. 관심 주제근접 중심성·평균 거리추가 07 · 새 추가 수업
복귀 · DAY 19원래 회차 이어가기

근접 중심성·평균 거리 · 16·17회차에서 차수와 매개 중심성을 본 뒤, 프리먼이 정리한 세 번째 중심성인 ‘가까움’을 계산합니다.

선택과 경로 기록은 이 브라우저에 저장됩니다. 본과정의 회차 완료와는 별도입니다.

복귀: DAY 19 → 본과정 다음 회차: DAY 20

01 / UNDERSTAND

핵심 개념

일반 PageRank의 서퍼는 지루해지면 N개 노드 중 아무 곳으로나 이동합니다. 개인화 PageRank(personalized PageRank, PPR)는 이 무작위 이동이 미리 정한 시작 노드(또는 노드 묶음)로만 돌아가게 바꿉니다. 브린과 페이지(1998)도 무작위 이동 항을 한 페이지나 페이지 묶음에만 더하는 변형으로 개인화를 할 수 있다고 언급했습니다.

식은 PR(v) = (1−d)·s(v) + d × Σ PR(u)/out(u)입니다. s(v)는 시작 노드면 1, 아니면 0이고, 시작 노드가 여러 개면 1을 나눠 가집니다. 서퍼는 링크를 따라 퍼져 나가다가 매번 15%의 확률로 출발점으로 끌려오므로, 출발점에 가깝고 여러 길로 이어진 노드일수록 점수가 높습니다. 그래서 이 점수는 ‘출발점에서 본 관련도’로 읽을 수 있습니다.

이런 성질 때문에 PPR은 추천과 검색에 자주 쓰입니다. 사용자가 좋아한 상품에서 출발해 점수가 높은 다른 상품을 추천하거나, 질문에 나온 엔티티에서 출발해 관련 문서를 찾습니다. 91회차의 HippoRAG는 질문 속 엔티티를 시작 노드로 지식 그래프 위에서 개인화 PageRank를 돌려, 여러 단계 떨어진 근거를 한 번에 찾습니다. 다만 결과가 출발점에 크게 좌우되므로, 출발점이 잘못 잡히면 엉뚱한 이웃이 높은 점수를 받습니다.

개인화 PageRank는 무작위 이동을 시작 노드로만 되돌려, 그 노드에서 본 관련도가 높은 노드를 찾습니다.

02 / WORKED EXAMPLE∑

작은 예제로 따라가기

동아리 네트워크의 엣지를 양방향 화살표로 보고 일반 PageRank를 구하면 지아·서준·유나·태오 약 0.136, 하린·도윤 약 0.133, 민수·보라 약 0.096으로 거의 고릅니다.

민수를 시작 노드로 하면 민수 0.273, 지아·서준 0.217, 하린 0.140, 도윤 0.060, 유나·태오 0.036, 보라 0.020이 됩니다. 민수 쪽 무리 4명이 점수의 약 85%를 가져갑니다.

보라를 시작 노드로 하면 같은 값이 좌우로 뒤바뀌어 보라 0.273, 유나·태오 0.217이 됩니다. 그래프는 그대로인데 출발점만 바꿔 순위가 뒤집혔습니다.

03 / EXPLORE

직접 실험해 보기

민수를 눌러 개인화 PageRank의 badge와 순위를 확인한 뒤 일반 PageRank와 번갈아 비교하고, 시작 노드를 하린이나 보라로 바꿔 순위가 어떻게 달라지는지 보세요.

LIVE EXPERIMENT · PERSONALIZED PAGERANK

출발점을 정해 PageRank 다시 계산하기

시작 노드 (눌러서 변경)상위 3

민수 근처가 높아집니다무작위 이동(확률 1−d = 0.15)이 늘 민수(으)로만 돌아갑니다. 무방향 엣지는 양방향 링크 2개로 봅니다.

순위	이름	개인화	일반
1	민수	0.273	0.096
2	지아	0.217	0.136
3	서준	0.217	0.136
4	하린	0.140	0.133
5	도윤	0.060	0.133
6	유나	0.036	0.136
7	태오	0.036	0.136
8	보라	0.020	0.096

04 / RECALL & PRACTICE

이번에는 직접 풀어 보세요

정답을 보기 전에 계산과 이유를 적어 보세요. 해설과 비교하고 확인 표시를 남기면 완료할 수 있습니다.

문제 1

노드 3개가 한 줄로 이어진 무방향 그래프 가–나–다를 양방향 화살표로 보고, 가를 시작 노드로 d=0.85 개인화 PageRank를 한 번 반복하세요. 처음 값은 가=1, 나=0, 다=0입니다.

힌트 보기

무작위 이동 몫 0.15는 가에게만 갑니다. 가는 이웃이 나뿐이라 자기 점수 전부를 나에게 보내고, 나는 가와 다에게 절반씩 보냅니다.

풀이와 비교하기

가=0.15+0.85×(나의 절반 0)=0.15, 나=0.85×(가의 전부 1)=0.85, 다=0.85×(나의 절반 0)=0이고 합은 1.00입니다. 계속 반복하면 나 약 0.46, 가 약 0.35, 다 약 0.20으로 수렴해 출발점과 그 이웃이 높게 남습니다.

내 풀이를 해설과 비교하고 다른 점을 확인했어요.

풀이와 확인 표시는 이 브라우저에 저장됩니다.

더 깊이 읽기

예제와 실험 데이터는 이 과정을 위해 만든 것입니다. 원문은 선택 자료이며, 강의와 직접 풀기만으로도 다음 회차를 이어갈 수 있습니다.

The anatomy of a large-scale hypertextual Web search engineBrin & Page (1998)HippoRAG: Neurobiologically Inspired Long-Term Memory for Large Language ModelsGutiérrez et al. (2024)

이 자료는 개념 학습용입니다. 실제 데이터베이스·라이브러리·플랫폼의 동작과 설정은 제품과 버전마다 다를 수 있습니다.

출발점을 정한 PageRank