Page rank and radiosity

I was talking to Jaron Lanier today, and we were swapping stories about “things very smart people should have known but it turns out they didn’t.”

I told him about the first time I visited Google, in Spring 2000. At some point during my visit Larry Page explained to me how his “Page Rank” algorithm works — the cornerstone of Google’s search strategy.

The basic idea of Page Rank is that a web page is considered more important if it is linked to by important web pages. And those pages are in turn considered important if they are linked to by important web pages.

So, for example, if your page is linked to by a page that lots of other pages link to — like a popular page on Google or Amazon — then your ranking goes up. It’s the ultimate example of “It’s not who you know, it’s who they know.”

One way to look at this is that you have a giant matrix that, one might say, shows how any page is “illuminated” by the light shining on it from other pages pointing to it. To figure out how “bright” a page is, you need to keep multiplying this huge matrix by itself over and over again (ideally, infinitely many times), to bounce that informational “light” around the system.

By the way, the matrix is mostly filled with zeros, because most web pages don’t link to most other web pages.

It turns out that multiplying a matrix by itself infinitely many times can be done by inverting the matrix (kind of the same as 0.5 is the inverse of 2, but with matrices instead of numbers). And if the matrix is mostly filled with zeros, there are clever fast ways of doing this. So practically speaking, Page Rank works by constructing a giant matrix, with mostly zeros in it, and then using some fancy math to invert this matrix as fast as possible.

People reading this who do research in computer graphics will recognize what I just described as the radiosity algorithm in computer graphics — except in radiosity you’re talking about actual rays of light bouncing around little bits of surface of a 3D scene.

The trick is exactly the same — you construct a giant matrix (that’s mostly filled with zeros) and then invert it, to figure out what happens when all those light rays bounce around the scene over and over again.

When Larry Page described Page Rank to me, my first response was “Oh, so it’s basically a radiosity algorithm.”

Larry’s response was “What’s radiosity?”

To my utter astonishment, by the way.

When I told this story to Jaron today he said “Ken, you really need to write about this.”

So here it is. 🙂