Page Rank

Algorithm behind ranking pages. Main ingredient behind Google Search Engine.

See CS370 and CS451 notes.

CS451

Google’s solution for traps is to teleport to another node with probability $\beta$.

• This is the initial simple code, where we simply accumulate the node’s probabilities. We have higher chance to end up in nodes with higher probabilities

For random jumps, just change the reducer side

In the bespin implementation, we do this

float mass = node.getPageRank() - (float) StrictMath.log(list.size());

CS370

The main formula is $M=\alpha P^{\prime }+(1-\alpha )\frac{1}{R}e{e}^T$

Google uses $\alpha =0.85$

How do you guarantee that there is convergence of page rank?

• You check for the eigenvalues. You can see the remaining values

We have page rank convergence if $M$ is a positive Markov matrix.

$p^{\infty }={\lim }_{k\to \infty }{M}^k{p}^0$