Mini-Project #3 PageRank
Due November 17 at 11:55pm
Motivation
Please read the following papers on Google and PageRank: [Link] [Link]
Implementation
Were given a directed web graph (If we were to implement a full search engine, we would have a web crawler generate this graph), where each node represents a website and each edge a link, and we would like to know the order of importance of the websites in this graph. Imagine a web surfer that obeys the following surng pattern. dampingFactor is a xed positive real number strictly smaller than 1: 1. Go to a random page on the web graph. 2. If the page contains no links, go to step 1 3. Pick a random number between 0 and 1 (a) If the number is greater than dampingFactor, go to step 1 (b) Otherwise i. Click on a randomly chosen link on this page ii. Go to step 2 The PageRank of a website indicates the probability that this hypothetical web surfer is visiting the aforementioned site at any given moment. It provides a simple, yet powerful way to gauge the importance or popularity of a given website. It is possible to calculate the PageRank of a set of websites in several ways. We will be using the power method, a popular and fast approximation method. Let N be the number of nodes in our web graph. Let Q be an N N matrix such that Qi,j is the probability that the web surfer described above navigates immediately to page i after page j . 1
For example, for the following web graph
and a damping factor of 0.9, we have the matrix 0 0 1/3 Q =dampingF actor 1/3 1/3 1 1 (1 dampingF actor) + 1 5 1 1 0 1/2 0 1/2 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1
If we have N websites on our web graph, we compute the PageRank vector p as follows: p(0) =Q u
p(1) =Q p(0) p
(k )
=Q p(k1)
where u is a uniform probability vector of length N (a vector consisting of the number 1/N repeated N times). The sequence p(0) p(k) will convergence to the dominant eigenvector of matrix Q which is the expected solution of the pagerank problem. Notice that, for testing purposes, p should be normalized, i.e. the sum of its elements should be equal to 1. Your program should return an approximation of the vector p in the form of a Rail of Doubles and will be expected to be within epsilon distance of the correct solution p. 2
Logistics
We will be testing your program on spicerack using two places with X10_NTHREADS set to 24 in each place. The testbench will parse a test conguration from le and invoke your solver method. The format of a conguration le is explained inside the test conguration le provided. As usual include a WRITEME with your design choices. *Only submit solver.x10 and [Link] on Courseworks* inside a zip or tar le with the usual naming convention.