O'Reilly logo

Advanced Graph Theory and Combinatorics by Michel Rigo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

10Google’s Page Rank

We will now start one of my favorite topics when lecturing or giving talks to a general audience1. 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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required