Proof of the equivalence of PageRank and degree centrality in undirected connected graphs

eigenvalues-eigenvectorsgraph theorypage-rankrandom walkstochastic-processes

Surprisingly, although this is stated everywhere in literature (usually citing surveys), there seems to be no recent source that explicitly proved this statement (there are, however, sources that proved this for a general case where there is damping factor, but the proof cannot be adapted to non-damping scenario).

To define the original problem, suppose that a graph is undirected and connected. Define $d(i)$ as the degree centrality (aka degree) of node $i$, $\mathbf{A}$ the adjacency matrix. Let $\pmb{w}$ denote the PR vector, and consider PageRank where there is no damping factor, i.e.

$$w(i)=\sum_{j}{A_{ij}\frac{w(j)}{d(j)}}$$

Now we want to prove that $w(i)\propto d(i)$, or $\pmb{w}=\alpha \mathbf{D}\cdot\mathbf{1}$, where $\mathbf{D}$ is the degree diagonal matrix.

I know Perron-Fronebius theorem can tackle this, but I am thinking if there could be a more straightforward proof, possibly solving directly the PageRank equations.

Edit 1:

It looks like Perron-Fronebius cannot directly get the work done because we don't have a strictly positive matrix. Perhaps should consider proof by contradiction with Chapman-Kolmogorov equations if proving uniqueness.

Best Answer

I believe we can simply input $w = \alpha \cdot D \cdot \mathbf{1}$ into the equation and check that it works. Note that your equation $$w(i) = \sum_{j} A_{i, j} \frac{w(j)}{d(j)}$$ may be rewritten in matrix terms as: $$\pmb{w}^T = \pmb{w}^T\mathbf{D}^{-1}A$$ Transposing both sides: $$\pmb{w} = A\mathbf{D}^{-1}\pmb{w},$$ as both $A$ and $\mathbf{D}$ are symmetric. Let us insert $\pmb{w} = \alpha \mathbf{D}\cdot \mathbf{1}$ on the right side. $$\pmb{w} = A\mathbf{D}^{-1}\alpha \mathbf{D}\cdot \mathbf{1}$$ $$\pmb{w} = \alpha A \cdot \mathbf{1}$$ Note that $A\cdot\mathbf{1}$ is a vector of degrees, i.e. $(A \cdot\mathbf{1})_i = \sum_j A_{i, j} = d(i)$. So, we got that $$\pmb{w} = \alpha \textbf{D}\cdot1,$$ which confirms our assumption.

Related Question