Quantum Physics, PageRank & the Schrödinger equation

  • 0
  • August 8, 2008
Patrick Altoft

Patrick Altoft

Director of Strategy

The original PageRank equation described the importance of a web-page as a function of the number of other web pages linking to it. The theory was based on a modified random walk model whereby if a random web surfer visited a page the probability they click on any given link is governed by the number of links on the page and a damping factor to take into account the probability they don’t click on any links.

The basic result of this formula is that the pages that have the most links (citations) are visited by the random surfer more times and are deemed to be of greater importance and are given higher PageRank.

Since the PageRank equation is iterative it requires quite a lot of computational power to calculate, something which Google has no doubt been addressing ever since they devised the algorithm in the late 90’s. A host of other papers have explored linear methods of improving the PageRank calculation process.

A new paper released last month describes how the PageRank algorithm can be compared to a Schrödinger type wave equation making calculations much faster.

Schrodinger Equation

The idea is that if the terms of the PageRank equation are rearranged to make a Schrödinger style wave equation a computer can make highly educated guesses on the distribution of PageRank score. This makes it possible to compute the value of PageRank score through matrix expansion rather than iteratively as with the original equation.

The figure below shows a pictorial representation of the PageRank equation and its counterpart in term of wave function. Bottom 3-d plot of potential V and the corresponding PageRank measured along concentric shells around an original vertex.

From the paper:

The present procedure to compute this quantity on a given graph is based on numerical iterations. The whole process corresponds to surf the WWW with a number of random surfers and to assign the PageRank of a page as the number of times it is crossed by a walker. Just to avoid the presence of trapping states for these surfers, they are allowed to jump into a completely new page of the WWW (with probability (1 – α) ∼ 0.15). The role of the damping factor α has been intensively studied, since PageRank changes significantly when α is modified [11].

The effectiveness of this ranking procedure is witnessed by the success of the search engine Google. Since the first investigations, various procedures and algorithms have been presented to determine the PageRank and its dynamical evolution [10, 12, 13, 14]. It is fair to say that the study of PageRank constitutes a field of research on its own. Actually the PageRank has also a strong impact in may Web-related topics such as propagation of trust (e.g. TrustRank, propagation of trust and distrust), and smoothed classification of pages.

We present here a novel approach based on an analogy with quantum physics. In particular we show that it is possible to rearrange the terms of the PageRank equation in such a way as to obtain a Schrodinger-like equation for a wave function. For a given page, the wave function is given by the PageRank divided by the outdegree (i.e., the number of outgoing links). Through this new approach we recognize that the topology of the system, (more precisely the difference between the number of ingoing and outgoing links per page), plays the role of a local quantum-like potential V defined on every page.

The paper concluded by stating:

In conclusion, rearranging the terms in the PageRank equation, we have been able to obtain a Schrodinger-like equation allowing us to define a site potential V in the system. According to the meaning of the original equation, the PageRank (now in the form of a wave function), localizes in the minima of this potential allowing educated guesses on the distribution of PageRank score.

Furthermore, this representation makes possible to compute the value of PageRank score through matrix expansion rather than iteratively. While in the limit of infinite pages the latter method is certainly less time consuming, for the subset of the WWW analysed here the expansion method is noticeably faster. Since the PageRank is also used for a variety of Web-related problems (like for example the propagation of trust), in most of these cases where one deals with systems of medium-large size, our approach can be competitive.

Finally, the formal analogy with quantum physics makes available a complete series of theoretical frameworks like perturbation theory that could be used to study the dynamical evolution of the PageRank score distribution. While with iterative techniques we must compute anew the PageRank score distribution for any change of the topology, through our approach we can in principle obtain in a much shorter time the evolution of this quantity. The Schr¨odinger-like equation we introduce, formally generates a connection among completely different kind of phenomena and at very distant scales, like the World Wide Web and the microscopic world of Quantum Physics and it is likely to pave the way to a series of activities in this field.

It is clear that Google isn’t still using the original PageRank equation developed over 10 years ago. The web gets bigger every day and Google has to make their algorithm as efficient and scalable as possible, therefore it is quite probable that this method of approximation or another similar one forms the basis of the Google PageRank algorithm today.

Further reading
PageRank at Wikipedia
Google PageRank explained
Thanks to Pierre for the tip.

Free of charge. Unsubscribe anytime.