Lesson 1

We are ready to dive into the main topic: the PageRank algorithm. Earlier, we outlined two key principles that guide our approach:

• Links as Votes.  A hyperlink from one page to another one is interpreted as a vote of confidence or endorsement. The more votes a page receives, the more important it is.


• Importance of the Voter.  Crucially, not all votes are equal. A vote from an important or authoritative page (one with a high PageRank itself) counts for more than a vote from an unimportant page.

Notice that these principles perfectly describe the behavior of a user randomly surfing the web: the user is more likely to visit popular pages and follow links from those pages to discover new content.

A natural approach to ranking web pages is to consider the stationary distribution of a random walk on the web graph. While this idea is appealing in principle, some challenges arise when we try to apply it directly. We cannot guarantee that the web graph will satisfy the conditions of the Ergodic Theorem: it may not be irreducible, aperiodic, or free of sink nodes. To address these issues, we introduce a damping factor \(d\) and connect all pairs of nodes with edges of small weight \(\frac{1-d}{n}\), where \(n\) is the total number of pages. To preserve the stochasticity of the transition matrix, we multiply the original edge weights by \(d\). Thus, the new update matrix \(\mathbf{U}\) becomes: \[\mathbf{U}=d\mathbf{T}+\frac{1-d}{n}\mathbf{J},\] where \(\mathbf{J}=\mathbf{1}_{n \times n}\) is the all-ones matrix.

For our toy graph and \(d=0.85\), it will look like this:

It is easy to see that this modified graph satisfies the conditions of the Ergodic Theorem. Consequently, we can perform a random walk on this graph and compute its stationary distribution, which gives us the PageRank scores of the pages.

For a more intuitive understanding, from the perspective of a random walk, this is equivalent to the following process: A random surfer starts at a random page and on each step with probability \(d\) follows links at random, however, with probability \(1-d\) the surfer gets bored and jumps to a random page instead of following a link.

In practice, solving the equation \(\mathbf{U}\mathbf{r}= \mathbf{r}\) to determine the stationary distribution can be computationally expensive (taking time \(O(n^{3})\)), particularly for large graphs such as the web graph. Instead, an iterative random walk is often employed. In this approach, an initial vector, typically a uniform distribution, is repeatedly multiplied by the transition matrix \(\mathbf{U}\) until the changes in the distribution become sufficiently small. This method converges exponentially to the stationary distribution, owing to the properties guaranteed by the Ergodic Theorem.