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":

${\begin{bmatrix}{\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{bmatrix}}$

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

${\begin{bmatrix}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{bmatrix}}$

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

$\alpha \,{\begin{bmatrix}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{bmatrix}}+(1-\alpha )\,{\begin{bmatrix}{\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{bmatrix}}={\begin{bmatrix}{\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{bmatrix}}$

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: ${\vec {x}}_{0}=\left\langle 0,1,0,0\right\rangle$

Our next position will be ${\vec {x}}_{1}={\vec {x}}_{0}\,{\hat {P}}$, then ${\vec {x}}_{2}={\vec {x}}_{1}\,{\hat {P}}={\vec {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, $\lim _{n\to \infty }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: ${\vec {x}}_{0}=\left\langle {\frac {1}{4}},{\frac {1}{4}},{\frac {1}{4}},{\frac {1}{4}}\right\rangle$

Bottom line:

${\vec {x}}=\lim _{n\to \infty }{\vec {x}}_{0}\,{\hat {P}}^{n}$

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

Solving the Markov Chain

Recall the equations we came up with last time:

${\begin{aligned}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{aligned}}$

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{aligned}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{aligned}}$

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

As $t\to \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.