PageRank

Pagerank is a measure of a node's "popularity" within a graph.

Rationale

Random graph for PageRank

Consider the directed graph at right.

If we start on node $A$ and choose to follow an edge at random, we will land on $B$ or $C$ with equal probability $P_{B}=P_{C}=0.5$. If we choose to follow a link again, we will arrive at $D$, $B$, or $A$ with the following probabilities:

• $P_{A}=0.25$
• $P_{B}=0.25$
• $P_{D}=0.5$

The process can be repeated indefinitely, and the probabilities will converge to a stable value. These values are the PageRank values of the nodes.

Mathematical Representation

Positional Probability

We choose to represent the probabilities of arriving at a node as a vector. Using the example above with coordinates for $A$, $B$, $C$, and $D$ in that order, we can represent the probabilities as follows:

• Starting at node $A$: $\left\langle 1,0,0,0\right\rangle$
• After one step: $\left\langle 0,0.5,0.5,0\right\rangle$
• After two steps: $\left\langle 0.25,0.25,0,0.5\right\rangle$

Graph Traversal (Transformation)

Let ${\vec {x}}_{0}$ be a probability vector as described above. The steps taken in determining the probability resulting from graph edge traversal be described by multiplication by a $n\times n$ matrix so that ${\vec {x}}_{1}=T\,{\vec {x}}_{0}$. The cells of this matrix represent the relative probability of following edges to other nodes, hence we shall call it the transformation probability matrix, although it will be shown later that this matrix requires some modification in order to work correctly.

Here we choose to represent the cell $T_{ij}$ as the probability of arriving at node $i$ if we were originally on node $j$. Observe that the sum of each column of this matrix is 1. Continuing with our running example, the initial transformation probability matrix for the above example is given by:

${\begin{bmatrix}0&0&0.5&0\\0.5&0&0.5&0\\0.5&0&0&1\\0&1&0&0\end{bmatrix}}$

Dead-Ends and Cycles

There is a slight problem with the transformation probability matrix representation above. If there are "dead-end" nodes in the graphs (i.e. no out-edges), then no more steps can be taken once those nodes are reached. If we represent this as a self-loop edge on the node, then the probability limit will eventually converge to only these dead-end nodes.

To alleviate this problem, we introduce an additional transformation matrix that represents the probability of jumping from any node to any other node. This is an $n\times n$ matrix whose values are all ${\frac {1}{n}}$:

${\frac {1}{n}}\,M_{n}\left(1\right)={\frac {1}{n}}\,{\begin{bmatrix}1&\dots &1\\\vdots &\ddots &\vdots \\1&\dots &1\end{bmatrix}}={\begin{bmatrix}{\frac {1}{n}}&\dots &{\frac {1}{n}}\\\vdots &\ddots &\vdots \\{\frac {1}{n}}&\dots &{\frac {1}{n}}\end{bmatrix}}$

This matrix also has the property that all column sums are 1. For the example above, the "teleport" transformation matrix is:

${\begin{bmatrix}0.25&0.25&0.25&0.25\\0.25&0.25&0.25&0.25\\0.25&0.25&0.25&0.25\\0.25&0.25&0.25&0.25\end{bmatrix}}$

Definition

Taking a weighted linear combination of the two transformation matrices given above with weight parameter $\alpha$ produces an adjusted transformation probability matrix. This parameter $\alpha$ represents the probability that the position randomly teleports from the current node to any other node in the graph.

${\hat {T}}=(1-\alpha )\,T+{\frac {\alpha }{n}}\,M_{n}(1)$

Starting at a positional probability vector ${\vec {x}}_{n}$, we define the process of taking a randomized single step in graph traversal as

${\vec {x}}_{n+1}={\hat {T}}\,{\vec {x}}_{n}$

Since the PageRank vector ${\hat {x}}$ is the converged positional probability vector, we can write

${\hat {x}}={\vec {x}}_{\infty }={\hat {T}}^{\infty }\,{\vec {x}}_{0}$

However, this limit is usually not feasible to evaluate, so we employ the following property: Assuming ${\vec {x}}$ is the converged PageRank vector, we have

${\vec {x}}{=}{\hat {T}}\,{\vec {x}}$

Hence ${\vec {x}}$ is a right eigenvector of ${\hat {T}}$ for eigenvalue $\lambda =1$