Menu
Home Explore People Places Arts History Plants & Animals Science Life & Culture Technology
On this page
Google matrix
Stochastic matrix representing links between entities

A Google matrix is a particular stochastic matrix that is used by Google's PageRank 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 the power method. However, in order for the power method to converge, the matrix must be stochastic, irreducible and aperiodic.

Related Image Collections Add Image
Profiles
1 Image
We don't have any YouTube videos related to Google matrix yet.
We don't have any PDF documents related to Google matrix yet.
We don't have any Books related to Google matrix yet.
We don't have any archived web articles related to Google matrix yet.

Adjacency matrix A and Markov matrix S

In order to generate the Google matrix G, we must first generate an adjacency matrix A which represents the relations between pages or nodes.

Assuming there are N pages, we can fill out A by doing the following:

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

Construction of Google matrix G

Then the final Google matrix G can be expressed via S as:

G i j = α S i j + ( 1 − α ) 1 N ( 1 ) {\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.

Usually S is a sparse 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.12

Examples of Google matrix

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

For the actual matrix, Google uses a damping factor α {\displaystyle \alpha } around 0.85.345 The term ( 1 − α ) {\displaystyle (1-\alpha )} gives a surfer probability to jump randomly on any page. The matrix G {\displaystyle G} belongs to the class of Perron-Frobenius operators of Markov chains.6 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.

Spectrum and eigenstates of G matrix

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

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

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].1415 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 d ≈ 1.3 {\displaystyle d\approx 1.3} (see Fig.5 from 16). Numerical analysis shows that the eigenstates of matrix G {\displaystyle G} are localized (see Fig.6 from 17). Arnoldi iteration method allows to compute many eigenvalues and eigenvectors for matrices of rather large size [13].1819

Other examples of G {\displaystyle G} matrix include the Google matrix of brain [17] and business process management [18], see also.20 Applications of Google matrix analysis to DNA 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]

Historical notes

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

See also

References

  1. Langville, Amy N.; Meyer, Carl (2006). Google's PageRank and Beyond. Princeton University Press. ISBN 978-0-691-12202-1. 978-0-691-12202-1 ↩

  2. Austin, David (2008). "How Google Finds Your Needle in the Web's Haystack". AMS Feature Columns. http://www.ams.org/samplings/feature-column/fcarc-pagerank ↩

  3. Langville, Amy N.; Meyer, Carl (2006). Google's PageRank and Beyond. Princeton University Press. ISBN 978-0-691-12202-1. 978-0-691-12202-1 ↩

  4. Austin, David (2008). "How Google Finds Your Needle in the Web's Haystack". AMS Feature Columns. http://www.ams.org/samplings/feature-column/fcarc-pagerank ↩

  5. Law, Edith (2008-10-09). "PageRank Lecture 12" (PDF). https://www.cs.cmu.edu/~elaw/pagerank.pdf ↩

  6. Langville, Amy N.; Meyer, Carl (2006). Google's PageRank and Beyond. Princeton University Press. ISBN 978-0-691-12202-1. 978-0-691-12202-1 ↩

  7. Langville, Amy N.; Meyer, Carl (2006). Google's PageRank and Beyond. Princeton University Press. ISBN 978-0-691-12202-1. 978-0-691-12202-1 ↩

  8. Donato, Debora; Laura, Luigi; Leonardi, Stefano; Millozzi, Stefano (2004-03-30). "Large scale properties of the Webgraph" (PDF). European Physical Journal B. 38 (2): 239–243. Bibcode:2004EPJB...38..239D. CiteSeerX 10.1.1.104.2136. doi:10.1140/epjb/e2004-00056-6. S2CID 10640375. http://www.cosinproject.eu/publications/donato-epjb38-2004.pdf ↩

  9. Pandurangan, Gopal; Ranghavan, Prabhakar; Upfal, Eli (2005). "Using PageRank to Characterize Web Structure" (PDF). Internet Mathematics. 3 (1): 1–20. doi:10.1080/15427951.2006.10129114. S2CID 101281. http://cs.brown.edu/research/pubs/pdfs/2005/Pandurangan-2005-UPC.pdf ↩

  10. Langville, Amy N.; Meyer, Carl (2006). Google's PageRank and Beyond. Princeton University Press. ISBN 978-0-691-12202-1. 978-0-691-12202-1 ↩

  11. Georgeot, Bertrand; Giraud, Olivier; Shepelyansky, Dima L. (2010-05-25). "Spectral properties of the Google matrix of the World Wide Web and other directed networks". Physical Review E. 81 (5): 056109. arXiv:1002.3342. Bibcode:2010PhRvE..81e6109G. doi:10.1103/PhysRevE.81.056109. PMID 20866299. S2CID 14490804. /wiki/ArXiv_(identifier) ↩

  12. Frahm, K. M.; Georgeot, B.; Shepelyansky, D. L. (2011-11-01). "Universal emergence of PageRank". Journal of Physics A. 44 (46): 465101. arXiv:1105.1062. Bibcode:2011JPhA...44T5101F. doi:10.1088/1751-8113/44/46/465101. S2CID 16292743. /wiki/ArXiv_(identifier) ↩

  13. Georgeot, Bertrand; Giraud, Olivier; Shepelyansky, Dima L. (2010-05-25). "Spectral properties of the Google matrix of the World Wide Web and other directed networks". Physical Review E. 81 (5): 056109. arXiv:1002.3342. Bibcode:2010PhRvE..81e6109G. doi:10.1103/PhysRevE.81.056109. PMID 20866299. S2CID 14490804. /wiki/ArXiv_(identifier) ↩

  14. Frahm, K. M.; Georgeot, B.; Shepelyansky, D. L. (2011-11-01). "Universal emergence of PageRank". Journal of Physics A. 44 (46): 465101. arXiv:1105.1062. Bibcode:2011JPhA...44T5101F. doi:10.1088/1751-8113/44/46/465101. S2CID 16292743. /wiki/ArXiv_(identifier) ↩

  15. Ermann, L.; Chepelianskii, A. D.; Shepelyansky, D. L. (2011). "Fractal Weyl law for Linux Kernel Architecture". European Physical Journal B. 79 (1): 115–120. arXiv:1005.1395. Bibcode:2011EPJB...79..115E. doi:10.1140/epjb/e2010-10774-7. S2CID 445348. /wiki/ArXiv_(identifier) ↩

  16. Ermann, L.; Chepelianskii, A. D.; Shepelyansky, D. L. (2011). "Fractal Weyl law for Linux Kernel Architecture". European Physical Journal B. 79 (1): 115–120. arXiv:1005.1395. Bibcode:2011EPJB...79..115E. doi:10.1140/epjb/e2010-10774-7. S2CID 445348. /wiki/ArXiv_(identifier) ↩

  17. Ermann, L.; Chepelianskii, A. D.; Shepelyansky, D. L. (2011). "Fractal Weyl law for Linux Kernel Architecture". European Physical Journal B. 79 (1): 115–120. arXiv:1005.1395. Bibcode:2011EPJB...79..115E. doi:10.1140/epjb/e2010-10774-7. S2CID 445348. /wiki/ArXiv_(identifier) ↩

  18. Frahm, K. M.; Georgeot, B.; Shepelyansky, D. L. (2011-11-01). "Universal emergence of PageRank". Journal of Physics A. 44 (46): 465101. arXiv:1105.1062. Bibcode:2011JPhA...44T5101F. doi:10.1088/1751-8113/44/46/465101. S2CID 16292743. /wiki/ArXiv_(identifier) ↩

  19. Ermann, L.; Chepelianskii, A. D.; Shepelyansky, D. L. (2011). "Fractal Weyl law for Linux Kernel Architecture". European Physical Journal B. 79 (1): 115–120. arXiv:1005.1395. Bibcode:2011EPJB...79..115E. doi:10.1140/epjb/e2010-10774-7. S2CID 445348. /wiki/ArXiv_(identifier) ↩

  20. Ermann, L.; Chepelianskii, A. D.; Shepelyansky, D. L. (2011). "Towards two-dimensional search engines". Journal of Physics A. 45 (27): 275101. arXiv:1106.6215. Bibcode:2012JPhA...45A5101E. doi:10.1088/1751-8113/45/27/275101. S2CID 14827486. /wiki/ArXiv_(identifier) ↩