4강. Link Analysis: PageRank

PageRank

• graph를 matrix로 다룬다.
• Random walk, matrix factorization, node embedding은 서로 밀접하게 관련이 있다.

PageRank

웹 페이지를 그래프로 표현하면 다음과 같다. 이때, nodes = web pages 이고, edges = hyperlinks 이다.

• 어떤 노드가 다른 노드보다 더 중요할까? 즉, 어떤 웹 페이지가 다른 웹 페이지보다 더 중요할까? → 검색 결과로 어떤 웹 페이지를 맨 위에 놓고, 어떤 웹 페이지를 맨 아래에 놓을 지 결정할 수 있다.

Idea: Links as votes

• 링크를 투표로 생각하는 방법으로 웹에서 웹 페이지의 중요성을 계산한다.
• 웹 페이지가 링크를 많이 가질수록 중요한 페이지라고 보는 것이다.
  • in-coming link: 다른 사람이 클릭해서 들어오기 때문에 위조가 어렵다.
  • out-going link: 내가 생성하는 링크이기 때문에 위조가 쉽다.
• in-links를 투표라고 보고 in-links가 많을수록 중요한 웹페이지라고 볼 수 있다. 중요한 웹페이지를 in-links로 가지고 있는 페이지는 중요한 페이지가 되는데, 이는 recursive(재귀적)이다.

The “Flow” Model

• 다른 중요한 페이지가 가리키는 페이지는 중요하다.

연립방정식을 푸는 방법: Matrix Formulation