Making the PageRank algorithm

1. Introduction to PageRank

 

• 페이지 A,B,C,D의 연결 관계를 나타내는 행렬 L의 각 행을 구한 것이다.
• 연결된 페이지의 수를 분모로 삼아 다른 페이지로 이어질 확률을 벡터로 표현한다.

 

• 모든 페이지의 랭크가 동일하게 normalise 되었다고 가정하면 랭크 벡터 r은 위와 같다.
• 그리고 페이지의 연결 관계를 확률로 나타낸 벡터 L도 위처럼 표현된다.
• A에 대한 랭크는 페이지 벡터 L과 r의 곱으로 구할 수 있다.
  이때 벡터 r을 반복적으로 곱하며 값을 업데이트한 식은 위와 같다.
  이 반복은 r이 변화를 멈출때까지 계속된다. 결국 r = Lr 이 된다.
• 이 방정식을 풀기 위한 좋은 방정식은 사다리꼴을 만드는 것이지만, 이는 고윳벡터를 알 때만 적용 가능하다.

 

 

 

2. PageRank

 

• PageRank 알고리즘을 풀기 위한 단계를 거치고 실제 코드로 작성해보는 프로그래밍 과제
• 각 페이지들의 연결 관계를 나타내는 행렬 L로부터 시작
• r = Lr 에서 r을 여러번 곱해서, 랭크가 특정 값으로 stablized 되도록 함
• damping facotr D를 포함한 풀이
  이는 기존의 연결 규칙 외를 다루고 있다.

 

 

 

출처: Coursera, Mathematics for Machine Learning: Linear Algebra, Imperial College London