# Page Rank with Apache Spark Graphx

#### What is Page Rank?

The PageRank algorithm outputs a probability distribution used to represent the likelihood that a person randomly clicking on links will arrive at any particular page. PageRank can be calculated for collections of documents of any size. It is assumed in several research papers that the distribution is evenly divided among all documents in the collection at the beginning of the computational process. The PageRank computations require several passes, called "iterations", through the collection to adjust approximate PageRank values to more closely reflect the theoretical true value.

A probability is expressed as a numeric value between 0 and 1. A 0.5 probability is commonly expressed as a "50% chance" of something happening. Hence, a document with a PageRank of 0.5 means there is a 50% chance that a person clicking on a random link will be directed to said document.

Companies run search engine can set the prices for placing ad on a web page based on page rank of the web page, placing ad on higher traffic web pages, conceivably with higher page ranks will cost more.

Below is a simple example:

Suppose you have a website that has 4 pages, there are links from each web pages. For simplicity, just assume these links are static (hard coded links). In the real world, links (URLs) to the web pages are more dynamically rendered for example, rather than hard coded one. Page ranks are actually dynamic, not static, need to be computed anytime when pages and links are rendered.

Looking at page products.html, which has 2 outbound URL links, 1 to index.html and 1 to services.html

Similarly, Index.html has 3 outbound URL links, 1 to products.html, 1 to services.html and 1 to investor.html

Services.html has 1 outbound URL links to products.html

Investor.html has 2 outbound URL links, 1 to products.html and 1 to index.html

Given all other pages have links to products.html, therefore, calculation of PageRank of products.html is denoted as PR(products.html) as below:

PR(products.html)=PR(index.html)/3+PR(services.html)/1+PR(investor.html)/2

Why PR(index.html)/3? Because index.html has 3 outbound links, only 1 pointing to products.html, hence only 1/3 of its PR value contributes to PR(products.html)

Likewise, for PR(services.html)/1 and PR(investor.html)/2

#### Computing Page Rank:

The PageRank algorithm outputs a probability distribution used to represent the likelihood that a person randomly clicking on links will arrive at any particular page. Since it is probability, Page Rank should be anywhere between 0 and 1, right?

Here is the scala code create a random graph of 10 vertices and outputs the page rank for each of the vertices and sort the page rank in descending order

I notice some page rank is > 1. I also notice if I add up all page ranks, it is equal to the number of vertices, by following code:

#### Math Behind Page Rank

Here is from Wikipedia

https://en.wikipedia.org/wiki/PageRank

The PageRank theory holds that an imaginary surfer who is randomly clicking on links will eventually stop clicking. The probability, at any step, that the person will continue is a damping factor d. Various studies have tested different damping factors, but it is generally assumed that the damping factor will be set around 0.85. The damping factor is subtracted from 1 (and in some variations of the algorithm, the result is divided by the number of documents (N) in the collection) and this term is then added to the product of the damping factor and the sum of the incoming PageRank scores.

Formula 1:

This is probability-based Page Rank, because add up all Page Ranks evaluate to 1, Page Rank for each Vertex must be within 0 and 1

However, according to original research paper from Google, the formula to calculate page rank is

(Formula 2):

Formula 2 is Formula 1 times N, meaning, adding up all page ranks evaluating to N, (N is number of web pages or number of vertices in the Graph). Therefore, it is possible for Page Rank for some vertices may be greater than 1, as long as sum up all of the page ranks being equal to N. Hence the page rank by formula 2 is no longer probability value, you can, however, derive the probability by dividing page rank value by N.

#### Spark Graphx Implementation of Page Rank

It is likely pageRank method from Spark Graphx is based on formula 2. To prove it, look at the relevant open source codes that compute page rank of vertex in a Graph:

pageRank is a method exposed in the abstract class Graph:

2. method pageRank is implemented in class GraphOps

3. Actual implementation method runUntilConvergence is in object pageRank:

#### Apache Spark Graphx Open source code reference:

#### Conclusion:

Tracing the code:

pageRank API method in class Graph ->

PageRank.runUntilConvergence in class GraphOps ->

runUntilConvergence in object PageRank ->

runUntilConvergence invokes runUntilConvergenceWithOption in object PageRank ->

runUntilConvergenceWithOption in object PageRank that execute essentially below logic:

Therefore, PageRank implemented by Apache Spark Graphx is:

This is exactly the formula from Google (formula 2):

#### Conclusion

That explains page rank code above produces page rank that can be greater than 1 and total of page rank added together is N (N=number of vertices in the Graph). In fact, whether or not page rank being a probability value is not important, the relative significance of page rank value is. The higher the page rank of a vetex (web page), the more visiting traffic the page is likely to have, therefore, set the price accordingly for anyone placing ads, that is what matters.

Last updated