Note that Google stopped using it in IIRC 2006.

It wasn't because of the adversarial link farms, though, which are usually handled by trying to identify fake links and take them out of the computation in a preprocessing step. (There are many others parts of Google's '00s ranking algorithm that relied upon backlinks as well). It was because the web scaled to the point where PageRank couldn't process it, because the exact matrix solution to it is O(N^3). They replaced it with an iterative graph traversal algorithm from a set of ~1000 seeds which were themselves chosen through the original PageRank algorithm. I suspect this is published somewhere, because Gemini alludes to it when I ask what's the algorithmic complexity of PageRank.

Interestingly this is a common pattern that Google uses. Come up with a heuristic algorithm that works well enough to get your first million users. Then, train a machine-learned algorithm on the actual behavior of your first million users to scale to your next billion. Assistant's NLP was similar, where the first version had all these linguists hand-inputting grammars for all the different ways you might say a command, and then they just trained a much simpler neural net mapping utterance -> command once they had enough users to get dense training data.

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 !