Hacker News Reader

Comment by inigyou | Hacker News Reader

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.

View on HN

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 !

> Unimportantly, it's named after Larry Page, not after the fact that it ranks pages.

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

His name may have influenced him to make his career from ranking pages

https://en.wikipedia.org/wiki/Nominative_determinism

I've always wondered what would happen if you named a kid Nominative Determinism. Some kind of paradox?

> name change at 18 probably

That's so cool because it's true, and holds very strongly with the semantic concept

name change at 18 probably

He'd probably grow up to be the guy who goes around making people do things that sound like their names.

He would be promptly murdered by someone named Alexander the Great.

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

He could also have worked for Motorola.

> Importantly, PageRank doesn't work today

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.

You clearly don't understand how Page Rank works. It is not just a matter of counting the incoming links.

So in other words it doesn't work.

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.

> Believe it or not, there are still some people in the world who believe that there is more to life than money

Do they use page rank?

We are talking about web search.

No, we are talking about Page Rank, which is an algorithm on directed graphs. Web search is one application, but not the only one.

> PageRank doesn't work today

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.

HodgeRank is a very different beast. It is nothing like Pagerank. Its input is not a citation/link graph but a list of paired ordered preferences.

In HodgeRank the goal is to combine a large list of pairwise preferences how to obtain the most representative total order.

Yes, but the comment I replied to outlined a way of using PageRank to aggregate noisy pairwise preferences into a global order.

That's right. My bad and my apologies. I should have read the context properly.

Another Goodhart's Law casualty...

Really?? And not BrinRank?

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.

Perhaps the second half of the word referred to Brin, after his smell after coding it for a week nonstop. Only a silly hypothesis of course.

Reply on news.ycombinator.com