The Physics of PageRank

Some of you may know that the physicist Kenneth Wilson died on June 15^{th}. His work made a huge impact in physics. Not just particle physics, but condensed matter physics as well. No part of physics which is formulated as a quantum field theory was left untouched. So, what did he do? And what does it have to do with PageRank?

Wilson’s Magnum Opus

In order for theorists to actually calculate anything using quantum field theory (QFT), renormalization theory was needed. Feynman, Tomonoga, and Schwinger each independently introduced renormalization into QFT. Freeman Dyson came along afterwards and showed that the three formalisms mentioned above were actually the same thing. But the theory wasn’t on firm theoretical ground before Wilson’s work. Kenneth Wilson introduced the Renormalization Group (RG). And with the RG, we could calculate things with QFT in a systematic, conceptually coherent manner.

(For more on the history, you can read a great blog post about it at Quantum Frontiers.)

When I was in graduate school, the RG was easily one of the most interesting aspects of theoretical physics. I loved that it provided us with a clear theory of critical phenomena and phase transitions as well.

What does this have to do with PageRank though? Here’s a rough outline of the relationship…

The Renormalization Group

Imagine a system described by a vector of parameters, K, and consider a transformation that shifts the parameters to some K'. We can describe this situation with the transformation equation

K'=\mathcal{R}(K),

where \cal{R} is the RG operator. If the transformation operator is applied repeatedly, then we end up with a sequence of parameter vectors K, K', K'',\ldots:

K^{(n)}=\mathcal{R}(K^{(n-1)})=\cdots=\mathcal{R}^n(K^{(0)}),

where n=0,1,2,\dots and K^{(0)} is our initial K.

If we plotted the initial K^{(0)} and plotted results of the successive transformations, we would have a sequence of points connecting K^{(0)} and K^{(n)}. The sequence of points is the RG flow and is represented by the above equation.

It’s possible that we may have fixed points in our parameter space. A fixed point K^{\ast} that remains unchanged when the transformation is applied:
\mathcal{R}(K^{\ast})=K^{\ast}.

Note that I’m glossing over a lot of detail.

The PageRank Algorithm

At its core, PageRank is an algorithm which answers the following question:

If we select a site in a network or graph at random, what is the likelihood of reaching any other given site?

PageRank determines the answer in an iterative fashion, using equations that look a lot like the RG equations. The iterative algorithm proceeds until the probabilities on the sites stop changing. This is our RG fixed-point.

You can learn more about PageRank and the iterative ranking algorithms which came before in a 2010 arXiv article PageRank: Standing on the shoulders of giants.

I’ll really have to look into this in more depth sometime, especially where the fixed-points are concerned.

Advertisements