PageRank 및 HITS 알고리즘
PageRank와 HITS는 웹 페이지의 내용뿐만 아니라 하이퍼링크 그래프의 구조로부터 웹 페이지의 중요성이나 권위를 추정하는 링크 분석 알고리즘입니다.
Definition
PageRank는 발신 링크를 감쇠 확률(damping probability)로 따르고 그렇지 않으면 텔레포트하는 무작위 서퍼(random surfer) 하에서 정상 상태 확률(stationary probability)과 동일한 쿼리 독립적인 중요도 점수를 각 페이지에 할당하는 반면, HITS는 쿼리 종속적인 서브그래프에 대해 가치 있는 콘텐츠를 가진 페이지에 대한 권위 점수와 좋은 권위 페이지로 연결되는 페이지에 대한 허브 점수를 계산하며, 이들은 서로를 강화합니다.
Scope
이 주제는 두 가지 기본 링크 분석 알고리즘을 다룹니다. 하나는 텔레포테이션(teleportation)을 포함하는 무작위 서퍼 모델(random-surfer model)에 기반한 쿼리 독립적인 페이지 중요도 측정인 PageRank이고, 다른 하나는 상호 강화적인 허브(hub) 및 권위(authority) 점수를 계산하는 쿼리 종속적인 방식인 HITS입니다. 이 주제는 기본이 되는 무작위 보행(random-walk) 및 고유 벡터(eigenvector) 공식화, 감쇠(damping) 및 텔레포테이션의 역할, 수렴(convergence), 그리고 주제 민감형 변형(topic-sensitive variants)을 다룹니다. 이러한 점수들이 텍스트 특징과 결합되어 최종 순위를 결정하는 방법은 웹 검색 순위 지정에 속하므로 제외합니다.
Core questions
- 무작위 서퍼 모델은 PageRank를 정상 분포로 어떻게 정의합니까?
- PageRank가 잘 정의되기 위해 감쇠 또는 텔레포테이션 인자가 왜 필요합니까?
- HITS에서 허브 및 권위 점수는 어떻게 서로를 강화합니까?
- 이러한 점수들은 어떻게 반복적으로 계산되며, 언제 수렴합니까?
- PageRank와 HITS는 쿼리 독립적 대 쿼리 종속적 점수 부여에서 어떻게 다릅니까?
Key concepts
- PageRank
- 무작위 서퍼 모델
- 감쇠 인자 및 텔레포테이션
- 정상 분포 / 주 고유 벡터
- HITS
- 허브 및 권위
- 쿼리 독립적 대 쿼리 종속적 점수 부여
- 거듭제곱 반복 및 수렴
Key theories
- PageRank 무작위 서퍼 모델
- 감쇠 인자와 동일한 확률로 링크를 따르고 그렇지 않으면 무작위 페이지로 점프하는 서퍼를 모델링하면, 장기 방문에 따라 페이지 점수를 매기는 마르코프 연쇄(Markov chain)가 생성되어 안정적이고 쿼리 독립적인 중요도 측정을 제공합니다.
- HITS 허브 및 권위
- 쿼리 중심 서브그래프 내에서 HITS는 각 페이지에 자신을 링크하는 페이지의 허브 점수에 비례하는 권위 점수와 자신이 링크하는 페이지의 권위 점수에 비례하는 허브 점수를 할당하며, 이러한 상호 강화 관계를 수렴할 때까지 반복하여 계산합니다.
Clinical relevance
PageRank는 대규모 웹 검색의 부상에 핵심적인 역할을 했으며, 그래프에서 중요성과 권위에 대한 개념적 기준점으로 남아 있습니다. 링크 분석 아이디어는 웹을 넘어 인용 네트워크, 소셜 네트워크 영향력, 사기 탐지, 추천 등 지지(endorsement)와 같은 링크가 정보를 전달하는 모든 곳으로 일반화됩니다.
History
1998년과 1999년에 거의 동시에 발표된 두 가지 제안은 하이퍼링크가 권위를 인코딩한다는 것을 보여주었습니다. 클라인버그(Kleinberg)의 HITS와 페이지(Page) 및 브린(Brin)의 PageRank입니다. PageRank의 쿼리 독립적이고 전역적으로 계산된 점수는 웹 규모 서비스에 매우 적합하다는 것이 입증되었고 선도적인 검색 엔진의 기반이 되었으며, HITS는 주제 추출(topic-distillation) 및 이후의 그래프 순위 연구에 영향을 미쳤습니다.
Key figures
- Larry Page
- Sergey Brin
- Jon Kleinberg
- Rajeev Motwani
Related topics
Seminal works
- page1999
- kleinberg1999
- brin1998
Frequently asked questions
- PageRank와 HITS의 차이점은 무엇입니까?
- PageRank는 전체 웹 그래프에서 모든 페이지에 대해 단일 쿼리 독립적인 중요도 점수를 미리 계산하는 반면, HITS는 검색 시점에 쿼리를 중심으로 구축된 작은 서브그래프에서 쿼리 종속적인 허브 및 권위 점수를 계산합니다. PageRank는 웹 서비스에 더 쉽게 확장됩니다.
- PageRank에 감쇠 인자가 왜 필요합니까?
- 감쇠 인자가 없으면 무작위 서퍼는 발신 링크가 없는 페이지나 순환(cycle)에 갇힐 수 있으며, 정상 분포가 유일하거나 잘 정의되지 않을 수 있습니다. 감쇠(텔레포테이션) 확률은 서퍼가 가끔 무작위 페이지로 점프하도록 하여 유일하고 잘 작동하는 점수를 보장합니다.