Importantly, PageRank doesn't work today - you need something else. It was one of many possible ranking hacks, and one that worked at the particular time in that particular state of the web where nobody was gaming links because PageRank didn't exist yet. Maybe you could invent a good ranking algorithm for the modern internet, perhaps just the reciprocal of the number of ads on the page, minus its AI detector score, but probably not that.
Unimportantly, it's named after Larry Page, not after the fact that it ranks pages.
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 !
It's not like he was going to be a Congressional staffer nor working at a newspaper. But if he was on-call for a lot of his career that'd be kind of amusing
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.
The PageRank algo by definition is broken, because it equates popularity rather than truth or correctness.
The perfect example of why this is broken is health and medicine, for all its fails, we all know that modern medicine is based on evidence, something all other alternatives are not.
Secondly take news, the actual source the source of truth most of the time is not the first match, and could and is often surpassed by some social media commentator which is just wrong imho.
PR never worked.
Its the same as thinking the stars of music (pick any name) are the best because they are popular even if they cant play an instrument and most never write their own songs.
Correctness is impossible to evaluate without a panel of humans to define "the truth" for each topic and an advanced NLP system that compares the meaning of a page with it. Impossible in 1996, you could maybe pull this off today with LLMs but it would be super expensive and not very reliable.
This would create an intentional bias in the results. That's not something you expect from a web search, it should return the most relevant and popular links not the ones that agree with mainstream science. Wikipedia, PubMed and other databases where actual experts contribute are way better for that.
Um, no? It works in non-adversarial environments. Such environments are rare in today's world but they still exist, mainly where there isn't a profit motive. Believe it or not, there are still some people in the world who believe that there is more to life than money.
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.
HodgeRank (see https://math.pku.edu.cn/teachers/yaoy/publications/HodgeRank...) is somewhat related to PageRank but is a natural way to approach this problem. I haven't tested it for anything but would expect it to handle noisy comparisons fairly well.
Larry designed the algorithm and Brin implemented it. Not so different than what we saw with transformers and LLMs. The people who came up wit the ideas and the algorithms were joined by others who implemented them. Together they made it all work.
There's no credible reference to this. The most likely scenario is that they worked together in designing the system. They also credited their professors, Motwani and Winograd, for it.
Unimportantly, it's named after Larry Page, not after the fact that it ranks pages.