이번에 더 배울 것
클라인버그(Kleinberg, 1999)의 HITS(Hyperlink-Induced Topic Search)는 노드마다 점수를 두 개 줍니다. 권위(authority) 점수는 좋은 허브들에게 많이 가리켜질수록 커지고, 허브(hub) 점수는 좋은 권위들을 많이 가리킬수록 커집니다. 서로가 서로를 정의하는 이 관계를 상호 강화(mutually reinforcing) 관계라고 부릅니다.
계산은 두 점수를 번갈아 갱신합니다. ① 각 노드의 권위 = 자신을 가리키는 노드들의 허브 점수 합. ② 각 노드의 허브 = 자신이 가리키는 노드들의 권위 점수 합. ③ 값이 끝없이 커지지 않도록 매번 정규화합니다. 원 논문은 제곱합이 1이 되게 나누지만, 같은 수로 나누는 일이라 합이 1이 되게 나눠도 순위는 같습니다. 반복하면 두 점수가 일정한 값으로 수렴합니다.
PageRank와 달리 HITS는 검색어마다 따로 계산하도록 설계되었습니다. 검색 결과 상위 페이지(root set)에 그와 링크로 이어진 페이지들을 더해 작은 부분 그래프를 만들고 그 안에서 점수를 냅니다. 그래서 주제에 맞는 허브와 권위를 찾을 수 있지만, 질의마다 계산이 필요하고 부분 그래프 안의 링크 몇 개에 결과가 크게 흔들릴 수 있습니다.
작은 예제로 따라가기
블로그 P·Q·R과 식당 X·Y·Z 사이에 P→X, P→Y, Q→X, Q→Y, R→Y, R→Z가 있습니다. 허브를 모두 1로 두면 첫 권위는 X=2, Y=3, Z=1입니다.
그 권위로 허브를 계산하면 P=X+Y=5, Q=5, R=Y+Z=4입니다. 합이 1이 되게 나누면 권위는 X 0.33·Y 0.50·Z 0.17, 허브는 P·Q 0.36·R 0.29입니다.
반복하면 권위는 Y 0.50 > X 0.37 > Z 0.13, 허브는 P·Q 0.37 > R 0.27로 수렴합니다. R은 덜 인정받는 Z를 가리켜 허브 점수가 낮습니다.
링크 하나가 바꾸는 두 점수
링크를 하나 바꾸거나 더했을 때 권위 1위와 허브 순위가 어떻게 바뀔지 먼저 예상하세요.
세 블로그가 모두 가리키는 Y가 권위 1위이고, Y와 X를 함께 가리키는 P·Q가 허브 1위입니다.
학습을 시작하면 새 문제를 직접 풀고 확인 퀴즈를 마친 뒤 선택한 본과정 회차로 돌아갑니다.