Chapter11. Link Analysis: PageRank

투빅스 12기 배유나

Web as a Graph

web graph look like:

web

-> directed graph로 표현된다.

-> strongly connected components 그래프 이론 사용

-> computational experiment : in- out components of given node v

-> structure of the web : BOWTIE

web as a graph:

• Nodes = web pages

• Edges = hyperlinks

초기 웹 링크는 방향을 알려주는 역할(navigational)이었다.

오늘날 많은 링크는 교류하는 역할(transactional)이다.

Web as a directed graph

노드 v가 주어졌을 때 들어오는 링크는 incoming link, 나가는 링크는 outcoming link로 정의된다.

Directed Graph

1. Strongly connected:

어떤 노드도 다른 노드에 도달할 수 있는 path가 존재

In(A)=Out(A)={A,B,C,D,E}

2. Directed Acyclic Graph(DAG):

사이클이 없는 그래프, 노드 u는 v에 도달해도 노드 v는 u에 도달하지 않음

Strongly Connected Component (SCC)

- 집합 S에서 노드들의 모든 쌍이 서로 도달할 수 있다.

- SCC이면서 집합 S를 포함하는 더 큰 집합은 존재하지 않는다.

예제: {A, B, C}는 첫번째 조건을 만족하나, {A, B, C, G}가 존재하므로 두번째 조건은 만족하지 못한다. (not SCC)

" Fact: Every directed graph is a DAG on its SCCs "

모든 directed graph 는 SCC들의 DAG이다.

즉, 모든 쌍들이 서로 도달할 수 있는 작은 그래프들이 모인 것이라고 볼 수 있다.

• SCC는 그래프 G의 노드들을 분할한다.(partition) → 각 SCC를 노드로 본다.

• SCC를 노드로 보는 그래프 G`이 있을 때, G`은 DAG 이다.

Graph Structure of the Web

웹의 큰 스냅샷을 살펴보면, 어떻게 SCC들이 DAG로 서로 맞춰있는지 이해할 수 있다.

Computational Issues:

SCC가 노드 v를 포함하는 것을 어떻게 발견?

• In(v): 노드 v로 들어오는 노드들의 집합

• Out(v): 노드 v로부터 도달가능한 노드들의 집합

• SCC 에 노드 v가 포함되면, Out(v)와 In(v)의 교집합에 노드 v가 있다.

• 위 방법은 연산이 많이 걸리므로 Out(v,G)와 Out(v, 방향을 뒤집은 G)의 교집합으로 노드 v를 찾는다.

따라서, 웹은 매우 큰 SCC 이다.

Structure of the Web

초기 웹은 데이터베이스에 링크나 url을 저장해둔 형태로 서버는 12GB의 메모리를 가졌었다.

Directed version of the Web graph

랜덤 노드 v 에서 In(v), Out(v) 계산. 결과

• 가장 큰 SCC: 노드들 중 28%가 해당된다. (56 million)

• 랜덤으로 노드 v를 가져오는 것은 Out(v) ~ 50% (100 million), In(v) ~ 50% (100 million) 이 되게 한다.

How to Organize the web PageRank (aka the Google Algorithm)

- 실제 웹은 너무 거대하며, 신뢰되지 않는 문서들이 매우 많다. 스팸도 그러하다.

- 검색 엔진의 2가지 난제

• 웹은 많은 정보를 포함한다. 신뢰(trust)에 대한 정보를 어떻게 알 수 있나?

  • 신뢰있는 페이지들은 서로서로 참조할 것이다.

• (키워드)“newspaper”를 질의할 때 최고의 대답(검색결과)는 무엇인가?

  • newspaper에 대해 실제로 아는 페이지들은 많은 newspaper들을 참조하고 있을 것이다.

Ranking Nodes on the Graph

• 모든 웹 페이지는 동등하게 중요하지 않다.

• 웹 그래프 노드 연결성에 대해 많은 다양성이 있다.

• 링크 구조에 따라 페이지들에 등급을 매길 수 있다.

-> So, let’s rank the pages using the web graph link structure!

Link Analysis Algorithms

그래프에서 노드의 중요도(importances or score)를 계산하기 위한 접근법

1. Page-Rank

2. Topic-Specific (Personalized) Page-Rank

3. Web Spam Detection Algorithms

" Links as Votes "

• 페이지는 많은 링크를 가질수록 중요해진다.

  • In-coming links: 노드로 들어오는 링크

  • Out-going links: 노드에서 나가는 링크

• in-links를 (다른 페이지로부터 받는) 투표로 보기

  • 예를 들어, 스탠포드 대학 사이트는 23,400 의 in-links를 가진다.

  • in-links가 많은 노드로부터 in-links를 받는 노드는 중요도가 더 높은 링크를 갖는다.

    • 인기있는 웹페이지로부터 참조를 받으면 다른 링크보다 중요도가 더 높아진다.

• 재귀적으로 in-links의 근원지(source)를 찾아 링크마다 scoring

  • page에서 오는 links를 중요한 page일수록 더 카운팅한다.

Page-Rank : The "Flow" Model

A “vote” from an important page is worth more:

• 각 링크의 투표(vote)는 들어오는 페이지의 중요도에 비례한다. (중요도만큼 투표를 받은 것으로 간주)

• 중요도 rj를 가지는 페이지 j가 n개의 out-links를 가진다면, 각 out-links는 rj/n 만큼의 중요도를 다른 노드에게 준다.

• 페이지 j의 중요도는 모든 in-links의 값들의 합이다.

• 즉, 노드는 자신의 score에서 out-links의 개수만큼 나눈 값을 다른 노드로 전달한다.

노드 k에 out-links의 개수는 4이기 때문에, 노드 k의 각 out-links의 값은 노드 k의 중요도 / 4 이다.

노드 i에서 out-links의 개수는 3이기 때문에, 노드 i의 각 out-links의 값은 노드 i의 중요도 / 3 이다.

노드 j에서 in-links는 노드 i와 k에서 오는 것만 있으므로, 중요도는 (노드 k의 중요도 / 4) + (노드 i의 중요도 / 3)이 된다.

- 중요한 페이지에서 투표값(score or vote)은 더욱 가치가 있다. 한 페이지는 다른 중요한 페이지들로부터 참조되면 더욱 중요해진다.

- 페이지 j에 대한 rank rj 의 정의

• di 는 노드 i의 out-degree (나가는 링크의 개수)이다.

• 노드 i에서 노드 j로 나가는 링크가 존재한다고 가정

페이지 j에 대한 rank rj

PageRank: Matrix Formulation

확률론적 인접 행렬(Stochastic adjacency matrix)

• 페이지 i가 di 값의 out-links 를 가질 때, 페이지 i에서 j로 링크가 있다면 인접행렬 M의 원소 Mij=1/di가 되며, 링크가 없다면 해당 원소는 0이 된다.

• 행렬 M은 column stochastic matrix 로 열 벡터의 합은 1이다.

- Rank Vector r: 원소가 페이지당 rank 에 해당되는 벡터

• ri 는 페이지 i의 중요도 점수이다.

• 벡터의 원소의 합은 1이다.

• 페이지 i의 score 를 페이지 i에서 j로 이동한 out-going link 의 개수로 나누면 노드 j의 score를 구할 수 있다.

- Eigenvector Formulation: rank vector r은 학률론적 웹 행렬(stochastic web matrix) M 의 eigenvector 이다.

• 행렬 M은 모두 양수인 원소를 갖는 column stochastic이기 때문에 가장 큰 eigenvalue는 1이다.

• 벡터 r의 길이는 1이며, 행렬 M의 각 컬럼의 합도 1이다.

• 그러나 이 방법은 느리기 때문에 보다 효율적으로 벡터 r을 구해야 한다.

  • 그 방법을 Power Iteration이라고 한다.

Power Iteration Method

- n개의 노드를 갖는 웹 그래프가 주어질 때, 노드들은 페이지를 의미하고 간선은 하이퍼링크를 의미한다.

- Power iteration: 단순 반복 계획(a simple iterative scheme)

• N = 웹 페이지 개수

초기화 단계에서 N으로 나누는 것은 모든 페이지들이 평등하단 의미이다.

Power iteration은 가장 큰 eigenvalue에 대응하는 벡터인, dominant eigenvector를 찾는 방법

Random Walk Interpretation

- 랜덤 웹 서퍼(random web surfer)

• t 시점에, 어떤 페이지 i를 서핑한다.

• t+1 시점에, 서퍼는 랜덤으로 균일하게 페이지 i로부터 out-link를 따라간다.

• 페이지 i로부터 연결된 페이지 j에서 끝이 난다.

• 무한하게 위의 과정을 반복한다.

- p(t) = 서퍼가 t 시점에 페이지 i에 있음을 증명하는 i번째 좌표를 가진 벡터

- p(t)는 페이지에 대한 확률 분포이다.

- 고정 분포(The Stationary Distribution)

• t+1 시점에 서퍼가 어디 있는가?

  • 랜덤으로 균일하게 link를 따른다.

  • p(t+1) = M*p(t)

• p(t+1) = M*p(t) = p(t) 일 때, p(t)는 random walk의 고정 분포이다. 즉, 어떤 상태(state)에 도달한 것이다.

• 원래 rank vector r은 r=M*r을 만족한다. 따라서 r은 random walk에 대한 고정 분포이다.

- 존재와 유일함(Existence and Uniqueness)

• random walk 이론으로부터 주요 결과는 Markov processes로 알려졌는데, 어떤 조건을 만족시키는 그래프에 대해서 고정 분포는 유일하고 초기 확률 분포가 어떻든지 마침내 어떤 상태에 도달할 것이다.

• 즉, 무한 루프가 아니다.

PageRank: The Google Formulation

- 3가지 질문

1. 언제 끝나는가? (Does this converge?)

2. 우리가 원할 때 끝나는가? (Does it converge to what we want?)

3. 결과는 합리적인가? (Are results reasonable?)

문제점

1.Dead end: 어떤 페이지들은 out-links를 갖지 않아, random walk는 갈 곳이 없다.

• r 벡터는 모두 0이 되는 현상

• 이런 페이지들은 중요도를 누출시킨다. (leak out)

2.Spider trap: random walk가 트랩에 빠지는 현상

• 모든 out-links가 그룹 내 에 있어서 외부 링크 벡터가 0이 되는 현상

• 결국 모든 중요도를 없애버린다.

노드 m에 도달하면 계속 m에 대한 링크만 타고 가게 된다. (trapped)

- 해결책: Teleports

• 구글은 spider trap에 대한 해결책을 제시했다. 각 시점의 스텝마다, 랜덤 서퍼는 2가지 옵션을 갖는 것이다.

  • 𝜷 를 가지고 랜덤으로 링크를 따라간다.

  • 1-𝜷 를 가지고 랜덤 페이지로 점프한다.

  • 𝜷 에 대한 일반적인 값은 0.8 ~ 0.9이다.

• 서퍼는 몇몇 시점에 스텝 시 spider trap에 걸리면 텔레포트(teleport)할 것이다.

• dead-end에서 확률 1을 가지고 랜덤으로 링크를 teleport 한다.

  • 이 때 노드의 개수만큼 확률을 나눠갖기 때문에 1이 분산된다.

- Teleport가 문제를 해결하는 이유

• Spider-traps 은 문제는 아니지만, 트랩이 있는 PageRank의 score는 원하던 것이 아니다. 유한한 숫자만큼 이동(steps)하면 spider trap 으로부터 teleport 할 수 있다.

• Dead-ends 는 문제가 맞다. 행렬은 column stochastic 이 아니어서, 초기 추측값이 다를 수 있다. 항상 갈 곳이 달리 없을 때 teleport해주어서 행렬의 column stochastic을 만들 수 있다.

- Random Teleport: 구글의 해결책

• 각 단계에서 랜덤 서퍼가 가지는 두 가지 옵션

  • 𝜷 를 가지고 랜덤으로 링크를 따라간다.

  • 1-𝜷 를 가지고 랜덤 페이지로 점프한다.

-Google Matrix

• NxN 행렬은 모든 원소가 1/N 이다.

• 재귀적인 문제: r = A*r

• Power method 가 여전히 잘 동작한다.

• 𝜷 에 대한 정의

  • 실제로 0.8, 0.9 이다.

PageRank 계산하는 방법

- matrix-vector multiplication

- 충분한 메모리를 가진다면 쉬우나, 실제로 행렬 A와 벡터 r은 매우 크다.

• N = 1 billion pages

• 각 원소마다 4바이트가 필요하고, r 벡터가 2 billion 개의 원소를 가진다면 대략 벡터 r 이 2개이므로 8 GB 가 필요하다.

• 행렬 A 는 N*N 개의 원소를 갖게된다.

- Matrix Formulation: N개의 페이지들이 있을 때, out-links 를 di 개 가지고 있는 페이지 i가 있다면 다음과 같은 공식이 성립한다.

- random teleport

• 페이지 i에서 모든 다른 페이지까지 teleport link를 추가하고 이동 확률(transition probability)을 (1-𝜷)/N 으로 설정한다.

• 각 out-link 를 1/|di| 에서 𝜷/|di| 로 확률을 줄인다.

  • 전체에서 𝜷를 곱한 게 전체가 되었으므로 그만큼 값이 분산된다.

• 각 페이지의 점수에 (1-𝜷) 를 곱하고 다시 분배한다.

  • 모든 웹페이지의 Rank Score 에서 (1-𝜷) 만큼 받아서 전체로 다시 분배(동일하게 나눠줌)

-Sparse Matrix Formulation

• 행렬 M은 sparse matrix이지만 dead-ends가 없다.

  • 각 노드에 10개의 link가 있으면 M의 원소의 개수는 10N 으로 근사한다.

• 매 반복마다 새로운 벡터 r을 계산해야 하고, 상수값을 새 벡터 r 에 더해주어야 한다.

Node Proximity Measurement

범용적인 인기도 대신에, 주제와 관련된 인기 척도를 사용

웹 페이지들이 특정 주제(e.g. “sports” or “history”)와 얼마나 가까운지에 따라 인기도를 계산하는 법

Topic Specific PageRank

• 주제 구체적인, 관련 페이지들의 집합 = teleport set

- 기본 아이디어: random walk 마다 bias를 주기

• 워커가 텔레포트를 할 때, 집합 S로부터 페이지를 선택한다.

• 집합 S는 해당 주제와 관련된 페이지들만 포함한다.

• 집합 S로 매 텔레포트가 발생하면, 매 순간 다른 벡터 r을 얻는다.

• 노드 u로부터 Topic Specific PageRank → teleport set S = {u}

• 노드 u에서 유사도를 측정해서 score를 낸다.