A minor comment: on a dense graph, one iteration of the power method would be O(N^2).

One would typically need many iterations for adequate convergence. If the number of iterations required is linear, then yes it would indeed take O(N^3). But it was never that bad.

However, the web-graph is very sparse, so per iteration cost is around O(N). That can still be quite a beast though.

Have fond memories of trying out Pagerank iterations on then new fangled infra called Mapreduce. Not for computing the pagerank for ranking pages, for experiments on some other large graph.

At that time (somewhere between 2004-07), computing Pagerank on the web, without preprocessing, got you all the porn sites at the top !