# Chapter11. Link Analysis: PageRank ## Web as a Graph #### web graph look like: ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75OjCuTbuDKggivXf2%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.01.44.png?alt=media\&token=182a0a43-d20f-4504-b33c-23a4ddd290e0) 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 ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75OGoPkcUCYet73wv4%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%209.59.43.png?alt=media\&token=ed0ddc34-49e4-46f5-87d1-7c4e8e84c1fa) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75PlMEIndhPXMUeECX%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.06.17.png?alt=media\&token=92bb8b08-7fb1-416a-be2d-8daf13101a97) 초기 웹 링크는 방향을 알려주는 역할(navigational)이었다. 오늘날 많은 링크는 교류하는 역할(transactional)이다. #### Web as a directed graph ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75QEK4QLKXaRGlOiEz%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.08.19.png?alt=media\&token=bba2a1a8-b197-4c0b-801d-24ddfee43149) 노드 v가 주어졌을 때 들어오는 링크는 incoming link, 나가는 링크는 outcoming link로 정의된다. #### Directed Graph 1. Strongly connected: 어떤 노드도 다른 노드에 도달할 수 있는 path가 존재 In(A)=Out(A)={A,B,C,D,E} ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75QmlKxIwZcnP7zyQY%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.10.44.png?alt=media\&token=a1f1acb7-82eb-42e7-8c62-3a29c54c3c5d) 2\. Directed Acyclic Graph(DAG): 사이클이 없는 그래프, 노드 u는 v에 도달해도 노드 v는 u에 도달하지 않음 ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75QrmvZEFHFZRuYYd7%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.11.06.png?alt=media\&token=77450be3-c1eb-4de3-9154-fc77cf5f3fa6) **Strongly Connected Component (SCC)** \- 집합 S에서 노드들의 모든 쌍이 서로 도달할 수 있다. \- SCC이면서 집합 S를 포함하는 더 큰 집합은 존재하지 않는다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75RAkt86ZIV8JlkNfp%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.12.28.png?alt=media\&token=7706aefe-73bd-4115-8e15-53193df42bb2) 예제: {A, B, C}는 첫번째 조건을 만족하나, {A, B, C, G}가 존재하므로 두번째 조건은 만족하지 못한다. (not SCC) " Fact: Every directed graph is a DAG on its SCCs " 모든 directed graph 는 SCC들의 DAG이다. 즉, 모든 쌍들이 서로 도달할 수 있는 작은 그래프들이 모인 것이라고 볼 수 있다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75RePWyoXwwu8fpfqP%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.14.34.png?alt=media\&token=cde07b0a-0663-4748-8360-34855ccd04cc) * 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를 찾는다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75SwYWecEc2GhMpiM_%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.20.10.png?alt=media\&token=5853058a-10b8-4990-982f-b54c9c420bee) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75TIVHwm60gOg-7oSu%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.21.39.png?alt=media\&token=fc01dbc3-87e1-4c08-8a9f-79e49770d17e) 따라서, 웹은 매우 큰 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) 이 되게 한다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75NWYvZhJfQ8JqYFKs%2F-M75V4Hdf1w7BHTzD56S%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.29.31.png?alt=media\&token=81eab935-b841-4681-afca-0a823d858797) ## 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의 개수만큼 나눈 값을 다른 노드로 전달한다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75W3_8XHN2KKq9bBsj%2F-M75WvXDL9XFoWTvMXj8%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.37.34.png?alt=media\&token=1cf5a82f-91a2-4f4f-ba9b-f7d50ce6f55e) 노드 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](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75W3_8XHN2KKq9bBsj%2F-M75YBYvVva0Y0_-K_XX%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.43.03.png?alt=media\&token=7c5ab524-5d70-4280-9423-f9cca10bdad2) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75W3_8XHN2KKq9bBsj%2F-M75_iAj83te4rDMTy34%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.54.08.png?alt=media\&token=fc810762-d7d6-4f74-aad8-fdf28d4ab213) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75W3_8XHN2KKq9bBsj%2F-M75aJgDvoLmT3b5eBNT%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2010.56.46.png?alt=media\&token=4c0b75fd-f6a7-4e2e-82fb-8d86025a1e76) **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이다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75arkx5RSBLwAr-FtY%2F-M75bIAArC342TDlN-10%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.01.03.png?alt=media\&token=40f999da-4644-44e8-96d5-6cd5cd37cea1) * 페이지 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이라고 한다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75djWLHgwb-eF4OqCn%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.11.43.png?alt=media\&token=7408ec11-29d9-44a7-893e-161be97b0b92) **Power Iteration Method** \- n개의 노드를 갖는 웹 그래프가 주어질 때, 노드들은 페이지를 의미하고 간선은 하이퍼링크를 의미한다. \- Power iteration: 단순 반복 계획(a simple iterative scheme) * N = 웹 페이지 개수 ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75e5OoTIjk2C7FK93x%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.13.16.png?alt=media\&token=78d2fd74-af7a-4666-97f0-d7151d0ae615) 초기화 단계에서 N으로 나누는 것은 모든 페이지들이 평등하단 의미이다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75eTXkK671wqdfwNpJ%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.14.55.png?alt=media\&token=702a7a38-2304-4b6b-bc3f-99ffe0213d2a) Power iteration은 가장 큰 eigenvalue에 대응하는 벡터인, dominant eigenvector를 찾는 방법 ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75iDyXpoLK6n01cazF%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.31.20.png?alt=media\&token=5ee45ee3-1b0a-45e4-9a2f-03d756b1c613) **Random Walk Interpretation** \- 랜덤 웹 서퍼(random web surfer) * t 시점에, 어떤 페이지 i를 서핑한다. * t+1 시점에, 서퍼는 랜덤으로 균일하게 페이지 i로부터 out-link를 따라간다. * 페이지 i로부터 연결된 페이지 j에서 끝이 난다. * 무한하게 위의 과정을 반복한다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75isW3uBc4LyLZ1p9O%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.34.10.png?alt=media\&token=b7316e98-4092-4daa-8471-5f42f9495032) \- p(t) = 서퍼가 t 시점에 페이지 i에 있음을 증명하는 i번째 좌표를 가진 벡터 \- p(t)는 페이지에 대한 확률 분포이다. \- 고정 분포(The Stationary Distribution) * t+1 시점에 서퍼가 어디 있는가? * 랜덤으로 균일하게 link를 따른다. * p(t+1) = M\*p(t) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75jHX7HHqXUctnqzpo%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.35.54.png?alt=media\&token=1f168d3f-ff93-47a9-ace7-304632c6d04f) * 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로 알려졌는데, 어떤 조건을 만족시키는 그래프에 대해서 고정 분포는 유일하고 초기 확률 분포가 어떻든지 마침내 어떤 상태에 도달할 것이다. * 즉, 무한 루프가 아니다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75jjLxrzh6FTPjp6gL%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.37.55.png?alt=media\&token=b5bf0c44-e572-4453-8802-af5ff2e15657) **PageRank: The Google Formulation** \- 3가지 질문 1. 언제 끝나는가? (Does this converge?) 2. 우리가 원할 때 끝나는가? (Does it converge to what we want?) 3. 결과는 합리적인가? (Are results reasonable?) 문제점 ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75k4Fd6pHZgXQYeVlx%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.39.25.png?alt=media\&token=a518e05d-d981-4a28-b88a-4e0c762e64be) 1.Dead end: 어떤 페이지들은 out-links를 갖지 않아, random walk는 갈 곳이 없다. * r 벡터는 모두 0이 되는 현상 * 이런 페이지들은 중요도를 누출시킨다. (leak out) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75kDNygkbaXv62ABrA%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.40.03.png?alt=media\&token=27df585b-044e-40c8-a8e4-9be966f25358) 2.Spider trap: random walk가 트랩에 빠지는 현상 * 모든 out-links가 그룹 내 에 있어서 외부 링크 벡터가 0이 되는 현상 * 결국 모든 중요도를 없애버린다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75kKR5d5RXOQTWaAZC%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.40.31.png?alt=media\&token=1f805527-be2e-4e7e-8829-8a6e6192d64b) 노드 m에 도달하면 계속 m에 대한 링크만 타고 가게 된다. (trapped) #### - 해결책: Teleports * 구글은 spider trap에 대한 해결책을 제시했다. 각 시점의 스텝마다, 랜덤 서퍼는 2가지 옵션을 갖는 것이다. * 𝜷 를 가지고 랜덤으로 링크를 따라간다. * 1-𝜷 를 가지고 랜덤 페이지로 점프한다. * 𝜷 에 대한 일반적인 값은 0.8 \~ 0.9이다. * 서퍼는 몇몇 시점에 스텝 시 spider trap에 걸리면 텔레포트(teleport)할 것이다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75kYMo6F5dY7b4eg1X%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.41.28.png?alt=media\&token=e2fcd306-4be9-44e7-ad94-147e9fd54789) * dead-end에서 확률 1을 가지고 랜덤으로 링크를 teleport 한다. * 이 때 노드의 개수만큼 확률을 나눠갖기 때문에 1이 분산된다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75khJG38KiL3vZFG6W%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.42.09.png?alt=media\&token=ffd2213e-0c7f-466d-ad5a-9297242b01ef) \- 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-𝜷 를 가지고 랜덤 페이지로 점프한다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75nMwwexfeiUpbLizr%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.53.48.png?alt=media\&token=76c3b090-8dc1-4c75-9d0f-4ad5605992e5) -Google Matrix ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75nTgWiBnCtO_Mm9b8%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.54.14.png?alt=media\&token=88e26ee9-842a-45de-a003-0e0932d31791) * NxN 행렬은 모든 원소가 1/N 이다. * 재귀적인 문제: r = A\*r * Power method 가 여전히 잘 동작한다. * 𝜷 에 대한 정의 * 실제로 0.8, 0.9 이다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75nbl5wSBEt6ilt4Nz%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.54.51.png?alt=media\&token=beb19deb-bc4f-4d85-8bd4-7e467701a16f) **PageRank 계산하는 방법** \- matrix-vector multiplication ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75niYkLnryecIyxAz4%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.55.20.png?alt=media\&token=24814228-e403-4aae-902d-d1379458f989) \- 충분한 메모리를 가진다면 쉬우나, 실제로 행렬 A와 벡터 r은 매우 크다. * N = 1 billion pages * 각 원소마다 4바이트가 필요하고, r 벡터가 2 billion 개의 원소를 가진다면 대략 벡터 r 이 2개이므로 8 GB 가 필요하다. * 행렬 A 는 N\*N 개의 원소를 갖게된다. \- Matrix Formulation: N개의 페이지들이 있을 때, out-links 를 di 개 가지고 있는 페이지 i가 있다면 다음과 같은 공식이 성립한다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75npZ4_H2_KsIMUeYu%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%8C%E1%85%A5%E1%86%AB%2011.55.49.png?alt=media\&token=649c99bf-588a-49c4-8ed6-78d1b45618d4) #### - random teleport * 페이지 i에서 모든 다른 페이지까지 teleport link를 추가하고 이동 확률(transition probability)을 (1-𝜷)/N 으로 설정한다. * 각 out-link 를 1/|di| 에서 𝜷/|di| 로 확률을 줄인다. * 전체에서 𝜷를 곱한 게 전체가 되었으므로 그만큼 값이 분산된다. * 각 페이지의 점수에 (1-𝜷) 를 곱하고 다시 분배한다. * 모든 웹페이지의 Rank Score 에서 (1-𝜷) 만큼 받아서 전체로 다시 분배(동일하게 나눠줌) ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75oqEsfTbn687AvsO1%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%2012.00.14.png?alt=media\&token=ac6b017c-85ad-47cf-98c1-1b56edacde49) -Sparse Matrix Formulation ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75p0pzsHMmAPp0QqkP%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%2012.01.02.png?alt=media\&token=47dfa3e8-7565-4439-821a-95431b89e37b) * 행렬 M은 sparse matrix이지만 dead-ends가 없다. * 각 노드에 10개의 link가 있으면 M의 원소의 개수는 10N 으로 근사한다. * 매 반복마다 새로운 벡터 r을 계산해야 하고, 상수값을 새 벡터 r 에 더해주어야 한다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75dP4R597EHbZ4S1bC%2F-M75p7ytUKI9SppfSLEF%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%2012.01.30.png?alt=media\&token=bf816f7b-6200-4101-9a4a-f3a2901da15e) ## 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를 낸다. ![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M75rQZ4ECQdjRr_6LUn%2F-M75wQf76xZUdVbvhVcf%2F%E1%84%89%E1%85%B3%E1%84%8F%E1%85%B3%E1%84%85%E1%85%B5%E1%86%AB%E1%84%89%E1%85%A3%E1%86%BA%202020-05-12%20%E1%84%8B%E1%85%A9%E1%84%92%E1%85%AE%2012.33.22.png?alt=media\&token=dffd6890-2d41-4b2d-b5a6-90ac9f32e977)