페이지랭킹 by google 20042521 김진태 국민대학교.

Presentation on theme: "페이지랭킹 by google 20042521 김진태 국민대학교."— Presentation transcript:

1 페이지랭킹 by google 김진태 국민대학교

2 PageRank gadget

3 Motivation 웹 페이지의 상대적 중요성을 어떻게 추산할 것인가? World Wide Web
Hypertext 기존 score알고리즘의 문제 임의의 조작 가능

4 Link Structure of the Web
Forwardlink(out edges) 페이지를 다운받으면 포워드링크를 알 수 있음. Backlink(in edges) 특정 페이지의 모든 백링크를 찾는 것은 불가능 Many Backlinks -> more important Important page’s forwarlink -> more important 어떤 페이지가 높은 랭크의 백링크를 많이 가질수록 그 페이지의 랭크도 올라간다. 예를 들어 페이지랭크가 9인 네이버에서 링크한 페이지는 아까 테스트할때 보았던 저의 보잘것 없는 블로그에서 링크한 페이지보다 더 중요한 페이지라는 것을 의미합니다.

5 pagerank (단순화시킨 버전) u = 웹페이지 Fu = u페이지가 가리키는 페이지의 집합
Bu = u페이지를 가리키는 페이지의 집합 Nu = |Fu| ; Fu의 개수 c = 노말라이제이션에 사용되는 팩터 (c < 1; 댕글링 링크)

6 pagerank – rank sink 두 페이지가 서로 가리키고 있으며 다른 페이지로는 연결되어 있지 않은 경우
무한 루프에 빠져 랭크를 계속 계산하며 외부로 전혀 분산하지 못한다. rank sink로부터 초래되는 문제를 해결하기 위해 rank source를 도입 source와 sink (그래프 이론 용어) sink : 밖으로 나가는 링크가 없는 것 source : 안으로 들어오는 링크가 없고 밖으로 나가는 것만 잇는 것 '소스'(source)와 '싱크'(sink)는 그래프 이론에서 나온 용어로, 아웃엣지가 없는, 즉 밖으로 나가는 링크가 없는 것을 싱크라 하고 반대로 인엣지가 없는, 즉 안으로 들어 오는 링크는 없고 밖으로 나가는 것만 있는 것을 소스라 합니다.

7 pagerank (랭크 소스 도입) E(u) : 랭크의 소스에 해당하는 웹 페이지의 벡터 중 하나
Random Surfer Model ‘랜덤 서퍼’의 행동을 모델링한 것이 페이지랭크 실제 웹서퍼가 rank sink를 만나 루프 내를 맴돌 가능성 -> ZERO 실제 웹서퍼라면 다른 페이지로 점프할 것이다. -> 부가적인 팩터 E

8 Dangling links problem
외부로 나가는 링크가 없는 페이지를 가리키는 링크 Problem dangling link의 가중치가 어디로 분산되고 있는지가 불분명 danglink link가 너무 많다. 다운로드한 문서가 100인 경우 100개의 문서에서 가리키는 링크의 문서를 모두 다운받기 어렵다. Solution dangling link 제거 모든 페이지 랭크가 계산될 때까지 무시 다른 링크의 노멀라이제이션이 영향을 받을 수는 있지만 크게 변화하지는 않는다. 페이지 랭크의 계산이 끝난 후 dangling link 첨가

9 Implementation 가중치 수렴 부모ID를 이용해서 링크 구조를 정렬 댕글링 링크 제거 랭크값 초기화
몇 번의 반복 작업만으로도 대부분의 댕글링 링크 제거 가능 랭크값 초기화 초기화 값을 잘 설정하면 수렴과정의 속도를 높일 수 있다. 가중치 수렴 현재 진행 중인 단계의 가중치는 메모리에 저장되고 전단계의 가중치는 디스크를 통해 리니어하게 엑세스한다. 가중치 수렴 후, 댕글링 링크 추가 후 랭킹 재연산

10 Convergence Properties

11 페이지랭크 적용 결과 비교 조건 : 1600만 페이지를 수집하여 제목만을 사용하는 검색
 우리는 페이지랭크를 활용한 두 가지 검색엔진을 임플리멘테이션했다. 하나는 단순한 타이틀 기반의 검색엔진이고 다른 하나는 풀 텍스트 검색엔진이다. 후자의 이름은 구글이다. 구글은 표준적인 IR 측정치, 근접성(proximity), 앵커 텍스트(웹 페이지를 가리키는 링크의 텍스트), 그리고 페이지랭크 등의 많은 요소를 바탕으로 검색 결과를 랭킹한다.

12 Common Case 페이지랭크를 이용한 검색은 커먼케이스를 잘 처리하게 된다.
꽃을 검색하였을 때 단순히 꽃의 정보가 담긴 사이트가 아닌 꽃 판매 사이트를 출력하는 경우

13 Personalized PageRank
랭크싱크처럼 아웃엣지가 없는 싸이클을 보충하기 위한 랭크 소스 웹페이지의 벡터

14 페이지랭크의 적용 웹 트래픽의 추산 백 링크 예측자로써의 페이지랭크 사용자 네비게이션:페이지랭크 프락시

15 결론 페이지랭크 ‘중요한’페이지로부터의 백링크는 평균적인 페이지들로부터의 백 링크보다 더 중요하다.
페이지의 컨텐트에 상관없이 오직 웹의 그래프 구조 상의 위치에만 의존하는 모든 웹 페이지의 글로벌 랭킹 ‘중요한’페이지로부터의 백링크는 평균적인 페이지들로부터의 백 링크보다 더 중요하다. 재귀적인 정의를 통해 확실히 구현되어 있다. 페이지랭크 실험을 통해 웹 그래프의 구조가 정보검색 작업에서 매우 유용하다는 것을 증명하였다.