I am trying to implement PageRank using the power method in Matlab.
I start with a sparse $n\times n$ matrix $\textbf{A}$ where all nonzero values are $1$. $n$ could be very large which is why I am using sparse format.
I then normalize each column of $\textbf{A}$ (with the $L^1$-norm).
Next I apply the algorithm by constructing $\textbf{B}$ where (assuming no column of $\textbf{A}$ is a $0$ vector in this case):
$\textbf{B} = \frac{1-p}{n}\textbf{E} + p\textbf{A}$
where $p$ is a probability and $\textbf{E}$ is a matrix of all ones.
The problem I have is that now B is not a sparse matrix, but I am supposed to multiply B many times in order to do the power method.
I thought the whole point of the PageRank algorithm was to take advantage of the sparse matrix format, but now I have a full matrix.
So my question is, how do I multiply B repeatedly to get the eigenvector if it's a full matrix? How can I avoid constructing B and just deal with sparse matrix multiplication?
Essentially PageRank is trying to solve the eigenvalue problem $r = Br$ where $r\in\mathbf{R}^n$, $\mathbf{1}^Tr = 1$, $r\succeq 0$, and $B\in\mathbf{R}^{n\times n}$ is the Google matrix you defined above.
Just doing out the matrix multiplication you get $$ \begin{align*} r_i &= \sum_{j=1}^n B_{ij} r_j\\ &= \sum_{j=1}^n \left(pA_{ij} + \frac{(1-p)}{n}\right)r_j \qquad //\text{your def of B}\\ &= \sum_{j=1}^n pA_{ij}r_j + \frac{(1-p)}{n} \sum_{j=1}^n r_j\\ &=\frac{(1-p)}{n} + \sum_{j=1}^n pA_{ij}r_j \qquad // \mathbf{1}^Tr = 1 \end{align*} $$ From the last line we can write the linear equations as $$\begin{align*} r &= pAr + \frac{(1-p)}{n}\mathbf{1}\qquad \\ \end{align*} $$
So the algorithm can be peformed as $$ r^{(t+1)} = pAr^{(t)} +\frac{(1-p)}{n}\mathbf{1} $$ Note that $A$ is sparse