PageRank
PageRank은 웹 페이지 사이 링크 그래프에서 임의 보행의 정상 분포를 이용해 상대적 중요도를 계산한다 그래프 순위 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용...
| 분류 | 알고리즘 · 그래프 순위 알고리즘 |
|---|---|
| 목적 | 웹 페이지 사이 링크 그래프에서 임의 보행의 정상 분포를 이용해 상대적 중요도를 계산한다 |
| 처리 방식 | 각 페이지의 점수를 링크를 따라 분배하고 댐핑 계수와 텔레포테이션 확률을 결합하여 반복 갱신한다 |
| 복잡도·성능 | 반복마다 대체로 O(V+E), 수렴까지 반복 횟수에 의존 |
| 필수 조건 | 댐핑 계수와 dangling node의 확률 분배 및 수렴 판정이 필요하다 |
| 참고 문헌 | 기술 참고 자료 |
| 관련 분야 | 알고리즘, 자료구조 |
PageRank은 웹 페이지 사이 링크 그래프에서 임의 보행의 정상 분포를 이용해 상대적 중요도를 계산한다 그래프 순위 알고리즘 분야에서 사용되며, 자료에 대한 조작·검색·집계 결과를 계산하는 중요한 기법이다. 자료의 표현과 계산 모델을 구분해 설계하면 결과의 정확성 및 시간·공간 비용을 체계적으로 분석할 수 있다.[1]
처리 과정은 각 페이지의 점수를 링크를 따라 분배하고 댐핑 계수와 텔레포테이션 확률을 결합하여 반복 갱신한다. 들어오는 링크가 많은 페이지도 링크 제공자의 점수와 링크 수에 따라 다른 기여를 받는다. 실제 구현에서는 각 단계의 결과가 어떤 의미를 갖는지 불변식을 정하고, 입력·갱신·질의의 처리 경로를 구분한다.
성능은 반복마다 대체로 O(V+E), 수렴까지 반복 횟수에 의존 올바르게 적용하려면 댐핑 계수와 dangling node의 확률 분배 및 수렴 판정이 필요하다 데이터의 범위와 해시·비교·수치 처리 규칙, 실패 시의 동작 등을 명확히 해야 구현체에 따라 결과가 달라지는 상황을 줄일 수 있다.
활용 및 관련 기법과 비교하면 웹 검색 순위 연구에서 출발했으며 네트워크·관계 그래프의 중심성 평가에도 사용한다. 성능 평가에서는 초기 자료구조 구성과 질의·갱신, 저장 공간을 분리하여 분석하고, 실제 하드웨어의 캐시 및 메모리 접근 비용도 함께 고려한다.[2]