Chapter 5 — PageRank, a way to estimate the importance of web pages

When a researcher wants to publish a paper in a specialized journal, he must go through review committees that evaluate the quality of his work according to precise criteria. To appear on television or in a newspaper, all one needs is a good story to tell.

Surfing the internet is like sex: everyone brags about doing more than they actually do. But in the case of the Internet, they brag far more.

Omnes Viae ad Googlem ducent

This chapter will attempt to lay the intuitive, axiomatic, and theoretical foundations of PageRank-type ranking methods, brought to prominence by the famous Google search engine [Goo98]. This painstaking survey work was greatly facilitated by Mohamed Bouklit, who, with the help of Alain Jean-Marie, cleared the ground before me [Bou01, BJ02], providing me with all the necessary references.

There already exist a number of surveys on PageRank (cf [BGS02, BGS03, LM04]), but we deemed this chapter necessary because it presents all PageRanks from a single perspective, that of the stochastic interpretation, and highlights several convergence results that cannot be found elsewhere¹.

5.1 A needle in a haystack…

One can find (just about) anything on the web; virtually all network users agree on this. Whether the information I am looking for exists on the web is no longer the crucial question. Nowadays, the problem has become: How do I find the page I am looking for?

• By knowing, one way or another, the address in question. For instance, by reading on a bag of flour the address of a site offering cooking recipes, by receiving an email from a friend recommending a web address, or by having the address in one’s Bookmarks…
• By navigating (surfing) the web, starting from a known address. If, for example, I am looking for a page about raccoons and I know of a zoology website, starting from that site may be a good way to find the page I am looking for.
• By using a search engine. In exchange for a query, that is, a set of words attempting to describe more or less precisely what I am looking for, the engine will return a list of pages likely to answer this query. According to [LG99], 85% of internet users rely on search engines.

The whole challenge for search engines is to return the pages the user is actually looking for. However, the answers to a given query often number in the hundreds or even thousands², as shown in Table 5.1. On the other hand, users quickly lose patience, and it is estimated that 90% of users do not go beyond the first page of results.

The goal of search engines is therefore to display within the first ten to twenty results the documents that best answer the question posed. In practice, no sorting method is perfect, but their variety gives search engines the possibility of combining them to better refine their results. The main sorting methods are the following:

Relevance ranking

Relevance ranking is the oldest and most widely used sorting method. It is based on the number of occurrences of the search terms in the pages, their proximity, their position in the text [Sal89, YL95]… Unfortunately, this method has the drawback of being easy to manipulate by authors wishing to place their pages at the top of the list. To do so, it suffices to overload the page with important words, either in the header or in invisible text within the body of the page.

URL analysis

One can also assign importance to a page based on its URL. For instance, depending on the context, URLs belonging to the Top Level Domain http:.com might be more important than others, as might URLs containing the string http:home [Li+00]. It has also been suggested that URLs at a low depth in the cluster tree are more important than others [CGP98].

Inbound links

Citation counting consists of assigning pages an importance proportional to the number of known links to that page. This method has been widely used in scientometrics to evaluate the importance of publications [Pri63].

PageRank

As we shall see, PageRank is a kind of recursive generalization of citation counting.

5.2 The two axioms of PageRank

PageRank, introduced by Brin et al. in 1998 [Pag+98], is the ranking method that made the Google search engine [Goo98] distinctive. It is in fact an adaptation to the Web of various methods introduced by scientometricians³ since the 1950s. Two scientometric methods in particular should be mentioned:

Citation counting

In 1963, Price published Little Science, Big Science [Pri63]. In this book, the first major work dealing with what would later become scientometrics, he proposed measuring the quality of scientific production through, among other things, a very simple technique, citation counting: one way to measure the quality of a publication is to count the number of times that publication is cited.

Markovian modeling

Markov chains, described in Chapter 4, not only allow one to play Monopoly (registered trademark), but also to model the evolution of a population distributed among several states, provided one can estimate the transition probabilities between states. For example, Goffman proposed in 1971 the study of the evolution of research in various subfields of logic using Markov chains [Gof71].

Let us now see how Brin et al. adapted these concepts to estimating the importance of Web pages.

5.2.1 An important page is pointed to by important pages

Transposed directly to Web graphs, the citation counting method amounts to saying that the importance of a page is proportional to its in-degree, that is, to the number of pages that cite it through a hyperlink:

where means points to .

Although this measure can indeed be used to estimate the importance of pages [CGP98], it is partly undermined by the absence of quality control. Indeed, when a researcher wants to publish a paper in a specialized journal, he must go through review committees that evaluate the quality of his work according to precise criteria. Because of this, the mere fact of being published gives a minimum level of importance to the articles in question, and there is some guarantee that the citations a paper receives are not entirely spurious. In the case of the Web, this safeguard does not exist: because of the low intellectual and material cost of a web page, anyone can link to anything without it necessarily having any real meaning⁴. For instance, why not create a multitude of meaningless pages that cite me through hyperlinks, in order to inflate my own importance at will?

Brin et al. propose to counter this problem with a recursive description of importance: What is an important page? It is a page pointed to by important pages. Concretely, if a page is pointed to by pages , the importance of should be defined by:

It remains to define and solve Equation (5.2).

5.2.2 The random surfer: chance does things well

A romanticized view of the Web is the principle of hyperlink navigation: to find what he is looking for, the user navigates from page to page and click to click until reaching his destination. Of course, this is not what happens in practice, for both technical reasons (it is not always possible to reach a page from a page ) and social reasons (use of search engines, user fatigue…)⁵.

Brin et al. had the idea of modeling the behavior of the clicking user by a Markov chain. All that was needed was to find the transition probabilities from one page to another. One of the simplest ways of looking at things is to consider that once on a given page, the user will click uniformly at random on one of the links contained in that page:

This is the basis of the random surfer model. For Brin et al., given that Web graphs reflect a deliberate and thoughtful architecture, interesting pages should be structurally easy to access, just as a city is all the more accessible by the road network the more important it is. Therefore, since the random surfer lets himself be guided by the hyperlink network, statistically, he should land on a page all the more frequently the more important it is. Hence the idea of defining the importance of a Web page by the asymptotic probability of being on that page in the random surfer model.

5.2.3 Consistency of the two interpretations

Now that we have defined two ways of considering the importance of a page, let us observe that they coincide and describe the same phenomenon: indeed, in the random surfer model, it is possible to estimate the asymptotic probability of being on a page as a function of those of the pages that point to :

One can see that we indeed have an importance transfer relation like the one defined by Equation (5.2), and that Equation (5.4) additionally obeys a conservation principle: a given page transmits all of its importance, which is equally distributed among the different pages it points to. Probability, viewed as importance, is thus transmitted through hyperlinks in the manner of a flow.

5.3 The classical models

Although PageRank is often referred to in the singular, there actually exists a multitude of PageRank(s). We shall see here how, starting from the theoretical random surfer model that we have just described, several variations have been introduced in order to adapt to the reality of Web graphs. This survey work has already been carried out for all PageRank(s) arising from explicitly stochastic processes [BGS02, BGS03, LM04], but we also wish to take into account sub-stochastic models here.

5.3.1 Ideal case

In the case where the Web graph that we wish to study is aperiodic and strongly connected, the principles seen in Section 5.2 apply directly: indeed, the task is to find a probability distribution on satisfying:

This amounts to finding the asymptotic distribution of the homogeneous Markov chain whose transition matrix is:

As seen in Section 4.3, the distribution sequence

initiated by an arbitrary probability distribution ⁶, converges geometrically to the unique distribution satisfying

that is, satisfying relation Equation (5.5).

This probability distribution is called the PageRank.

5.3.2 Simple renormalization

Most of the time, a Web graph is not strongly connected. In particular, there exists a non-negligible number of dangling pages, which are either pages that actually contain no links, or simply pages that are known but not indexed. The rows of corresponding to these dangling pages therefore contain only s, and is thus strictly sub-stochastic. Consequently, the sequence of will converge⁷ to a vector that is zero outside any recurrent strongly connected components on which is stochastic⁸. To avoid this problem, one could consider recursively removing all dangling pages until a stochastic matrix is obtained, with the drawback of considering a smaller graph than the original. Another approach, proposed by [Pag+98], consists in renormalizing at each iteration:

This iterative procedure is a power method ([Ste94]), so it is known to converge to an eigenvector associated with the largest eigenvalue of . Two cases must then be considered:

• If the matrix is sub-irreducible, then its maximum eigenvalue is strictly less than 1. By Theorem 4.6⁹, the associated eigenspace has dimension , where is the number of pseudo-recurrent components, and its support is that generated by the union of the filters of the pseudo-recurrent components. In the particular case where is pseudo-irreducible, the eigenspace is a line, and there exists an associated strictly positive eigenvector: thanks to renormalization, everything proceeds as in the case of an irreducible stochastic matrix.

• If the matrix is not sub-irreducible, contains at least one recurrent strongly connected component on which is stochastic. The maximum eigenvalue of is therefore , which means that renormalization will not change the initial result: the eigenvector will be a linear combination of the eigenvectors on the different strongly connected components on which is stochastic¹⁰.

Equivalent stochastic process

The use of sub-stochastic matrices means that we lose the natural interpretation of the random surfer. However, it is sometimes possible to complete the matrix into an equivalent stochastic matrix, that is, to find a stochastic matrix satisfying:

• if , with maximal, then

If there exists a unique maximal probability vector for , the simplest way to define such a matrix is to consider the stochastic defect of : if is sub-stochastic, the stochastic defect of is defined as the vector . The matrix

is indeed a stochastic matrix¹¹ greater than , and it is easy to see that is a probability distribution homogeneous to , hence equal to .

The matrix has the advantage of giving a stochastic interpretation to the simple renormalization procedure: asymptotically, the random surfer follows at each step a link according to the probabilities given by . When he does not know what to do, he zaps to another page according to the probability distribution that is the maximal eigenvector of .

On the other hand, as soon as the maximal eigenspace has dimension greater than , the problem is delicate, even very delicate in the case of pseudo-recurrent components whose filters have a non-zero intersection. We will therefore limit our study of equivalent stochastic processes to cases where the maximal eigenvector is unique.

5.3.3 Stochastic completion

In order to replace with a stochastic matrix, and to avoid establishing an uncontrolled equivalent stochastic process through simple renormalization, a natural idea is to add transitions to dangling pages. One possible method consists in modeling the use of the Back button, and will be the subject of Chapter 6. Another method, proposed¹² initially by [Pag+98] (in the form of Algorithm 5.1) and studied among others by [LM04], consists in defining a default probability distribution on , and using it to model the behavior of the random surfer when he arrives on a dangling page. Concretely, each zero row in (which therefore corresponds to a dangling page) is replaced by the row .

This procedure can be generalized to complete any sub-stochastic matrix: The completion of by is then the stochastic matrix

Choice of and interpretation

represents the behavior of the random surfer when does not specify where he should go, that is, all page changes that are not due to the use of hyperlinks (manually typed address, Bookmarks, search engine query…). Generally, the uniform distribution is chosen for :

which represents a zap anywhere at random on the known Web.

It has also been proposed to “personalize” , notably by [Pag+98]. For instance, it is possible to restrict to the home pages of sites. On the one hand, this avoids implicitly giving sites a partial importance measure proportional to the number of crawled pages (see Section 7.5). On the other hand, this obeys a certain natural intuition: when one breaks hyperlink navigation to zap to something else, it is likely that one will start from a home page. This intuition is confirmed by numerous studies that demonstrate the existence of pages that play the role of “hubs” for actual users [CP95, Kle98, Mil+04, WM04].

Irreducibility of

A probability distribution is said to be covering if its support satisfies . This is a natural condition to impose on any zap distribution, since it guarantees that all known pages are potentially accessible after a zap. The uniform distribution is obviously covering. The same holds for the distribution on home pages if all known pages of a site are accessible from the home page. It is also the case for the importance distribution if, and only if, all pages in have a non-zero in-degree.

5.3.4 Rank source: zap factor

In order to resolve the irreducibility problem, Brin et al. [Pag+98] propose another incorporation of the zap distribution . They replace by , and seek to solve:

If , one then has the guarantee of operating on a positive, irreducible, and aperiodic matrix, since the underlying graph is a clique¹³. The Perron-Frobenius theorem therefore ensures convergence of the iterative process to the eigenvector associated with the maximal eigenvalue. However, unless , the new matrix is neither stochastic nor even sub-stochastic, which makes the interpretation in terms of a random surfer problematic. In order to more easily give an interpretation to the iterative process, Brin and Page normalize the matrix by taking the weighted average by of A and :

The resulting matrix preserves the (sub-)stochasticity of , and it is irreducible and aperiodic. If is stochastic, corresponds to the ideal case of Section 5.3.1¹⁴. The maximal eigenvector, which we shall call PageRank with zap factor, is then obtained by Algorithm 5.2. This vector represents the last academic version of PageRank presented by Brin and Page before Google’s ranking methods became an industrial secret. It is what is generally referred to when one speaks of PageRank.

Interpretation

When is stochastic, the dual interpretation of is fairly straightforward:

Importance transfer

with the zap factor, pages transmit only a fraction of their importance. In return, each page is assigned a Minimum Insertion PageRank (MIPR) equal to .

Random surfer

at each step of the stochastic process described by , the random surfer will click at random on one of the outgoing links, with probability , or zap with probability somewhere on the graph according to the distribution .

5.3.5 Choice of

Before going further, it is appropriate to discuss the choice of the parameter and the reasons that led to this choice. To begin with, let us state a universal and unalterable empirical reality: equals , give or take . Since the beginnings of PageRank, has always been the reference value, and to my knowledge, practical PageRank computations following the rank source model seen in Section 5.3.4 always use a between and .

Convergence/graph alteration tradeoff

By Theorem 5.2, if is stochastic, which can be assumed by performing a completion if necessary, the eigenvalues of other than are less than in absolute value¹⁷. This guarantees algorithms Algorithm 5.2 and Algorithm 5.3 a geometric convergence with ratio at most . One therefore has an interest in choosing as small as possible… except that the smaller is, the greater the influence of the zap, which is a component external to the intrinsic Web graph. A small alters, or even distorts, the underlying graph. Choosing the largest that guarantees reasonable convergence therefore seems like a good tradeoff. Now, technical limitations mean that the number of iterations achievable by a search engine like Google is on the order of a hundred¹⁸. offers a precision of after iterations, after iterations, and therefore appears to be heuristically the desired tradeoff. Indeed, as we shall see in Section 5.5, corresponds to the differentiation threshold for a Web graph of one million pages, while is the differentiation threshold for one billion pages.

5.4 Rank source and sub-stochastic matrices

In the rank source model seen in Section 5.3.4, we saw that while adding a zap factor associated with a covering distribution guarantees the irreducibility of , the stochasticity of remains that of . When is sub-stochastic, one must therefore adapt, and we shall see in this section the main possible solutions.

5.4.1 Hybrid model: zap factor and renormalization

is pseudo-irreducible (since it is irreducible). A first possible method for obtaining a fixed point is therefore to apply the simple renormalization method (cf Section 5.3.2) to the matrix .

The interpretation in terms of a random surfer is the same as in the case where is stochastic, except that the stochastic defect of must be completed by a zap according to the distribution defined by the maximal probability eigenvector associated with .

5.4.2 Completion and rank source: -compensation

Since stochastic completion is a relatively simple way of assimilating any sub-stochastic matrix to a stochastic matrix, it is interesting to hybridize the stochastic completion method with a zap-type method or virtual page addition (see Section 5.6). This avoids having to renormalize at each iteration, and provides greater consistency in terms of stochastic interpretation. Moreover, if one chooses a completion distribution equal to the zap distribution , one obtains a very simple algorithm (Algorithm 5.3): the -compensation algorithm. The interpretation is equally simple: at each step of the stochastic process described by , the random surfer will click at random on one of the outgoing links (if any exist), with probability . In all other cases, he will zap according to .

5.4.3 Non-compensated PageRank

The non-compensated PageRank algorithm consists in computing , exactly as in Algorithm 5.2, without worrying about renormalization. This yields a strictly positive vector, which can be used to define a PageRank, as shown by Theorem 5.3 and the interpretation that follows.

5.4.4 Comparison: -compensated or non-compensated algorithms?

There is a very strong link between the -compensated algorithm and the non-compensated algorithm: they yield the same result, as shown by Theorem 5.4.

Convergence

The tests we have been able to perform show that with the choice of as the initial distribution, there is no significant difference between the convergence of the -compensation algorithm and the non-compensated one. In both cases, convergence is very fast during the first iterations, and then stabilizes toward a convergence with ratio (cf main loop of Figure 5.1).

Iteration speed

The -compensation must compute the parameter at each iteration, while the non-compensated version does not. Does this have a significant influence on performance?

• If the matrix does not fit in memory, the limiting factor in computing an iteration is the multiplication of by . The time used for compensation is then negligible, and the iteration speed has no influence on the choice between the two algorithms.
• On the other hand, if , or even simply the adjacency matrix, fits in memory, the computation and incorporation of takes a duration comparable to that of computing . In fact, any norm computation adds a non-negligible overhead to the computation of an iteration, and even the computation of the convergence parameter considerably reduces performance. This leads to the SpeedRank algorithm (5.4), which computes the non-compensated PageRank by roughly estimating the number of iterations needed for good convergence. Our experiments revealed a speed gain of more than on iterations between SpeedRank and Algorithm 5.3, which more than compensates for the slight overestimation of the number of iterations needed to converge.

In terms of performance, the -compensated algorithm is therefore to be avoided when working on “small” graphs. One may be surprised in passing that Kamvar et al. use -compensation in their BlockRank algorithm [Kam+03b], which is precisely based on the decomposition of PageRank on small graphs. For specialists in PageRank computation optimization (cf [Kam+03a]), it is curious to overlook a speed gain of …