Google/Matrix

Page-ranking Problem

There are billions of web pages accessible over the internet, but how can someone find the ones with the most relevant information to the topic they are interested in? We need a way to compare the importance and/or relevance of all of these pages. A primary concern for the search engine (beyond being able to index every page) is to be able to rank pages with an algorithm that incorporates common usage patterns (i.e. a user who visits web page X is more likely to click the link to page Y than the link to page Z).

Similar Problems

A similar problem is the BCS (Bowl Championship Series)w:Bowl_Championship_Series rankings for college football. Since many football teams do not play each other during the regular season, how can they be ranked against one another? In this case, the BCS standings are calculated by summing three results: the Harris Interactive Poll[1], the USA Today Coaches Pollw:Coaches_Poll, and the average from six computer ranking systems.

Eigenvalue Solution Techniques

Google uses the PageRank algorithm which primarily ranks pages by the number of links to a web page, and the weights of the links. Initially every indexed page is given an equal rank, and a n x n connectivity matrix A is created (where n is the number of indexed pages). Position A_i,j is 1 if page i links to page j, otherwise it is 0. (Note: Since n is a very large integer, storing and working with A as a full matrix would be very inefficient, so it is usually stored as a sparse matrix.)

Once the initial rankings of every indexed page is calculated (simply 1/n), the PageRank of a new page is determined by how many links there are to the page, and the PageRanks of those 'linking' websites. The rank of a page is the probability that a web-surfer with an infinite amount of time will visit it.

In order to compute the PageRank of each website, we can use the Power Method to get the dominating eigenvector. This eigenvector will be n x 1, and will be made up of the PageRanks of all n websites. The connectivity matrix A is not initially in the correct format for use in the Power Method algorithm, so we will adjust A by dividing each row by the number of ones in that row and then (in order to keep track of everything) call the resultant matrix B.

Algorithm Outline

The Power Method x ← Bx will converge if B is:

• Stochastic: each row contains strictly nonnegative values and the sum of the values in a row equals one
• Irreducible: in the connectivity matrix it must be possible to get from any web page to any other web page
• Aperiodic: every web page has a link to itself (or the user can simply refresh the page)

In order to calculate our dominant eigenvector, we need to satisfy the rules listed above. Let C be a n x n matrix whose elements are C_i,j = p*B_i,j + δ.

(where p is the probability of the user clicking a link on the page, usually taken to be 0.85, and δ = (1 - p)/n, where n is the total number of pages).

C now satisfies the above conditions (and is the transition matrix of the Markov chain of a random progression through web pages). Next, we iterate through the Power Method until we find a dominating eigenvector, x, such that x = Ax. Once we have x, we can "assign" its components (the PageRanks) to the corresponding web pages in A.

Example of Use

As an example, let's say we have websites X, Y, and Z. X links to both Y and Z. Y links to X. Z links to Y. This then gives us matrix A,

$\mathbf {A} ={\begin{bmatrix}0&1&1\\1&0&0\\0&1&0\end{bmatrix}}$

but then we must divide each element of a row by the sum of the elements in that row, giving us matrix B,

$\mathbf {B} ={\begin{bmatrix}0&.5&.5\\1&0&0\\0&1&0\end{bmatrix}}$

and then we compute matrix C by taking into account p,

$\mathbf {C} =.85{\begin{bmatrix}0&.5&.5\\1&0&0\\0&1&0\end{bmatrix}}+{\frac {(1-.85)}{3}}{\begin{bmatrix}1&1&1\\1&1&1\\1&1&1\end{bmatrix}}$

$\mathbf {C} ={\begin{bmatrix}0&.425&.425\\.85&0&0\\0&.85&0\end{bmatrix}}+{\begin{bmatrix}.05&.05&.05\\.05&.05&.05\\.05&.05&.05\end{bmatrix}}$

$\mathbf {C} ={\begin{bmatrix}.05&.475&.475\\.9&.05&.05\\.05&.9&.05\end{bmatrix}}$

and then we use some initial guess, x⁽⁰⁾, for our Power Method, and calculate x⁽¹⁾, x⁽²⁾, and so on,

$\mathbf {x} ^{(0)}={\begin{bmatrix}3\\1\\2\end{bmatrix}}$

$\mathbf {x} ^{(1)}=Ax^{(0)}={\begin{bmatrix}.05&.475&.475\\.9&.05&.05\\.05&.9&.05\end{bmatrix}}{\begin{bmatrix}3\\1\\2\end{bmatrix}}\mathbf {=} {\begin{bmatrix}1.575\\2.85\\1.15\end{bmatrix}}$

$\mathbf {x} ^{(2)}=Ax^{(1)}={\begin{bmatrix}.05&.475&.475\\.9&.05&.05\\.05&.9&.05\end{bmatrix}}{\begin{bmatrix}1.575\\2.85\\1.15\end{bmatrix}}\mathbf {=} {\begin{bmatrix}1.97875\\1.6175\\2.70125\end{bmatrix}}$

$\mathbf {x} ^{(3)}=Ax^{(2)}={\begin{bmatrix}.05&.475&.475\\.9&.05&.05\\.05&.9&.05\end{bmatrix}}{\begin{bmatrix}1.97875\\1.6175\\2.70125\end{bmatrix}}\mathbf {\approx } {\begin{bmatrix}2.15\\2.0\\1.69\end{bmatrix}}$

$\mathbf {x} ^{(4)}=Ax^{(3)}\approx {\begin{bmatrix}.05&.475&.475\\.9&.05&.05\\.05&.9&.05\end{bmatrix}}{\begin{bmatrix}2.15\\2.0\\1.69\end{bmatrix}}\mathbf {\approx } {\begin{bmatrix}1.86\\2.12\\1.99\end{bmatrix}}$

Analysis

Convergence

To more easily see which component is increasing the most, we can break down the vectors, x⁽ⁱ⁾, into unit vectors and their coefficients,

$\mathbf {x} ^{(0)}=3{\begin{bmatrix}1\\0\\0\end{bmatrix}}\mathbf {+} 1{\begin{bmatrix}0\\1\\0\end{bmatrix}}\mathbf {+} 2{\begin{bmatrix}0\\0\\1\end{bmatrix}}$

$\mathbf {x} ^{(1)}=3{\begin{bmatrix}.525\\0\\0\end{bmatrix}}\mathbf {+} 1{\begin{bmatrix}0\\2.85\\0\end{bmatrix}}\mathbf {+} 2{\begin{bmatrix}0\\0\\.575\end{bmatrix}}$

$\mathbf {x} ^{(2)}\approx 3{\begin{bmatrix}.66\\0\\0\end{bmatrix}}\mathbf {+} 1{\begin{bmatrix}0\\1.62\\0\end{bmatrix}}\mathbf {+} 2{\begin{bmatrix}0\\0\\1.35\end{bmatrix}}$

$\mathbf {x} ^{(3)}\approx 3{\begin{bmatrix}.72\\0\\0\end{bmatrix}}\mathbf {+} 1{\begin{bmatrix}0\\2.0\\0\end{bmatrix}}\mathbf {+} 2{\begin{bmatrix}0\\0\\.845\end{bmatrix}}$

$\mathbf {x} ^{(4)}\approx 3{\begin{bmatrix}.62\\0\\0\end{bmatrix}}\mathbf {+} 1{\begin{bmatrix}0\\2.12\\0\end{bmatrix}}\mathbf {+} 2{\begin{bmatrix}0\\0\\1.0\end{bmatrix}}$

and so, from the looks of it, Y seems to have the highest PageRank, followed by Z, and then X.

---