Quantum Physics and PageRank
In the last 20 years, the amount of pages on the web has increased over a thousandfold, from an already astounding 1 million pages in 1997 to an incomprehensibly huge 1.2 billion pages in 2017. But of what use is all of this information if it is inconvenient, difficult to find, and sometimes impossible to access? Luckily, ranking algorithms have made it possible for search engines to deliver relevant results for queries. For years, PageRank has been considered one of the premier algorithmic tools to make sense of the Web by assigning a weighted “importance” to each site that it comes across. It’s so good, that it is largely responsible for Google’s runaway success in the late 90s and early 2000s in the search engine market.
As we learned in class, PageRank evaluates individual nodes in a graph based on how many edges point to a given node and how many edges leave that node, determining the overall level of “importance” of a given node to be higher if the number of edges pointing to it is higher than the number of edges pointing away from it.
Highly-ranked nodes display a rictus of sheer joy upon being informed of their favorable PageRank
Recently, researchers in Australia have applied quantum physics to the problem of network graph search and sorting. Quantum physics may not seem like an intuitive partner for the field of network research, but when considering the importance of randomness to “walking” through a network in order to rank the nodes, the link is much more clear. In their research, they used subatomic particles in such a way that they could explore a graph randomly while also studying the interference effects between the particles. In experiments, this new quantum method was able to match the performance of PageRank in evaluating the “centrality” of nodes, and even beat PageRank in the task of identifying equivalent sets of nodes in a given graph.
These new findings just add to the interdisciplinary character of this course. I never would have imagined seeing anything about quantum physics in this course content, yet even here there are relations to the study of networks. I am curious how research in this direction will affect future interpretations of graph search. Hopefully Profs. Easley and Kleinberg will not have to rewrite the textbook too soon.
Sources:
https://journals.aps.org/pra/abstract/10.1103/PhysRevA.96.032305
http://www.internetlivestats.com/total-number-of-websites/