Ruby로 짜본 구글 PageRank 알고리즘

오늘 집에 있으려니 좀이 쑤셔서 요즘 공부하고 있는 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라는 패키지를 깔아야 한다.

Xb54bURHj8.exe

실행파일

XcISLVSmyW.rb

소스

이렇게 만들어 봤으니 다시 책을 보면 이해가 좀 될까 모르겠다. 이것때문에 페이지 랭크 공부를 위해 선형대수학 책을 사서 공부를 했다는…

휴우~~~ Google PageRank 사내 세미나를 위한 예제 파일은 준비가 된거 같다. 이젠 ppt를 만들 차례군.

This entry was posted in 검색엔진

  • http://blog.repl.net/ 이삼구

    굿~~~ 잘봤습니다. :-)

  • http://dotty.org Dotty

    재미있게 잘 봤습니다. ^^
    실제로 page rank만으론 웹상에서 잘작동치않아서 내부적으로 trustRank 및 기타 휴리스틱도 많이 반영하는 것으로 아는데, 혹시 들으신 바 있으시면 피드백 부탁드립니다.

  • http://freesearch.pe.kr 고감자

    TrustRank는 논문만 뽑아두고 자세히 보지는 못했답니다.

    몇주 전에 조정후 UCLA 교수님께서 회사에 오셔서 세미나를 해줄때 TrustRank를 처음 봤답니다. 구글 페이지 랭크를 이용한 스팸처리알고리즘 이더군요. 아주 산뜻 했답니다. 그때도 PageRank에 대한 자료를 보고 있던 터라서 더욱 그랬는지도 모르구요.

    일단 구글 페이지랭크를 다 이해한 다음에 TrustRank를 습득하기 위해 넘어갈 생각입니다. 그때에 또 다시 이런 포스팅을 하게 되겠지만요.

  • http://smle.net 스믈군

    잘 보았습니다. 감사합니다.

  • Pingback: from __future__ import dream

  • http://zento.tistory.com zento

    python과 ruby에 대해 관심이 있습니다.
    ruby는 matrix와 vector가 기본 패키지에 포함이 되어 있군요.

    만약 대량의 monte-carlo simulation을 한다면
    python, ruby의 적합도는 어느정도가 될까요?

    고견을 듣고 싶습니다.

  • http://freesearch.pe.kr 고감자

    ((2r)^2)/(pi*r^2) = (정사각형 내부에 찍힌 점)/(원 내부에 찍힌점)

    위의 점화식과 랜덤으로 찍힌 점의 위치의 확률을 이용해 원주율 pi를 구하는 것처럼 발생된 난수와 그 난수를 활용한 문제 해결이라고 알고 있는데요.

    문제가 어떤지 모르겠지만, 두 언어다 적당하다고 생각합니다.
    몬테 카를로를 위해서 특별하게 고안된 라이브러리같은게 없으니..

    그런데 몬테 카를로 법에서 가장 중요한것은 rand 함수의 신뢰성이라고 생각합니다. rand 함수를 그대로 쓰면 어느정도 주기를 형성하면서 숫자를 뽑아내니 rand 함수를 부를때마다 seed를 다시 적용시킬 수 있는지 확인해보는것이 급선무라고 생각합니다.

    제가 알기론 Python은 가능한걸로 알고 있습니다. 아마도 Ruby도 가능할껍니다.(확인은 안해봤지만..)

  • http://zento.tistory.com zento

    감사합니다. :)

  • Pingback: LiFiDeA by 김진영