Lesson 4

Previously, we considered the classical PageRank algorithm, which treats all pages in the graph uniformly and models a random walk of a user. Over time, the algorithm has undergone numerous modifications aimed at improving both accuracy and computational efficiency.

One such modification is personalized PageRank. In the previous setting, we assumed that the user starts the random walk from a uniformly chosen vertex. In practice, however, this assumption is unrealistic. Each user has individual interests that make certain pages more attractive and, consequently, more likely to be visited. Personalized PageRank was introduced to account for this behavior. Although accurately estimating a user's true preferences may be challenging in practice, when such preferences are known, the algorithm from the previous section can be easily adapted to compute personalized PageRank. Specifically, if we are given a probability vector \(\mathbf{w}= (w_{1}, w_{2}, …, w_{n})\) where \(w_{i}\) denotes the probability that the user starts the random walk from page \(i\), it suffices to replace the update matrix with \(U = d\mathbf{T}+ (1-d)\mathbf{W}\), where \(\mathbf{W}= (\mathbf{w}, \mathbf{w}, ..., \mathbf{w})\) is a matrix consisting of \(n\) columns \(\mathbf{w}\). The resulting algorithm then computes a personalized PageRank that reflects the user's interests.

It may not be immediately obvious why this modification works. To see this, recall that we begin the process at a random vertex, so the initial vector \(\mathbf{v}_{0} = (\tfrac{1}{n}, \tfrac{1}{n}, …, \tfrac{1}{n})^{\top}\) is uniformly distributed over all vertices. At each iteration, we make a step of the random walk which is equivalent to \(\mathbf{v}_{i+1}= d \mathbf{T}\mathbf{v}_{i} + (1-d)\mathbf{v}_{0}\). Here, the term \(d \mathbf{T}\mathbf{v}_{i}\) corresponds to following an outgoing link chosen uniformly at random with probability \(d\), while the term \((1-d)\mathbf{v}_{0}\) represents a jump to a uniformly random page with probability \(1-d\).

In the personalized setting, instead of assuming that the random jump is uniformly distributed, we introduce a personalization vector \(\mathbf{w}= (w_{1}, w_{2}, …, w_{n})^{\top}\) where \(w_{i}\) denotes the probability that the user jumps to vertex \(i\), and \(\sum_{i} w_{i} = 1\). Replacing \(\mathbf{v}_{0}\) with \(\mathbf{w}\), the update rule becomes \(\mathbf{v}_{i+1}= d \mathbf{T}\mathbf{v}_{i} + (1-d)\mathbf{w}\). This modification models a random surfer who, with probability \(d\), follows an outgoing link, and with probability \(1-d\), teleports to a page according to the distribution \(\mathbf{w}\), thereby biasing the PageRank scores toward the user's preferences. And it is also easy to see that this update rule is equivalent to multiplying probability vector \(\mathbf{w}\) by the modified update matrix \(U = d\mathbf{T}+ (1-d)\mathbf{W}\).