{VERSION 6 0 "IBM INTEL NT" "6.0" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 0 0 0 1 }{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 } {PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Text Output" -1 6 1 {CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 2 2 2 2 2 1 2 1 3 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }} {SECT 0 {EXCHG {PARA 0 "" 0 "" {TEXT -1 122 "Notebook to set up, compu te eigenvalues/vectors of the Google matrix. Accompanies \"The $20,000 ,000,000 Eigenvector\" paper." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 29 "restart;\nwith(LinearAlgebra):" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 185 "Choose \"n\" as number of pages in web. The variable \"link\" is a list of pairs [i,j], where \"[i,j]\" means page \"i\" links to p age \"j\". This is the web for the second figure in the paper." }}} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 146 "n := 5: \+ #Number of pages\nlinks := [[1,2],[2,1],[3,4],[4,3],[5,3],[5,4]]; \nA := Matrix(n,n): #Allocate storage" }}{PARA 11 "" 1 " " {XPPMATH 20 "6#>%&linksG7(7$\"\"\"\"\"#7$F(F'7$\"\"$\"\"%7$F,F+7$\" \"&F+7$F/F," }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 44 "Actually set up of link matrix \"A\" in paper." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 440 "#Set all elements of A corresponding to links\nL := nops(links) :\nfor i from 1 to n do\n for k from 1 to L do\n if links[k,1] = i then A[links[k,2],i] := 1; fi:\n od:\nod:\n#Scale each column to sum to one. If any linkless page, its column is all 1/n.\nfor i from 1 to n do\n s := add(A[j,i], j=1..n):\n if s <> 0 then for j from 1 to n do A[j,i] := evalf(A[j,i]/s); od: fi;\n if s = 0 then for j from 1 t o n do A[j,i] := 1.0/n; od: fi;\nod:\nA;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\")/y()>-%'MATRIXG6#7'7'$\"\"!F-$\"\"\"F-F,F,F,7'F.F ,F,F,F,7'F,F,F,F.$\"+++++]!#57'F,F,F.F,F27'F,F,F,F,F,%'MatrixG" }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 151 "Compute dimension of eigenspace V _1(A) and find independent eigenvectors, scaled to non-negative compon ents, sum to 1. Uses Maple's built in commands." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 334 "r := 0:\neigvA := array(1..n):\nQ := Eigenve ctors(A):\neigs := Q[1]:\nfor j from 1 to n do\n if evalf(abs(eigs[j] -1.0)) < 1.0e-6 then r := r + 1; eigvA[r] := Column(Q[2],j): fi;\nod: \nprintf(`V_1(A) is %d dimensional`, r);\nfor j from 1 to r do\n s := add(eigvA[j][k], k=1..n):\n eigvA[j] := map(q->Re(q), eigvA[j]/s);\n print(eigvA[j]);\nod:" }}{PARA 6 "" 1 "" {TEXT -1 23 "V_1(A) is 2 di mensional" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\")+?c?-%'MAT RIXG6#7'7#$\"35P$4:++++&!#=F+7#$\"\"!F1F/F/&%'VectorG6#%'columnG" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\")+Gc?-%'MATRIXG6#7'7#$\" \"!F-F+7#$\"35P$4:++++&!#=F.F+&%'VectorG6#%'columnG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 51 "Choose \"m\" in paper, with m>0, set up the ma trix M" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "m := 0.15:\nM := \+ evalf((1-m)*A + m*Matrix([seq([seq(1/n,j=1..n)],k=1..n)]));" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"MG-%'RTABLEG6%\")kGv?-%'MATRIXG6#7'7'$\" 3!***************H!#>$\"3-+++++++))!#=F.F.F.7'F1F.F.F.F.7'F.F.F.F1$\"3 ;++++++]XF37'F.F.F1F.F67'F.F.F.F.F.%'MatrixG" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 97 "Compute the unique importance eigenvector for the web g iven by the appropriate element of V_1(M):" }}}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 208 "Q2 := Eigenvectors(M):\neigs := Q2[1]:\nfor j from 1 to n do\n if evalf(abs(eigs[j]-1.0)) < 1.0e-6 then eigvM := Column (Q2[2],j): fi;\nod:\ns := add(eigvM[k], k=1..n):\neigvM := evalf(map(q q->Re(qq), eigvM/s),16);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%&eigvMG- %'RTABLEG6%\")+Qc?-%'MATRIXG6#7'7#$\"1FAo++++?!#;7#$\"1GAo++++?F07#$\" 1x@(4+++&GF07#$\"1w@(4+++&GF07#$\"1RL-,+++I!#<&%'VectorG6#%'columnG" } }}{EXCHG {PARA 0 "" 0 "" {TEXT -1 21 "This is the Pagerank." }}} {EXCHG {PARA 0 "" 0 "" {TEXT -1 71 "The power method can also be used \+ to compute the eigenvector, as below:" }}{PARA 0 "" 0 "" {TEXT -1 0 " " }}{PARA 0 "" 0 "" {TEXT -1 151 "Start with a \"random\" initial gues s. In this case a vector x0 with all components 1/n is a good start, \+ since it cannot be orthogonal to the eigenspace" }}}{EXCHG {PARA 0 "> \+ " 0 "" {MPLTEXT 1 0 64 "s := evalf(Vector([seq(1/n, j=1..n)])): #As in the paper\nx := s;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%\"xG-%'RTABLE G6%\")S\\b@-%'MATRIXG6#7'7#$\"+++++?!#5F-F-F-F-&%'VectorG6#%'columnG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 79 "Loop, repeatedly applying M to \+ x. For good measure, rescale at each iteration." }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 189 "for k from 1 to 1000 do\n xnew := (1-m)*A.x + m*s:\n xnew := xnew/Norm(xnew,1): #Scale to maintain x as probabi lity vector\n if Norm(x-xnew,1)<1.0e-6 then break; fi;\n x := xnew; \nod:\nk;\nx;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'RTABLEG6%\")KV'*H-%'MATRIXG6#7'7#$\"35+++++++?! #=F+7#$\"3K++++++]GF.F/7#$\"3!***************H!#>&%'VectorG6#%'columnG " }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}{MARK "1 0 0" 8 } {VIEWOPTS 1 1 0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 } {RTABLE_HANDLES 19877804 20562000 20562800 20752864 20563800 21554940 29964332 }{RTABLE M7R0 I5RTABLE_SAVE/19877804X,%)anythingG6"6"[gl!"%!!!#:"&"&$""!F($"""F(F'F'F'F)F'F'F 'F'F'F'F'F)F'F'F'F)F'F'F'F'$"+++++]!#5F+F'F& } {RTABLE M7R0 I5RTABLE_SAVE/20562000X*%)anythingG6"6"[gl!#%!!!"&"&$"35P$4:++++&!#=F'$""!F+F*F *F& } {RTABLE M7R0 I5RTABLE_SAVE/20562800X*%)anythingG6"6"[gl!#%!!!"&"&$""!F(F'$"35P$4:++++&!#=F)F 'F& } {RTABLE M7R0 I5RTABLE_SAVE/20752864X,%)anythingG6"6"[gl'"%!!!#:"&"&3F9EB851EB851EB83FEC28F5C 28F5C293F9EB851EB851EB83F9EB851EB851EB83F9EB851EB851EB83FEC28F5C28F5C293F9EB851 EB851EB83F9EB851EB851EB83F9EB851EB851EB83F9EB851EB851EB83F9EB851EB851EB83F9EB85 1EB851EB83F9EB851EB851EB83FEC28F5C28F5C293F9EB851EB851EB83F9EB851EB851EB83F9EB8 51EB851EB83FEC28F5C28F5C293F9EB851EB851EB83F9EB851EB851EB83F9EB851EB851EB83F9EB 851EB851EB83FDD1EB851EB851F3FDD1EB851EB851F3F9EB851EB851EB8F& } {RTABLE M7R0 I5RTABLE_SAVE/20563800X*%)anythingG6"6"[gl!#%!!!"&"&$"1FAo++++?!#;$"1GAo++++?F) $"1x@(4+++&GF)$"1w@(4+++&GF)$"1RL-,+++I!#