A Superintroduction to Google Matrices for Undergraduates Kazuyuki FUJII ∗ and Hiroshi OIKE † 5 ∗International College of Arts and Sciences 1 0 2 Yokohama City University n a Yokohama, 236–0027 J 8 Japan ] I S †Takado 85–5, Yamagata, 990–2464 . s c [ Japan 1 v 7 6 4 Abstract 3 0 1. Inthispaperweconsiderso-calledGooglematricesandshowthatalleigenvalues(λ) 0 5 ofthemhaveafundamentalproperty|λ| ≤ 1. Thestochasticeigenvector corresponding 1 v: to λ = 1 called the PageRank vector plays a central role in the Google’s software. We i X study it in detail and present some important problems. r a The purpose of the paper is to make the heart of Google clearer for undergrad- uates. Keywords : google matrices; eigenvalue 1; pagerank vector; linear algebra Mathematics Subject Classification 2010 : 05C50; 65F50; ? ∗E-mail address : [email protected] †E-mail address : [email protected] 1 1 Introduction Googleis one of important tools to analyze Modern Society. In this paper we want to explain a secret of Google, which is “the heart of Google’s software”, to undergraduates. AlthoughwearenotexpertsofIT(InformationTechnology)thesecretisclearlyexpressed in terms of Linear Algebra in Mathematics. However, it is almost impossible to solve the linear algebra version explicitly, so we need some approximate method. First, we give a fundamental lemma to understand a Google matrix (see the definition in the text) and present an important problem to define a realistic Google matrix (in our terminology). The problem is a challenging one for young researchers. For such a matrix we can use the power method to obtain the PageRank vector. Second, we pick up an interesting example in [1] and calculate it thoroughly by use of MATHEMATICA. A good example and a thorough calculation help undergraduates to understand. Last, we show anexample which does not give the PageRank vector in terms of the power method with usual initial vector when H is not a realistic Google matrix. For this case we treat the power method with another initial vector and present a general problem. We expect that undergraduates will cry out “I got Google !” after reading the paper. 2 Main Result We introduce a Google matrix (realistic Google matrix) and study its key property. We consider a collection of web pages with links (for example, a homepage and some homepages cited in it). See the figure in the next section (eight web pages with several links). If a page has k links we give the equal weight 1 to each link and construct a column k vector consisting of these weights. See the figure once more. For example, since the page 4 links to the pages 2, 5 and 6 (three links) each weight is 1. Therefore we obtain the column 3 vector like 2 0   1 < 2  3     0        0   page 4 −→    1 < 5 3      1 < 6  3     0       0      As a result, the collection of web pages gives a square matrix H = (H ); H ≥ 0, H = 1 (2.1) ij ij ij Xi which we will call a Google matrix. Note that H = 0 for all i (we prohibit the self-citation). ii Fromthedefinitionitisasparsematrixbecausethenumber oflinksstartingfromawebpage is in general small compared to the number of webpages. If we set J = (1,1,··· ,1)T where T is the transpose (of a vector or a matrix) then it is easy to see HTJ = J (2.2) because row vectors of HT are the transpose of column vectors of H like 1 1 1 page 4 −→ 0, ,0,0, , ,0,0 . (cid:18) 3 3 3 (cid:19) From this we know that 1 is an eigenvalue of HT. By the way, the eigenvalues of H are equal to those of HT because 0 = |λE −H| = |λE −HT| , so we conclude that 1 is just an eigenvalue of H. Therefore, we have the equation HI = I (2.3) 3 where we assume that the eigenvector I is stochastic (the sum of all entries is 1). This I is called the PageRank vector and plays a central role in Google. Now, we give a fundamental lemma to Google matrices : Lemma Let λ be any eigenvalue of a Google matrix H. Then we have |λ| ≤ 1. (2.4) The proof is easy and is derived from the Gerschgorin’s (circle) theorem [2]. Note that the eigenvalues of H are equal to those of HT and the sum of all entries of each row is 1 (see for example (3.2)). Namely, n n (HT) = H = 1 and (HT) = H = 0 (2.5) ij ji ii ii Xj=1 Xj=1 for all i and j. We are in a position to state the Gerschgorin’s theorem. Let A = (a ) be a n×n complex ij (real in our case) matrix, and we set n R = |a | i ij j=X1, j6=i and D(a ;R ) = {z ∈ C | |z −a | ≤ R } ii i ii i for each i. This is a closed disc centered at a with radius R called the Gerschgorin’s disc. ii i Theorem (Gerschgorin) For any eigenvalue λ of A we have n λ ∈ D(a ;R ). (2.6) ii i i[=1 The proof is simple. Let us consider the equation Ax = λx (x 6= 0) (2.7) and |x | be the maximum i x j |x | = max{|x |,|x |,··· ,|x |} =6 0 =⇒ | | ≤ 1. i 1 2 n x i 4 From (2.7) we have n n a x = λx ⇐⇒ a x = λx −a x = (λ−a )x . ij j i ij j i ii i ii i Xj=1 j=X1, j6=i x 6= 0 gives i n x j λ−a = a ii ij x j=X1, j6=i i and we have n n n n x x x j j j |λ−a | = | a | ≤ |a | = |a || | ≤ |a | = R . ii ij ij ij ij i x x x j=X1, j6=i i j=X1, j6=i i j=X1, j6=i i j=X1, j6=i This means λ ∈ D(a ;R ) for some i and completes the proof. ii i Finally, let us complete our lemma. In our case H ≥ 0, H = 0 and R = 1 for all i and ij ii i j, so these give the result |λ| ≤ 1 for any eigenvalue λ of H. This is indeed a fundamental property of Google matrices. A comment is in order. The lemma must have been known. However, we could not find such a reference within our efforts. Let us go ahead. In order to construct the eigenvector I in (2.3) a method called the power method is very convenient for a sparse matrix H of huge size. To calculate the characteristic polynomial is actually impossible. The method is very simple, [1]. A sequence {I } is defined recurrently by n In = HIn−1 and I0 = e1 (2.8) where the initial vector is e1 = (1,0,··· ,0)T, which is usually standard. This is also rewrit- ten as In = HnI0 = Hne1. If {I } converges to I then we obtain the equation (2.3) like n HI = H(lim I ) = lim HI = lim I = I. n n n+1 n→∞ n→∞ n→∞ 5 In order that the power method works correctly some assumption on H is required. Namely, (♥) For a set of eigenvalues {λ = 1,λ ,··· ,λ } we assume 1 2 n λ = 1 > |λ | ≥ ··· ≥ |λ |. (2.9) 1 2 n Note that 1 is a simple root. The assumption may be strong. If a Google matrix H satisfies (2.9) we call H a realistic Google matrix. Now, let us present an important Problem For a huge sparse matrix H propose a method to find or to estimate the second eigenvalue λ without calculating the characteristic polynomial. 2 As far as we know such a method has not been given in Mathematical Physics or in Quantum Mechanics. This is a challenging problem for mathematical physicists. 3 Example We consider an interesting example given in [1] and calculate it thoroughly by use of MATH- EMATICA. A good example helps undergraduates to understand a model deeply. In this section we need some results from Linear Algebra, so see for example [3] or [4] (we don’t know a standard textbook of Linear Algebra in Europe or America or etc). Example : a collection of web pages with links1 1 3 5 7 2 4 6 8 1 It is not easy for us to draw a (free) curve by use of the free soft WinTpic. 6 The Google matrix for this graph is given by 0 0 0 0 0 0 1 0  3  1 0 1 1 0 0 0 0  2 2 3     1 0 0 0 0 0 0 0   2      0 1 0 0 0 0 0 0   H =   (3.1)  0 0 1 1 0 0 1 0  2 3 3      0 0 0 1 1 0 0 1   3 3 2     0 0 0 0 1 0 0 1   3 2     0 0 0 0 1 1 1 0   3 3    and its transpose is 0 1 1 0 0 0 0 0  2 2  0 0 0 1 0 0 0 0      0 1 0 0 1 0 0 0   2 2     0 1 0 0 1 1 0 0  HT =  3 3 3 . (3.2)  0 0 0 0 0 1 1 1  3 3 3      0 0 0 0 0 0 0 1       1 0 0 0 1 0 0 1   3 3 3     0 0 0 0 0 1 1 0   2 2    If we define a stochastic vector T 1 1 1 1 1 1 1 1 J = , , , , , , , (cid:18)8 8 8 8 8 8 8 8(cid:19) it is easy to see HTJ = J. (3.3) Let us study H from the mathematical view point by use of MATHEMATICA. The characteristic polynomial of H is given by 7 f(λ) = |λE −H| λ 0 0 0 0 0 −1 0 (cid:12) 3 (cid:12) (cid:12) (cid:12) (cid:12) −1 λ −1 −1 0 0 0 0 (cid:12) (cid:12) 2 2 3 (cid:12) (cid:12) (cid:12) (cid:12) −1 0 λ 0 0 0 0 0 (cid:12) (cid:12) 2 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) 0 −1 0 λ 0 0 0 0 (cid:12) (cid:12) = (cid:12) (cid:12) (cid:12)(cid:12) 0 0 −1 −1 λ 0 −1 0 (cid:12)(cid:12) 2 3 3 (cid:12) (cid:12) (cid:12) (cid:12) (cid:12) 0 0 0 −1 −1 λ 0 −1 (cid:12) (cid:12) 3 3 2 (cid:12) (cid:12) (cid:12) (cid:12) 0 0 0 0 −1 0 λ −1 (cid:12) (cid:12) 3 2 (cid:12) (cid:12) (cid:12) (cid:12) 0 0 0 0 −1 −1 −1 λ (cid:12) (cid:12) 3 3 (cid:12) (cid:12) (cid:12) (cid:12) 1 1 7 (cid:12) 11 1 (cid:12) 6 5 4 3 2 (cid:12) = λ(λ−1) λ +λ − λ − λ + λ + λ+ . (3.4) (cid:18) 9 6 108 216 72(cid:19) The exact solutions are {λ = 1,λ = 0} and approximate ones (we round off a real number 1 8 to five decimal places like −0.87021··· = −0.8702) are given by λ = −0.8702, λ = −0.5568, 2 3 λ = 0.4251−0.2914i, λ = 0.4251+0.2914i, 4 5 λ = −0.2116−0.2512i, λ = −0.2116+0.2512i. 6 7 From these we have λ = 1 > |λ | > |λ | > |λ | = |λ | > |λ | = |λ | > λ = 0. (3.5) 1 2 3 4 5 6 7 8 H becomes a realistic Google matrix from (2.9). Moreover, the eigenvector for λ = 1 is given by 1 Iˆ= (24,27,12,27,39,81,72,118)T. To check this (by hand) is not difficult and good exercise for undergraduates. Since the sum of all entries of Iˆis 400 the stochastic eigenvector (= the PageRank vector) I becomes 8 24 0.06  400    27 0.0675  400         12   0.03   400         27   0.0675   400    I =   =  . (3.6)  39   0.0975  400          81   0.2025   400         72   0.18   400         118   0.295   400        As a result, the ranking of webpages becomes page 8 > page 6 > page 7 > page 5 > page 2 = page 4 > page 1 > page 3. (3.7) See the figure once more. Here, let us show the power method to obtain the PageRank vector I, which is very useful if a realistic Google matrix is huge. A sequence {I } is defined as n I = HI and I = (1,0,0,0,0,0,0,0)T n n−1 0 or I = HnI . n 0 If the condition |λ | < 1 holds then we have 2 lim I = I n n→∞ because H can be diagonalized to be H = Sdiag(1,λ ,··· ,λ )S−1 =⇒ Hn = Sdiag(1,λn,··· ,λn)S−1 2 8 2 8 with a matrix S consisting of eigenvectors. The speed of convergence depends on |λ |. 2 9 Let us list the calculation (rule : a real number is rounded off to five decimal places) : 0.0601 0.0600 0.0600 0.0600         0.0675 0.0675 0.0675 0.0675                  0.0299   0.0300   0.0300   0.0300                          0.0676 0.0675 0.0675 0.0675         I =  , I =  , I =  , I =   ≡ I. (3.8) 40 45 50 55          0.0976   0.0975   0.0975   0.0975                   0.2022   0.2024   0.2024   0.2025                   0.1797   0.1800   0.1799   0.1800                   0.2954   0.2951   0.2951   0.2950                  The result must be related to the powers of |λ | = 0.87 like 2 40 45 50 55 (0.87) = 0.0038, (0.87) = 0.0019, (0.87) = 0.0009, (0.87) = 0.0005. (3.9) Problem Clarify a relation between I and (0.87)n. n 4 Counter Example We show an example which does not give the PageRank vector in terms of the power method with usual initial vector e when H is not a realistic Google matrix. 1 Example : a collection of web pages with links 1 2 3 4 The Google matrix for this graph is given by 0 1 0 0 2   1 0 1 0 H =  2 . (4.1)    0 1 0 1   2     0 0 1 0   2    10