Google Matrix

The Google matrix is the matrix used in Google’s original PageRank algorithm to rank web pages.

If a web consists of $n$n pages, the Google matrix $G$G is defined as:$$G = \alpha S + (1-\alpha)\frac{1}{n}E$$G=αS+(1−α)n1​E

where:

• $S$S is the normalized link matrix (each column sums to 1).
• $E$E is an $n \times n$n×n matrix of all ones.
• $\alpha$α is the damping factor, typically $0.85$0.85.
• $n$n is the number of pages.

Here’s the formula visually:

$G=\alpha S+(1-\alpha)\frac{1}{n}E$G=αS+(1−α)n1​E

Why it’s used

The matrix models a “random surfer” who:

• Follows a link on the current page with probability $\alpha$α.
• Jumps to a random page with probability $1-\alpha$1−α.

The PageRank vector $p$p is the stationary distribution satisfying$$Gp = p.$$Gp=p.

That is, $p$p is the eigenvector corresponding to eigenvalue $1$1.