This article has multiple issues. Please helpimprove it or discuss these issues on thetalk page.(Learn how and when to remove these messages) This articleprovides insufficient context for those unfamiliar with the subject. Please helpimprove the article byproviding more context for the reader.(March 2019) (Learn how and when to remove this message) This articlehas an unclearcitation style. The references used may be made clearer with a different or consistent style ofcitation andfootnoting.(December 2014) (Learn how and when to remove this message) (Learn how and when to remove this message)

AGoogle matrix is a particularstochastic matrix that is used byGoogle'sPageRank algorithm. The matrix represents a graph with edges representing links between pages. The PageRank of each page can then be generated iteratively from the Google matrix using thepower method. However, in order for the power method to converge, the matrix must be stochastic,irreducible andaperiodic.

In order to generate the Google matrixG, we must first generate anadjacency matrixA which represents the relations between pages or nodes.

Assuming there areN pages, we can fill outA by doing the following:

1. A matrix element${\displaystyle A_{i,j}}$ is filled with 1 if node${\displaystyle j}$ has a link to node${\displaystyle i}$, and 0 otherwise; this is the adjacency matrix of links.
2. A related matrixS corresponding to the transitions in aMarkov chain of given network is constructed fromA by dividing the elements of column "j" by a number of${\displaystyle k_j={\mathrm{\Sigma }}_{i=1}^N{A}_{i,j}}$ where${\displaystyle k_j}$ is the total number of outgoing links from node j to all other nodes. The columns havingzero matrix elements, corresponding to dangling nodes, are replaced by a constant value1/N. Such a procedure adds a link from every sink, dangling state${\displaystyle a}$ to every other node.
3. Now by the construction the sum of all elements in any column of matrixS is equal to unity. In this way the matrixS is mathematically well defined and it belongs to the class of Markov chains and the class of Perron-Frobenius operators. That makesS suitable for thePageRank algorithm.

Then the final Google matrix G can be expressed viaS as:

${\displaystyle G_{ij}=\alpha S_{ij}+(1-\alpha )\frac{1}{N}(1)}$

By the construction the sum of all non-negative elements inside each matrix column is equal to unity. The numerical coefficient${\displaystyle \alpha }$ is known as a damping factor.

UsuallyS is asparse matrix and for modern directed networks it has only about ten nonzero elements in a line or column, thus only about 10N multiplications are needed to multiply a vector by matrix G.^[2][3]

An example of the matrix${\displaystyle S}$ construction via Eq.(1) within a simple network is given in the articleCheiRank.

For the actual matrix, Google uses a damping factor${\displaystyle \alpha }$ around 0.85.^[2][3][4] The term${\displaystyle (1-\alpha )}$ gives a surfer probability to jump randomly on any page. The matrix${\displaystyle G}$ belongs to the class ofPerron-Frobenius operators ofMarkov chains.^[2] The examples of Google matrix structure are shown in Fig.1 for Wikipedia articles hyperlink network in 2009 at small scale and in Fig.2 for University of Cambridge network in 2006 at large scale.

For there is only one maximal eigenvalue${\displaystyle \lambda =1}$ with the corresponding right eigenvector which has non-negative elements${\displaystyle P_i}$ which can be viewed as stationary probability distribution.^[2] These probabilities ordered by their decreasing values give the PageRank vector${\displaystyle P_i}$ with the PageRank${\displaystyle K_i}$ used by Google search to rank webpages. Usually one has for the World Wide Web that${\displaystyle P\propto 1/K^{\beta }}$ with${\displaystyle \beta \approx 0.9}$. The number of nodes with a given PageRank value scales as${\displaystyle N_P\propto 1/P^{\nu }}$ with the exponent${\displaystyle \nu =1+1/\beta \approx 2.1}$.^[6][7] The left eigenvector at${\displaystyle \lambda =1}$ has constant matrix elements. With all eigenvalues move as${\displaystyle {\lambda }_i\to \alpha {\lambda }_i}$ except the maximal eigenvalue${\displaystyle \lambda =1}$, which remains unchanged.^[2] The PageRank vector varies with${\displaystyle \alpha }$ but other eigenvectors with remain unchanged due to their orthogonality to the constant left vector at${\displaystyle \lambda =1}$. The gap between${\displaystyle \lambda =1}$ and other eigenvalue being${\displaystyle 1-\alpha \approx 0.15}$ gives a rapid convergence of a random initial vector to the PageRank approximately after 50 multiplications on${\displaystyle G}$ matrix.

At${\displaystyle \alpha =1}$ the matrix${\displaystyle G}$has generally many degenerate eigenvalues${\displaystyle \lambda =1}$(see e.g. [6]^[8]). Examples of the eigenvalue spectrum of the Google matrix of various directed networks is shown in Fig.3 from^[5] and Fig.4 from.^[8]

The Google matrix can be also constructed for the Ulam networks generated by the Ulam method [8] for dynamical maps. The spectral properties of such matrices are discussed in [9,10,11,12,13,15].^[5][9] In a number of cases the spectrum is described by the fractal Weyl law [10,12].

The Google matrix can be constructed also for other directed networks, e.g. for the procedure call network of the Linux Kernel software introduced in [15]. In this case the spectrum of${\displaystyle \lambda }$ is described by the fractal Weyl law with the fractal dimension${\displaystyle d\approx 1.3}$ (see Fig.5 from^[9]).Numerical analysis shows that the eigenstates of matrix${\displaystyle G}$ are localized (see Fig.6 from^[9]).Arnoldi iteration method allows to compute many eigenvalues and eigenvectors for matrices of rather large size [13].^[5][9]

Other examples of${\displaystyle G}$ matrix include the Google matrix of brain [17]and business process management [18], see also.^[1] Applications of Google matrix analysis toDNA sequences is described in [20]. Such a Google matrix approach allows also to analyze entanglement of cultures via ranking of multilingual Wikipedia articles abouts persons [21]

The Google matrix with damping factor was described bySergey Brin andLarry Page in 1998 [22], see also articles on PageRank history [23], [24].

• CheiRank
• Arnoldi iteration
• Markov chain
• Transfer operator
• Perron–Frobenius theorem
• Web search engines

• Google matrix at Scholarpedia
• Google PR Shut Down
• Video lectures at IHES Workshop "Google matrix: fundamental, applications and beyond", Oct 2018

• Google Search
• Link analysis
• Markov models

• Articles with short description
• Short description matches Wikidata
• Wikipedia articles needing context from March 2019
• All Wikipedia articles needing context
• All pages needing cleanup
• Wikipedia references cleanup from December 2014
• All articles needing references cleanup
• Articles covered by WikiProject Wikify from December 2014
• All articles covered by WikiProject Wikify
• Articles with multiple maintenance issues