[Week 5-2] 🔗페이지랭크 알고리즘

5주차 화요일

• 페이지랭크의 정의
• 페이지랭크 점수 계산

---

📝[페이지랭크의 정의]

웹은 웹페이지(정점)와 하이퍼링크(간선)로 구성된 거대한 방향 있는 그래프다.

초창기 검색 엔진에서는 웹을 예술, 뉴스, 교육, 건강 등 거대한 디렉토리로 정의하고자 했다. 하지만 웹 페이지의 수가 증가함에 따라 카테고리의 수와 깊이도 무한정 커지고 카테고리의 구분이 모호한 경우도 있어 저장과 검색에 어려움이 생기게 되었다. 또다른 시도로 사용자가 검색한 키워드가 많이 포함되어 있는 웹페이지를 반환하는 방법도 사용되었는데, 검색 유도를 목적으로 특정 키워드를 일부러 많이 넣어 놓은 관련 없는 웹 페이지가 검색되는 단점이 있다.

구글의 창업자 래리 페이지와 세르게이 브린이 논문 The PageRank Citation Ranking: Bringing Order to the Web, 1999 에서 소개한 PageRank 알고리즘이 이 문제를 개선했다.

• 페이지랭크 : 투표
  페이지랭크의 핵심 아이디어는 투표다. 투표를 통해 사용자 키워드와 관련이 높으며 신뢰할 수 있는 웹 페이지를 찾는다. 투표의 주체는 웹 페이지로, 하이퍼링크를 통해 투표하게 된다. 어떤 웹 페이지 u가 v로의 하이퍼링크를 포함하고 있다면 u의 작성자는 v가 관련 있고 신뢰할 수 있는 페이지라고 생각했을 것이다. 따라서 u가 v에게 투표한 것이 된다. 하이퍼링크는 간선이므로, 들어오는 간선이 많을수록 신뢰할 수 있다고 볼 수 있겠다. 그러나 웹 페이지를 여러 개 만들거나 sns 가짜 계정을 많이 만들어 팔로우하는 등 간선의 수를 조작할 가능성이 있기 때문에 악용을 막기 위해 가중 투표를 적용하여 관련성이 높고 신뢰할 수 있는 웹 페이지의 투표를 더 중요한 것으로 간주한다.
  
  주목할 만한 점은 투표를 통해 측정하고자 하는 관련성과 신뢰성 정보를 투표에 사용한다는 것으로, 재귀적인 연립방정식을 통해 계산할 수 있다.
  
  측정하려는 웹 페이지의 관련성과 신뢰도를 페이지랭크 점수라고 부른다. 각 웹 페이지는 나가는 이웃들에게 자신의 (페이지랭크 점수/나가는 이웃의 수) 만큼의 가중치로 투표한다. 각 웹 페이지의 페이지랭크 점수는 받은 투표의 가중치 합으로 정의된다.
  

• 페이지랭크 : 임의 보행
  임의 보행을 통해 웹을 탐색(현재 페이지의 하이퍼링크 중 하나를 균일한 확률로 클릭)하는 웹 서퍼를 가정하면 웹 서퍼가 t번째로 방문한 웹 페이지가 i일 확률을 p_i(t)로 정의할 수 있다. 이 때 p(t)는 길이가 웹 페이지 수인 확률분포 벡터가 된다. 이를 통해 웹 서퍼가 t+1번째로 방문한 페이지가 j일 확률도 구할 수 있는데, 이 과정을 무한히 반복하여 t가 무한히 커지면 확률분포 p(t)가 수렴하여 p(t)=p(t+1)=p가 된다. 이 때 수렴한 확률분포 p를 정상 분포라고 부르며, 이것은 투표 관점에서 정의한 페이지 랭크 점수와 동일하다.
  

---

📝[페이지랭크의 계산]

페이지랭크 점수를 계산하기 위해 반복곱(Power iteration)을 사용한다.

• 반복곱

1. 각 페이지 i의 페이지랭크 점수 r_i(0)을 모두 1/웹페이지 수 로 초기화한다.
2. 각 페이지의 페이지랭크 점수를 갱신한다.
3. 페이지랭크 점수가 수렴(r(t)와 r(t+1)이 충분히 유사해짐)하였으면 종료, 수렴하지 않았으면 2번 과정으로 돌아가 반복한다.
   
   그러나 반복곱 알고리즘은 '항상', '합리적인' 점수로 수렴하는 것을 보장할 수 없다. 들어오는 간선은 있지만 나가는 간선이 없는 막다른 정점을 만나면 페이지랭크 점수가 0으로 수렴하며, 들어오는 간선은 있지만 나가는 간선이 없는 정점의 집합인 스파이더 트랩에 빠진 경우에는 페이지랭크 점수가 수렴하지 않는다.
   
   

• 순간이동
  이 문제를 해결하기 위해 순간이동을 도입했는데, 웹 상을 임의 보행하는 웹 서퍼의 행동을 다음과 같이 수정하였다.
  
  1. 현재 페이지에 하이퍼링크가 없다면 임의의 웹 페이지로 순간이동한다.
  2. 현재 페이지에 하이퍼링크가 있다면 앞면이 나올 확률이 α인 동전을 던진다.
  3. 앞면이 나왔다면 하이퍼링크 중 하나를 균일한 확률로 선택해 클릭한다.
  4. 뒷면이 나왔다면 임의의 웹페이지로 순간이동한다.

순간이동을 적용하면 막다른 정점이나 스파이더 트랩에 갇히는 일이 없어진다. 페이지랭크 점수를 구하는 수식은 다음과 같이 바뀐다.