PageRank explained

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.

I've always taken it as a happy double play since it is named after Page, but also ranks pages.

It works as well as it ever did, i.e. in non-adversarial situations. It's not designed to be secure so it fails when people try to game it. Designing something like Page Rank that works in an adversarial environment is still an open problem.

That's silly to say when it can be fruitfully applied in so many situations. Any time you have noisy and sparse pairwise comparisons, you can think of them as one of the sides of the pair vouching for the other side. If you then solve PageRank for the entire graph, you get a somewhat principled global ranking of all items.

I used it recently to construct a top list of books I read a year based only on sloppy pairwise comparisons between them. I've also used it to judge the quality of other relevance algorithms while keeping the human input to a minimum.

I don't know of many alternatives that work better than PageRank under those conditions. Thurstone-type models require dense comparisons, and Elo doesn't fare very well when the comparisons are too noisy.

For anyone puzzling over what is the graph-based perspective, there's actually a very elegant and simple mathematical way to derive page rank.

Define the directed graph of web links / citations through its adjacency matrix: web pages as nodes and links as directed edges. Represent a web surfer as a random walker on this graph, and run forth (simulate) the probability distribution of where they might end up.

If you've studied linear algebra you would see an immediate analogy between the PageRank algorithm how the power method is used to find the dominant eigenvector (of the transition matrix, which is a normalized version of the adjacency matrix).

This process is basically equivalent to implementing the diffusion process generated by the discrete graph laplacian. And simulating the random walk to find the long term stationary probability dstribution over nodes is akin to finding the zero eigenvector of this graph laplacian -- because it must generate "zero change" on the fixed point state.

Could you elaborate? I'm a very graph-oriented thinker, and I was never aware this was some kind of declining skill (For context I was not alive in '96).

[1] https://www.semanticscholar.org/paper/The-PageRank-Citation-...

> It is not the critic who counts; not the man who points out how the strong man stumbles or where the doer of deeds could have done them better. The credit belongs to the man who is actually in the arena, whose face is marred by dust and sweat and blood; who strives valiantly; who errs, and comes short again and again, because there is no effort without error and shortcoming; but who does actually strive to do the deeds; who knows the great enthusiasms, the great devotions; who spends himself in a worthy cause; who at the best knows in the end the triumph of high achievement, and who at the worst, if he fails, at least fails while daring greatly, so that his place shall never be with those cold and timid souls who know neither victory nor defeat.

https://www.presidency.ucsb.edu/documents/address-the-sorbon...

Back in 1996, this could be done by hand

Also, WTF, it seems impossible to find a PDF of the original paper still on the web without a paywall.

A little nihilistic, but I find it charming.