Advanced Graph Theory and Combinatorics

10Google’s Page Rank

We will now start one of my favorite topics when lecturing or giving talks to a general audience¹. Indeed, we will see that Perron’s theorem is behind the famous search engine and how powerful this result is. In this chapter, we will describe the basic ideas behind the PageRank algorithm. This is only an introduction to the subject. Entire books are devoted to this important topic [LAN 06]. The PageRank of a page is only one of the ingredients (but an important one) used by Google to provide its ranking of Webpages. This requires a more complex formula to include, for instance, information about the user (language, searcher’s last queries, geographic location, which links are usually clicked on, operating system or browser, etc.) to obtain a personalization of the search. Even though many improvements have been made over two decades, the idea behind PageRank link analysis is fundamental.

Search engines (SEs) play a major role in what pages users effectively see. They have a tremendous power in their hands. People click more on the pages they see at the top. No one goes on the third page of results provided by Google. There is an ongoing debate about how results should be displayed by SE. Organic search is the result given by the SE based on relevance only (versus non-organic search including pay-per-click advertisement). If the user clicks on some particular item, the SE makes more money. The SE has to find a good balance between maximizing revenue and keeping ...