pageRank the flow formulation

주요용어

flow model

dead end

spider trap

여기서 아이디어는 링크를 하나의 투표라고 생각하는것이다.

그런데 이때 투표를 많이받은애가 링크를 주는것과 투표를 적게받은애가 링크를 주는것엔 값차이가 있어야한다

그래서 우리는 노드들이 있을때 j 에서 나가는 노드가 N개 있을경우 j의 투표력은 r(j)/n이라고 할것이다

그럼 r(j)는 어떻게 정할것인가

r(j)는 노드 j 로 들어오는 모든 투표력의 합이다

flow model

r(j) = (i->j) r(i)/d(i)

d(i) 는 노드 i 가 연결한 링크수이다

그리고 모든 r(i) 의 합은 1이 되어야한다

그리고 이 연결을 표현한 매트릭스 M은 세로의 합이 1이 되어야한다

flow model의 계산법

r(i) = 1/N으로 설정하고

r = M*r을 계산전값과 계산후값의 차가 임계치를 넘지못했을때까지 한다

그럼 대체로 어떤 값에서 수렴하는데

이때 문제가 몇가지 발생한다

문제1

노드가 단 2개일때 서로를 가리키고있으면 서로를 번갈아가면서 지목하여 수렴이 불가능!

문제2

노드가 어떤 한가지를 지목하고 끝나는 경우 0,으로 전부 정리되어버린다

문제 2번같은경우는 크게봤을때

Dead end 와 스파이더 트랩이라는 문제에 같히게된다

스파이더 트랩일때 해결법

텔레포트라는것을 해준다 예를들어 노드 ABC가 있을때 C가 자기자신만 지목하고 다른사람을 지목하지 않는다면

B값을 0.8정도해주고 (B*M + (1-B)*(전부다1/N인 매트릭스) )*r 해준다

이게 스파이더 트랩은 해결해주지만 데드엔드는 해결해주지 못한다다

데드엔드 solution

데드엔드가 나는 녀석의 column을 전부 (1/N)으로 바꿔서 계산한다.

그래야 세로가 1이라는 Flow model의 규칙을 벗어나지 않는다

hgglife