How does PageRank deal with nodes that do not have out-links?

176 Views Asked by At

I will use the notation that $A_{ij}=1$ if an arrow exists from $j$ to $i$ and otherwise zero. Just to avoid confusion I use in brackets the standard convention $B_{ij}=1$ when $i$ has a directed arrow to $j$.

As far as I can understand the non-damping version of PageRank goes like this: \begin{equation} r_a(t+1)=\sum_b A_{ab} \frac{r_b(t)}{\sum_{c}A_{cb}} \qquad \Big(\;r_a(t+1)=\sum_{b}\frac{r_b(t)}{\sum_{c}B_{bc}}B_{ba}\;\Big) \end{equation} I guess one may use the Brower fixed point theorem to conclude that there exists a fixed point and that $\boldsymbol r$ converges to one of them. However this only holds under the assumption that the map is continuous, which might not be the case when there are divisions by zero.

Question: What happens when a node doesn't have any out-links? Then we are technically in trouble because of the division by zero.

Consider the example: \begin{equation} A=\left[\begin{array}{cc} 0 & 0\\ 1 & 0 \end{array} \right] \qquad \Bigg( B=\left[\begin{array}{cc} 0 & 1\\ 0 & 0 \end{array} \right] \Bigg) \end{equation} Then after the first round of iterations (initializing at $r_1(0)=r_2(0)=1/2$), we get: \begin{align} r_1(1)&=0\frac{r_2(0)}{0}\\ r_2(1)&=r_1(0) \end{align}

The only way to resolve this issue is to set $\frac{0}{0}$ to one in this case. I don't know whether it resolves the issue in general, but it definitely doesn't yield the intuitive result of giving preference to the receiving node. Furthermore it doesn't converge in general! In this case it converges only for $r_1(0)=r_2(0)=1/2$.