오늘 집에 있으려니 좀이 쑤셔서 요즘 공부하고 있는 Ruby로 그동안 틈틈히 봐두었던 Google PageRank 알고리즘을 짜보았다.
물론 콘솔 기반으로 만들었고 이해하기 위해서는 약간의 링크 메트릭스에 대한 지식이 필요하다.
노드의 갯수?
이것은 웹문서의 갯수라고 생각하면 된다. 스샷에서는 3개라고 했으니 이 프로그램 전체에 있는 웹문서는 3개뿐이다. 이 3개 노드 사이에서 서로 링크에 관련된 정보가 필요한데 이것이 바로 X번째 노드벡터의 outLink를 입력하는 부분이다.
첫번째 노드벡터의 OutLink 정보가 1,0,1로 되어 있는데 이것이 의미하는것은 첫번째 노드(자기 자신)에 링크가 걸렸다는 의미고 두번째 노드로 나가는 링크는 없고, 세번째 노드로 나가는 링크는 존재한다는 걸 의미한다.(0은 존재않함, 1은 존재함 Boolean으로 표시함)
좀 웃긴 부분인데 자기 자신에 대한 링크가 되어 있는 경우다.(예제를 만들다 보니.. ㅡㅡ;)
두번째, 세번째 노드벡터 정보도 마찬가지 이다. 두번째 0,0,0 일 경우는 아무 아웃링크가 없는 경우 Dangling node일 경우다.(물론 이 경우에 Score가 집중될걸 대비해 PageRank는 보정작업을 한다.)
이런식으로 자료 입력을 하면 첫 링크정보 Matrix는
1,0,1
0,0,0
0,1,1
이 되고 Row는 OutLink, col은 inlink정보가 된다. 물론 이 링크 정보는 알고리즘 상으로 normalization이 된다.
여기 이터레이션을 위한 정밀도 임계값 설정을 하는데, 이 부분은 이전 PageRank Vector와 현재 PageRank Vector의 – 연산의 유클리드언 거리를 이용한 조건 설정을 위함이다. 간단히 말해서 이전 벡터와 현 벡터의 원점에서의 거리의 차이값이 임계값 이하로 내려갈때 Rank Iteration은 끝이난다.
또한 Scoring Parameter입력을 하는데 이곳은 사용자가 링크를 따라갈 확률을 넣어주면 된다. 그러니 1 – Scoring Parameter는 링크를 따라 써핑을 하다가 갑자기 어느 한 페이지로 점프할 확률이 될 것이다. (페이지 랭크에서 이 개념을 보구 놀라고 말았다. 이름하여 random surfer)
따라서 결과 도출을 위해 4번의 PageRank Vector의 갱신이 이루어졌고 랭킹은 3번노드, 2번노드, 1번노드 순이 되었다.
위의 예제는 세상의 웹페이지가 3개 존재한다는 가정하에 만들것이고, 실제적으로 구글은 81억 X 81억 크기의 링크 메트릭스를 페이지 랭크를 위해 계산하고 있고 생각해보니 엄청난 계산량이라는 생각이 든다. 약간의 수학적 지식으로는 submatrix를 어떻게 나누고 각각의 계산을 하는지가 노하우일것 같다는 예상을 해본다.
예제를 굳이 Ruby로 짠 이유가 뭐냐고 묻는다면…. Ruby 연습을 위함이고, 또한 Ruby 라이브러리 패키지에 Matrix와 Vector 계산을 위한것들이 기본적으로 포함되어 있다는 이유 정도가 될 것이다. 참고로 Python은 따로 scipy라는 패키지를 깔아야 한다.
이렇게 만들어 봤으니 다시 책을 보면 이해가 좀 될까 모르겠다. 이것때문에 페이지 랭크 공부를 위해 선형대수학 책을 사서 공부를 했다는…
휴우~~~ Google PageRank 사내 세미나를 위한 예제 파일은 준비가 된거 같다. 이젠 ppt를 만들 차례군.
Ruby로 짜본 구글 PageRank 알고리즘 by from __future__ import dream is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.