> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/tobigs-graph-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/tobigs-graph-study/chapter11..md).

# Chapter11. Link Analysis: PageRank

## Web as a Graph

#### web graph look like:

![](/files/-M75OjCuTbuDKggivXf2)

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

![](/files/-M75OGoPkcUCYet73wv4)

![](/files/-M75PlMEIndhPXMUeECX)

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

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

#### Web as a directed graph

![](/files/-M75QEK4QLKXaRGlOiEz)

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

#### Directed Graph

1. Strongly connected: 

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

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

![](/files/-M75QmlKxIwZcnP7zyQY)

2\. Directed Acyclic Graph(DAG): 

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

![](/files/-M75QrmvZEFHFZRuYYd7)

**Strongly Connected Component (SCC)**

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

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

![](/files/-M75RAkt86ZIV8JlkNfp)

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

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

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

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

![](/files/-M75RePWyoXwwu8fpfqP)

* 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를 찾는다.

![](/files/-M75SwYWecEc2GhMpiM_)

![](/files/-M75TIVHwm60gOg-7oSu)

따라서, 웹은 매우 큰 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) 이 되게 한다.

![](/files/-M75V4Hdf1w7BHTzD56S)

## 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)는 들어오는 페이지의 중요도에 비례한다. (중요도만큼 투표를 받은 것으로 간주)
* 중요도 **r**j를 가지는 페이지 j가 n개의 out-links를 가진다면, 각 out-links는 **r**j/n 만큼의 중요도를 다른 노드에게 준다.
* 페이지 j의 중요도는 모든 in-links의 값들의 합이다.
* 즉, 노드는 자신의 score에서 out-links의 개수만큼 나눈 값을 다른 노드로 전달한다.

![](/files/-M75WvXDL9XFoWTvMXj8)

노드 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 **r**j 의 정의

* di 는 노드 i의 out-degree (나가는 링크의 개수)이다.
* 노드 i에서 노드 j로 나가는 링크가 존재한다고 가정

![페이지 j에 대한 rank rj](/files/-M75YBYvVva0Y0_-K_XX)

![](/files/-M75_iAj83te4rDMTy34)

![](/files/-M75aJgDvoLmT3b5eBNT)

**PageRank: Matrix Formulation**

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

* 페이지 i가 **d**i 값의 out-links 를 가질 때, 페이지 i에서 j로 링크가 있다면 인접행렬 **M**의 원소 **M**ij=1/**d**i가 되며, 링크가 없다면 해당 원소는 0이 된다.
* 행렬 M은 column stochastic matrix 로 열 벡터의 합은 1이다.

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

* **r**i 는 페이지 i의 중요도 점수이다.   
* 벡터의 원소의 합은 1이다.

![](/files/-M75bIAArC342TDlN-10)

* 페이지 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이라고 한다.

![](/files/-M75djWLHgwb-eF4OqCn)

**Power Iteration Method**

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

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

* N = 웹 페이지 개수

![](/files/-M75e5OoTIjk2C7FK93x)

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

![](/files/-M75eTXkK671wqdfwNpJ)

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

![](/files/-M75iDyXpoLK6n01cazF)

**Random Walk Interpretation**

\- 랜덤 웹 서퍼(random web surfer)

* t 시점에, 어떤 페이지 i를 서핑한다.
* t+1 시점에, 서퍼는 랜덤으로 균일하게 페이지 i로부터 out-link를 따라간다.
* 페이지 i로부터 연결된 페이지 j에서 끝이 난다.
* 무한하게 위의 과정을 반복한다.

![](/files/-M75isW3uBc4LyLZ1p9O)

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

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

\- 고정 분포(The Stationary Distribution)

* t+1 시점에 서퍼가 어디 있는가?
  * 랜덤으로 균일하게 link를 따른다.
  * p(t+1) = M\*p(t)

![](/files/-M75jHX7HHqXUctnqzpo)

* 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로 알려졌는데, 어떤 조건을 만족시키는 그래프에 대해서 고정 분포는 유일하고 초기 확률 분포가 어떻든지 마침내 어떤 상태에 도달할 것이다.  
* 즉, 무한 루프가 아니다.

![](/files/-M75jjLxrzh6FTPjp6gL)

**PageRank: The Google Formulation**     

\- 3가지 질문  

1. 언제 끝나는가? (Does this converge?)
2. 우리가 원할 때 끝나는가? (Does it converge to what we want?)
3. 결과는 합리적인가? (Are results reasonable?) 

문제점

![](/files/-M75k4Fd6pHZgXQYeVlx)

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

* r 벡터는 모두 0이 되는 현상 
* 이런 페이지들은 중요도를 누출시킨다. (leak out) 

![](/files/-M75kDNygkbaXv62ABrA)

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

* 모든 out-links가 그룹 내 에 있어서 외부 링크 벡터가 0이 되는 현상
* 결국 모든 중요도를 없애버린다.

![](/files/-M75kKR5d5RXOQTWaAZC)

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

#### - 해결책: Teleports 

* 구글은 spider trap에 대한 해결책을 제시했다. 각 시점의 스텝마다, 랜덤 서퍼는 2가지 옵션을 갖는 것이다.
  * 𝜷 를 가지고 랜덤으로 링크를 따라간다.
  * 1-𝜷 를 가지고 랜덤 페이지로 점프한다.
  * 𝜷 에 대한 일반적인 값은 0.8 \~ 0.9이다.
* 서퍼는 몇몇 시점에 스텝 시 spider trap에 걸리면 텔레포트(teleport)할 것이다.

![](/files/-M75kYMo6F5dY7b4eg1X)

* dead-end에서 확률 1을 가지고 랜덤으로 링크를 teleport 한다.
  * 이 때 노드의 개수만큼 확률을 나눠갖기 때문에 1이 분산된다.

![](/files/-M75khJG38KiL3vZFG6W)

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

* Spider-traps 은 문제는 아니지만, 트랩이 있는 PageRank의 score는 원하던 것이 아니다. 유한한 숫자만큼 이동(steps)하면 spider trap 으로부터 teleport 할 수 있다.
* Dead-ends 는 문제가 맞다. 행렬은 [column stochastic ](https://ko.wikipedia.org/wiki/%EB%A7%88%EB%A5%B4%EC%BD%94%ED%94%84_%ED%96%89%EB%A0%AC)이 아니어서, 초기 추측값이 다를 수 있다. 항상 갈 곳이 달리 없을 때 teleport해주어서 행렬의 column stochastic을 만들 수 있다.

#### - Random Teleport: 구글의 해결책

* 각 단계에서 랜덤 서퍼가 가지는 두 가지 옵션
  * 𝜷 를 가지고 랜덤으로 링크를 따라간다.
  * 1-𝜷 를 가지고 랜덤 페이지로 점프한다.

![](/files/-M75nMwwexfeiUpbLizr)

-Google Matrix

![](/files/-M75nTgWiBnCtO_Mm9b8)

* NxN 행렬은 모든 원소가 1/N 이다.
* 재귀적인 문제: r = A\*r
* Power method 가 여전히 잘 동작한다.
* 𝜷 에 대한 정의
  * 실제로 0.8, 0.9 이다.

![](/files/-M75nbl5wSBEt6ilt4Nz)

**PageRank 계산하는 방법**

\- matrix-vector multiplication  

![](/files/-M75niYkLnryecIyxAz4)

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

* N = 1 billion pages 
* 각 원소마다 4바이트가 필요하고, r 벡터가 2 billion 개의 원소를 가진다면 대략 벡터 r 이 2개이므로 8 GB 가 필요하다. 
* 행렬 A 는 N\*N 개의 원소를 갖게된다.  

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

![](/files/-M75npZ4_H2_KsIMUeYu)

#### - random teleport  

* 페이지 i에서 모든 다른 페이지까지 teleport link를 추가하고 이동 확률(transition probability)을 (1-𝜷)/N 으로 설정한다.  
* 각 out-link 를 1/|di| 에서 𝜷/|di| 로 확률을 줄인다. 
  * 전체에서 𝜷를 곱한 게 전체가 되었으므로 그만큼 값이 분산된다.  
* 각 페이지의 점수에 (1-𝜷) 를 곱하고 다시 분배한다. 
  * 모든 웹페이지의 Rank Score 에서 (1-𝜷) 만큼 받아서 전체로 다시 분배(동일하게 나눠줌) 

![](/files/-M75oqEsfTbn687AvsO1)

-Sparse Matrix Formulation

![](/files/-M75p0pzsHMmAPp0QqkP)

* 행렬 M은 sparse matrix이지만 dead-ends가 없다.
  * 각 노드에 10개의 link가 있으면 M의 원소의 개수는 10N 으로 근사한다.
* 매 반복마다 새로운 벡터 r을 계산해야 하고, 상수값을 새 벡터 r 에 더해주어야 한다.

![](/files/-M75p7ytUKI9SppfSLEF)

## 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를 낸다.

![](/files/-M75wQf76xZUdVbvhVcf)