CSCE 470 Lecture 11

« previous | Wednesday, September 18, 2013 | next »

Pagerank

Random surfer

Transition Probability Matrix

"If I'm on (row), what's the probability that I will go to (col)" Each row must sum to 1, but what about pages without any outlinks?

When surfer gets bored, magically pick a random page and continue walking. This is called the "I'm bored matrix" or the "teleport matrix":

$\left[\begin{array}{cccc}\frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \end{array}\right]$

Let's use $\alpha$ to represent our "am I not bored?" coin. So I get bored at each page with probability $(1-\alpha )$.

For pages with no outlinks, we'll use a "hack" row from our teleport matrix (since our only way out is to teleport). Thus our "follow link matrix" becomes

$\left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& \frac{1}{2}& \frac{1}{2}\\ 1& 0& 0& 0\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \end{array}\right]$

Now we can apply our "am I bored?" parameter to represent the choices we will make:

$\alpha \left[\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& \frac{1}{2}& \frac{1}{2}\\ 1& 0& 0& 0\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \end{array}\right]+(1-\alpha )\left[\begin{array}{cccc}\frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\\ \end{array}\right]=\left[\begin{array}{cccc}\frac{1}{16}& \frac{13}{16}& \frac{1}{16}& \frac{1}{16}\\ \frac{1}{16}& \frac{1}{16}& \frac{7}{16}& \frac{7}{16}\\ \frac{13}{16}& \frac{1}{16}& \frac{1}{16}& \frac{1}{16}\\ \frac{1}{4}& \frac{1}{4}& \frac{1}{4}& \frac{1}{4}\end{array}\right]$

This shall henceforth be informally known as the "final super mega" matrix.

Markov Property

"I'm forgetful. I forgot where I was. All I know is that I'm here, so what do I do now?"

Formally: Markov chains are stateless; no history

Encode current location as a vector. Suppose the surfer is at B: ${\overrightarrow{x}}_0=⟨0,1,0,0⟩$

Our next position will be ${\overrightarrow{x}}_1={\overrightarrow{x}}_0\hat{P}$, then ${\overrightarrow{x}}_2={\overrightarrow{x}}_1\hat{P}={\overrightarrow{x}}_0{\hat{P}}^2$

We continue to infinity, and our position magically converges. This converged vector becomes our Pagerank

Things to take away

• Now to blow our mind: it doesn't matter where we start, $\underset{n\to \mathrm{\infty }}{\lim }{x}_n$
• If we start with the converged vector, it converges in one step

Since start position actually doesn't matter; we could start simultaneously at all pages: ${\overrightarrow{x}}_0=⟨\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4}⟩$

Bottom line:

$\overrightarrow{x}=\underset{n\to \mathrm{\infty }}{\lim }{\overrightarrow{x}}_0{\hat{P}}^n$

Thus the PageRank vector $\overrightarrow{x}$ is a left eigenvector of the transition matrix $\hat{P}$. (i.e. $\overrightarrow{x}$ is an eigenvector of ${\hat{P}}^T$.)

Solving the Markov Chain

Recall the equations we came up with last time:

$\begin{array}{rl}PR(A)& =\alpha PR(C)+\frac{1-\alpha }{n}\\ PR(B)& =\alpha PR(A)+\frac{1-\alpha }{n}\\ PR(C)& =\alpha PR(B)+\frac{1-\alpha }{n}\\ PR(D)& =\alpha \frac{PR(B)}{2}+\frac{1-\alpha }{n}\end{array}$

The $\frac{1-\alpha }{n}$ represents our teleport probability from our matrix above.

Let's add subscripts to reflect the fact that the values change at each iteration.

$\begin{array}{rl}PR(A{)}_t& =\alpha PR(C{)}_{t-1}+\frac{1-\alpha }{n}\\ PR(B{)}_t& =\alpha PR(A{)}_{t-1}+\frac{1-\alpha }{n}\\ PR(C{)}_t& =\alpha PR(B{)}_{t-1}+\frac{1-\alpha }{n}\\ PR(D{)}_t& =\alpha \frac{PR(B{)}_{t-1}}{2}+\frac{1-\alpha }{n}\end{array}$

We start our 0^th iteration $t=0$ with all pagerank values equal to 1.

As $t\to \mathrm{\infty }$, the values will converge to the same thing as our condition matrix.

Obviously, since the system of equations can be represented as a matrix.