PageRank explained
praveshkoirala.com
praveshkoirala.com
I didn't really know what I was doing (I was 17), but it was an awesome unpaid summer internship. There were two parts of the search engine - a crawler and the search engine. Both were written in Perl.
Yet, this is not even half the work. It like a third of the way.
Before you could have invented PageRank, you must think in graphs. That is possible in 1996, but not as widespread as today.
After you invented PageRank, you still need to deploy it. Again, possible but challenging as well. Is Python performant enough in 96? Can you afford more than 4MB RAM?
At least Lego will not sue you for using their bricks to build a server rack in 1996.
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).
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.
* [2020-06-17] Spanning Tree - "How Google's PageRank Algorithm Works" (5m16s): https://www.youtube.com/watch?v=meonLcN7LD4
* [2022-05-23] Reducible - "PageRank: A Trillion Dollar Algorithm" (25m25s): https://www.youtube.com/watch?v=JGQe4kiPnrU
Tying relevancy to link frequency was definitely a novel idea at the time, even if it seems "obvious" or simple in retrospect.
Yes you could have invented PageRank, but could you also have invented MapReduce, BigFiles/Google File System (GFS), Google Web Server, Bigtable, Protobuf? Then spun up fault-tolerant clusters consisting of cheap commodity PC hardware in an era where AWS wasn't even an idea yet? Then invented the concept of Borg to manage this hardware globally?
Money you get by being a pair of connected Stanford grads living in the most tech connected place in the world, with Stanford alumni and venture capital connected people all around you.
The CS is part is medium-hard. The productionizing part is a hiring problem.
Getting the capital is a whole other aspect.
I knew lots of smart people in 1996 in the first .com wave. None of us made any money :-) I should have moved to San Francisco in 97 like I was originally planning. Oops. (And no, I could not have done what Jeff Dean & Sanjay did but I would have loved to have tried ;-) )
Inverting the huge, sparse matrix of references for PageRank was expensive. Originally, Google did it about once a week. The big breakthrough was when someone (who?) figured out how to do it incrementally at scale.
[0] https://math.libretexts.org/Bookshelves/Linear_Algebra/Under...
google became the most popular search engine exactly because those SEO keyword spam lists didn't work anymore and, after a while, they vanished. blogs, on the other hand, worked exceptionally well, because they used to link to other blogs' entries a lot, and blogs also used to be (comparably) high quality content.
so the main SEO guideline for getting a good page rank used to be: have a blog/news and publish lots of high quality content that bloggers link to.
No, Brin wasn’t a co-inventor of PageRank.
[1] https://www.semanticscholar.org/paper/The-PageRank-Citation-...
The system disincentifies adding "ghost" inventors since incorrect listing of the inventors can invalidate a patent.
So, yes, it's likely that the patent attorneys hired by Stanford advised that only Page should be listed as an inventor. Stanford gets its money via the assignment, not the inventor list.
> 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...
Citation index https://en.wikipedia.org/wiki/Citation_index
Shepard's Citations https://en.wikipedia.org/wiki/Shepard's_Citations
https://web.archive.org/web/20130728183938/williamcotton.com...
I never thought of it.
I never thought of the Million Dollar Homepage, either.
It's still there! https://milliondollarhomepage.com/
I remember the first ever HTML CV (résumé) being published.
I am Slashdot user #6030. I used it for ages before I created a user account.
I was already paying for my own personal email address in 1991 when timbl revealed the WWW to the world. I thought it was a gimmick. It'd never catch on. We already had Gopher and Archie and Veronica.
deep sigh
A little nihilistic, but I find it charming.
Outbid is just sad. People pay money to get on a slop board?
PageRank, at its core, symbolizes these basic properties.
Except in the case of advertising
Even if, hypothetically, company knows what user is searching for before user finishes typing a query, it does not mean company is going to deliver it to user
Company is paid by advertisers, not users
Company can deliver something _popular_, call it "relevant", make bank
"Popular" grows audience, good for advertisers
"Relevant" not necessarily good for advertisers, only good for user
Company serves its customers: advertisers
Company does not need PageRank to determine popularity, only search traffic (search query data)
(Of course a result could be both relevant and popular. But a result could also be relevant and _unpopular_. Company is promotes the former to the exclusion of the later. It profits by selling advertising services to advertisers, not information services to www users)
For example, paying vendors to be the "default" search engine
Also, WTF, it seems impossible to find a PDF of the original paper still on the web without a paywall.
Back in 1996, this could be done by hand
Then we move on to upvotes, retweets, likes, listens, views, please-please-please-subscribe-to-my-channel, reviews etc. Thus the continuum of the "social" internet.
We tried really hard to make truth into a capitalist endeavor.
What if I fricken want fricken "Hotels for Chickens", what about that, huh?
I mean, page rank was useful but it was also a step in the direction of "search give you what it think you, not what you asked for" and I think now we can how far and dubious progress in that direction has been.
More by this author:
> a new crowd-funded investigative journalism project, breaks the exclusive story of how the United States intelligence community funded, nurtured and incubated Google as part of a drive to dominate the world through control of information. Seed-funded by the NSA and CIA, Google was merely the first among a plethora of private sector start-ups co-opted by US intelligence to retain ‘information superiority.’
> The origins of this ingenious strategy trace back to a secret Pentagon-sponsored group, that for the last two decades has functioned as a bridge between the US government and elites across the business, industry, finance, corporate, and media sectors. The group has allowed some of the most powerful special interests in corporate America to systematically circumvent democratic accountability and the rule of law to influence government policies, as well as public opinion in the US and around the world. The results have been catastrophic: NSA mass surveillance, a permanent state of global war, and a new initiative to transform the US military into Skynet.
https://web.archive.org/web/20190722034225/https://medium.co...
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.
That's so cool because it's true, and holds very strongly with the semantic concept
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.
In HodgeRank the goal is to combine a large list of pairwise preferences how to obtain the most representative total order.
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.
Do they use page rank?
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.
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.
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.
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 !
One of my favorite things about HN is the way that you can find someone who has produced definitive proof of the non-existence of the public education system in an offhand comment.