GoKawiilPicture this, the year is 1996. You find yourself frustrated with the incumbent search engines like AltaVista, which primarily does a content-based search (it’ll give you an article on “Hotels for Chickens” if you search “Hotels” because the word matches). There’s gotta be a better way, right? Well, in hindsight, of course. Sergey Brin and Larry Page came up with this precise algorithm, i.e., PageRank, which was one of the key algorithms that helped catapult Google into a household name and made them tons of money. Both Sergey and Larry were grad students at Stanford, so their coming up with such an amazing algorithm doesn’t seem surprising. However, the question is, could you have stumbled upon the same? I think yes.
PageRank, at its core, symbolizes these basic properties.
Every page has a “rank” or reputation.
A page shares its “rank” with another page by linking to it, sort of giving it a mark of approval.
A page’s total rank/reputation is some minimum summed with all the reputation it gets from its neighbors (whoever links it).
And that’s it. To solidify this with a concrete example. Imagine a page (say BBC News) has a reputation of 50 and it links to 5 different pages. Assume that it distributes 80% (40) of its reputation to its linkees (the remaining being distributed uniformly to all pages). Then each of its linkees gets, from BBC, a total of 40/5 = 8 points.
You could potentially cook up a very small (and surprisingly readable) python program that does this as follows:
# incoming[n] has all incoming nodes upon n # outgoing[n] has all outgoing nodes from n # A page distributes damping% of its reputation to its neighbors. # (1-damping)% is distributed to all pages equally. def pagerank ( incoming , outgoing , damping = .85 , tolerance = 1e-10 ): n = len (incoming) # total pages rank = [ 1 / n] * n # starting ranks. all equal. minimum_rank = ( 1 - damping) / n # a page gets at least this # from every other page # due to random jumps. while True : old = rank.copy() for page, neighbors in enumerate (incoming): # you get this from your linker (who's distributing # its rank equally to all of its linkees) acquired = sum ( old[neighbor] / len (outgoing[neighbor]) for neighbor in neighbors ) rank[page] = minimum_rank + damping * acquired # until the algorithm converges if max ( abs (a - b) for a, b in zip (rank, old)) < tolerance: return rank
And that’s about it. If you run these updates a bunch of times, you eventually end up with a rank for each of the pages that basically tells you how important they are. Of course, certain assumptions have been made here (like no dangling nodes, etc.), but those are simply bookkeeping, and you now know the crux of the algorithm. Congratulations, if you ever find yourself in 1996, you know what to do to become a billionaire!