1. PageRank의 배경
2. PageRank 정의 & 개념
   1. 웹 그래프
   2. PageRank란?
   3. PageRank에 대한 직관
3. Simple PageRank
   1. 투표 (vote) 관점에서의 Simple PageRank
   2. random walk 관점에서의 Simple PageRank
   3. Simple PageRank 관점 정리
   4. Simple PageRank의 계산
   5. Simple PageRank의 문제점
4. Simple PageRank
   1. Spider trap과 ****Dead end의 해결 방법
   2. Simple PageRank 계산 예시
5. PageRank의 결과
   1. Convergence Properties
6. • PageRank를 이해하는 데 필요한 수학
   1. Stochastic matrix
   2. Perron-Frobenius theorem
7. • 질문

1 PageRank의 배경

1.1 PageRank의 배경

• 구글 이전의 검색 엔진은, 사용자가 입력한 키워드에 의존하여, 웹페이지를 반환했습니다.
  • 하지만 이런 검색 엔진은, 취약점이 있습니다.
  • 악성 웹페이지들이 검색 엔진을 속여, 사용자의 검색 키워드에 상관 없이, 사용자들을 자신의 페이지로 오게 만들었습니다.
    • 예를 들어, “운동화" 판매자가 자신의 페이지에, 자신의 “운동화" 판매와 상관 없는 내용들을 (e.g., 영화, 음악, ...), 보이지 않게 (바탕과 똑같은 색깔의 글씨로) 가득 적어놓으면, 검색 엔진은 “영화"를 키워드로 검색에도 “운동화" 판매 페이지를 보여줍니다.
• 구글은, 검색 엔진의 품질을 향상시키기 위해, 웹 그래프 구조 (웹의 link structure)를 사용하는 PageRank 기술을 도입했습니다.

2 PageRank 정의 & 개념

2.1 웹 그래프

• 웹은 node는 웹페이지 이고, edge는 하이퍼링크인 directed graph로 표현할 수 있습니다.

• 예를 들어, 아래의 그림처럼 표현할 수 있습니다.

• (그림 출처: CS224W 4. Link Analysis: PageRank)

  

  • 첫 번째 웹 페이지 (node)의 Networks는 하이퍼링크 (edge)를 포함하고 있습니다.
  • 첫 번째 웹 페이지 (node)의 “Networks”와 같은 단어 (or 문장)을 anchor text라고 합니다.

• (그림 출처: The PageRank Citation Ranking: Bringing Order to the Web (PageRank 논문))

  

2.2 PageRank란?