(************** Content-type: application/mathematica ************** CreatedBy='Mathematica 5.0' Mathematica-Compatible Notebook This notebook can be used with any Mathematica-compatible application, such as Mathematica, MathReader or Publicon. The data for the notebook starts with the line containing stars above. To get the notebook into a Mathematica-compatible application, do one of the following: * Save the data starting with the line of stars above into a file with a name ending in .nb, then open the file inside the application; * Copy the data starting with the line of stars above to the clipboard, then use the Paste menu command inside the application. Data for notebooks contains only printable 7-bit ASCII and can be sent directly in email or through ftp in text mode. Newlines can be CR, LF or CRLF (Unix, Macintosh or MS-DOS style). NOTE: If you modify the data for this notebook not in a Mathematica- compatible application, you must delete the line below containing the word CacheID, otherwise Mathematica-compatible applications may try to use invalid cache data. For more information on notebooks and Mathematica-compatible applications, contact Wolfram Research: web: http://www.wolfram.com email: info@wolfram.com phone: +1-217-398-0700 (U.S.) Notebook reader applications are available free of charge from Wolfram Research. *******************************************************************) (*CacheID: 232*) (*NotebookFileLineBreakTest NotebookFileLineBreakTest*) (*NotebookOptionsPosition[ 15185, 473]*) (*NotebookOutlinePosition[ 15821, 495]*) (* CellTagsIndexPosition[ 15777, 491]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell["\<\ Matrix Computations of PageRank Kurt Bryan and Tanya Leise\ \>", "Title"], Cell[CellGroupData[{ Cell["Link matrix A", "Section"], Cell[CellGroupData[{ Cell[BoxData[ \(\(\( (*\ Example\ with\ page\ 1\ pointing\ to\ pages\ 2, 3, 4; \ page\ 2\ pointing\ to\ pages\ 3, 4; \ page\ 3\ pointing\ to\ page\ 1; \ page\ 4\ pointing\ to\ pages\ 1, 3\ *) \)\(\[IndentingNewLine]\)\(\(A = {{0, 0, 1, 1/2}, {1/3, 0, 0, 0}, {1/3, 1/2, 0, 1/2}, {1/3, 1/2, 0, 0}};\)\[IndentingNewLine] MatrixForm[A]\)\)\)], "Input"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "1", \(1\/2\)}, {\(1\/3\), "0", "0", "0"}, {\(1\/3\), \(1\/2\), "0", \(1\/2\)}, {\(1\/3\), \(1\/2\), "0", "0"} }], "\[NoBreak]", ")"}], Function[ BoxForm`e$, MatrixForm[ BoxForm`e$]]]], "Output"] }, Open ]], Cell[BoxData[ \( (*\ Calculate\ the\ eigenvector\ of\ A\ for\ eigenvalue\ 1\ using\ the\ \ reduced\ echelon\ form\ of\ A - I\ *) \)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(RowReduce[A - IdentityMatrix[4]]\ // \ MatrixForm\)], "Input"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"1", "0", "0", \(-2\)}, {"0", "1", "0", \(-\(2\/3\)\)}, {"0", "0", "1", \(-\(3\/2\)\)}, {"0", "0", "0", "0"} }], "\[NoBreak]", ")"}], Function[ BoxForm`e$, MatrixForm[ BoxForm`e$]]]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ \(m = 6 {2, 2/3, 3/2, 1}\), "\[IndentingNewLine]", \(q = m/Sum[m[\([i]\)], {i, 1, 4}]\ (*\ Use\ rankings\ that\ sum\ to\ one\ *) \), "\[IndentingNewLine]", \(N[%]\)}], "Input"], Cell[BoxData[ \({12, 4, 9, 6}\)], "Output"], Cell[BoxData[ \({12\/31, 4\/31, 9\/31, 6\/31}\)], "Output"], Cell[BoxData[ \({0.3870967741935484`, 0.12903225806451613`, 0.2903225806451613`, 0.1935483870967742`}\)], "Output"] }, Open ]], Cell[BoxData[ \( (*\ Using\ Eigensystem\ command\ to\ find\ eigenvector, \ which\ is\ given\ as\ a\ unit\ vector\ *) \)], "Input"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(ev = Eigensystem[N[A]];\)\), "\[IndentingNewLine]", \(MatrixForm[ev]\)}], "Input"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ { "1.0000000000000004`", \(\(-0.36062333350611026`\) + 0.4109755454950539`\ \[ImaginaryI]\), \ \(\(-0.36062333350611026`\) - 0.4109755454950539`\ \[ImaginaryI]\), \ \(-0.2787533329877789`\)}, {\({0.7210101217513316`, 0.24033670725044398`, 0.5407575913134988`, 0.36050506087566586`}\), \({\(-0.7552157082699408`\) + 0.`\ \[ImaginaryI], \(\(0.30367210388485816`\)\(\ \[InvisibleSpace]\)\) + 0.34607247216185955`\ \[ImaginaryI], \ \(\(0.09315320807988628`\)\(\[InvisibleSpace]\)\) - 0.27467790318348567`\ \[ImaginaryI], \ \(\(0.35839039630519626`\)\(\[InvisibleSpace]\)\) - 0.07139456897837397`\ \[ImaginaryI]}\), \ \({\(-0.7552157082699408`\) + 0.`\ \[ImaginaryI], \(\(0.30367210388485816`\)\(\ \[InvisibleSpace]\)\) - 0.34607247216185955`\ \[ImaginaryI], \ \(\(0.09315320807988628`\)\(\[InvisibleSpace]\)\) + 0.27467790318348567`\ \[ImaginaryI], \ \(\(0.35839039630519626`\)\(\[InvisibleSpace]\)\) + 0.07139456897837397`\ \[ImaginaryI]}\), \ \({0.5064856213328005`, \(-0.6056556835920182`\), \(-0.38153917237302665`\), 0.4807092346322444`}\)} }], "\[NoBreak]", ")"}], Function[ BoxForm`e$, MatrixForm[ BoxForm`e$]]]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ \(\(m = ev[\([2, 1]\)];\)\), "\[IndentingNewLine]", \(q = \(\(m\)\(/\)\(Sum[m[\([i]\)], {i, 1, 4}]\)\(\ \)\( (*\ adjust\ so\ rankings\ sum\ to\ one, \ to\ show\ this\ is\ same\ as\ found\ before\ *) \)\)\)}], "Input"], Cell[BoxData[ \({0.3870967741935483`, 0.12903225806451618`, 0.2903225806451613`, 0.1935483870967742`}\)], "Output"] }, Open ]], Cell[BoxData[ \( (*\ Alternatively, \ can\ compute\ using\ power\ method\ *) \)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(s = {1, 1, 1, 1}/4; \ (*\ Initial\ "\"\ *) \[IndentingNewLine]MatrixPower[N[A], 40] . s\)], "Input"], Cell[BoxData[ \({0.387096774199987`, 0.1290322580610693`, 0.29032258064504757`, 0.19354838709389538`}\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Improved matrix M", "Section"], Cell[CellGroupData[{ Cell[BoxData[ \(M = .85\ A + .15 {s, s, s, s}; MatrixForm[M]\)], "Input"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0.0375`", "0.0375`", "0.8875`", "0.46249999999999997`"}, {"0.3208333333333333`", "0.0375`", "0.0375`", "0.0375`"}, {"0.3208333333333333`", "0.46249999999999997`", "0.0375`", "0.46249999999999997`"}, {"0.3208333333333333`", "0.46249999999999997`", "0.0375`", "0.0375`"} }], "\[NoBreak]", ")"}], Function[ BoxForm`e$, MatrixForm[ BoxForm`e$]]]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(ev = Eigensystem[M]; MatrixForm[ev]\)], "Input"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ { "1.`", \(\(-0.30652983348019414`\) + 0.349329213670796`\ \[ImaginaryI]\), \ \(\(-0.30652983348019414`\) - 0.349329213670796`\ \[ImaginaryI]\), \ \(-0.23694033303961207`\)}, {\({\(-0.6964830662945717`\), \(-0.26828095938109875`\), \ \(-0.5447780231432439`\), \(-0.38230036711806575`\)}\), \ \({\(\(0.7552157082699408`\)\(\[InvisibleSpace]\)\) + 0.`\ \[ImaginaryI], \(-0.30367210388485855`\) - 0.3460724721618594`\ \[ImaginaryI], \(-0.09315320807988631`\ \) + 0.2746779031834855`\ \[ImaginaryI], \(-0.35839039630519637`\) + 0.0713945689783738`\ \[ImaginaryI]}\), \ \({\(\(0.7552157082699408`\)\(\[InvisibleSpace]\)\) + 0.`\ \[ImaginaryI], \(-0.30367210388485855`\) + 0.3460724721618594`\ \[ImaginaryI], \(-0.09315320807988631`\ \) - 0.2746779031834855`\ \[ImaginaryI], \(-0.35839039630519637`\) - 0.0713945689783738`\ \[ImaginaryI]}\), \ \({0.5064856213328003`, \(-0.6056556835920185`\), \(-0.38153917237302626`\), 0.4807092346322442`}\)} }], "\[NoBreak]", ")"}], Function[ BoxForm`e$, MatrixForm[ BoxForm`e$]]]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ \(\(m = ev[\([2, 1]\)];\)\), "\[IndentingNewLine]", \(q = \(\(m\)\(/\)\(Sum[m[\([i]\)], {i, 1, 4}]\)\(\ \)\( (*\ adjust\ so\ rankings\ sum\ to\ one\ *) \)\)\)}], "Input"], Cell[BoxData[ \({0.3681506770476027`, 0.14180935849682078`, 0.2879616285976068`, 0.2020783358579696`}\)], "Output"] }, Open ]], Cell[BoxData[ \( (*\ Alternatively, \ can\ use\ power\ method\ or\ iteration\ of\ vector\ formula\ *) \)], \ "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixPower[M, 40] . s\)], "Input"], Cell[BoxData[ \({0.36815067704761006`, 0.14180935849681564`, 0.2879616285976057`, 0.20207833585796514`}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ \(\(x = s;\)\), "\[IndentingNewLine]", \(For[i = 1, i \[LessEqual] 40, x = .85 A . x + .15\ s, \(i++\)]\), "\[IndentingNewLine]", \(x\)}], "Input"], Cell[BoxData[ \({0.3681506770476112`, 0.141809358496816`, 0.28796162859760654`, 0.20207833585796572`}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ \(Sum[\(ev[\([2, 2]\)]\)[\([i]\)], {i, 1, 4}]\ (*\ other\ eigenvectors\ sum\ to\ zero\ *) \), "\[IndentingNewLine]", \(Sum[\(ev[\([2, 3]\)]\)[\([i]\)], {i, 1, 4}]\ \), "\[IndentingNewLine]", \(Sum[\(ev[\([2, 4]\)]\)[\([i]\)], {i, 1, 4}]\ \)}], "Input"], Cell[BoxData[ \(\(-4.440892098500626`*^-16\) - 6.938893903907228`*^-17\ \[ImaginaryI]\)], "Output"], Cell[BoxData[ \(\(-4.440892098500626`*^-16\) + 6.938893903907228`*^-17\ \[ImaginaryI]\)], "Output"], Cell[BoxData[ \(\(-2.7755575615628914`*^-16\)\)], "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Convergence of power method", "Section"], Cell[CellGroupData[{ Cell[BoxData[{ \(\(A = {{0, 1, 0, 0, 0}, {1, 0, 0, 0, 0}, {0, 0, 0, 1, 1/2}, {0, 0, 1, 0, 1/2}, {0, 0, 0, 0, 0}};\)\), "\[IndentingNewLine]", \(\(s = {1, 1, 1, 1, 1}/5;\)\), "\[IndentingNewLine]", \(M = .85\ A + .15 {s, s, s, s, s}; MatrixForm[M]\)}], "Input"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0.03`", "0.88`", "0.03`", "0.03`", "0.03`"}, {"0.88`", "0.03`", "0.03`", "0.03`", "0.03`"}, {"0.03`", "0.03`", "0.03`", "0.88`", "0.45499999999999996`"}, {"0.03`", "0.03`", "0.88`", "0.03`", "0.45499999999999996`"}, {"0.03`", "0.03`", "0.03`", "0.03`", "0.03`"} }], "\[NoBreak]", ")"}], Function[ BoxForm`e$, MatrixForm[ BoxForm`e$]]]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(ev = Eigensystem[M]; MatrixForm[ev]\)], "Input"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ { "0.9999999999999992`", \(-0.8500000000000002`\), \ \(-0.8499999999999999`\), "0.8499999999999992`", \(-6.427691088436098`*^-18\)}, {\({0.4054285427382974`, 0.40542854273829704`, 0.5777356734020742`, 0.577735673402074`, 0.060814281410744575`}\), \({\(-0.012192106687332787`\), 0.012192106687332787`, \(-0.7070016637424023`\), 0.7070016637424024`, \(-1.1509576468566438`*^-16\)}\), \ \({0.7071067811865475`, \(-0.7071067811865475`\), \ \(-6.892399098768545`*^-17\), 2.87154699874316`*^-17, 1.7127851428140998`*^-16}\), \({0.5`, 0.5000000000000003`, \(-0.5`\), \(-0.4999999999999999`\), 5.335900186870508`*^-17}\), \({\(-2.990080171523863`*^-17\), \ \(-1.0553321100709951`*^-16\), 0.4082482904638633`, 0.4082482904638632`, \(-0.8164965809277258`\)}\)} }], "\[NoBreak]", ")"}], Function[ BoxForm`e$, MatrixForm[ BoxForm`e$]]]], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ \(\(m = ev[\([2, 1]\)];\)\), "\[IndentingNewLine]", \(q = \(\(m\)\(/\)\(Sum[m[\([i]\)], {i, 1, 5}]\)\(\ \)\( (*\ adjust\ so\ rankings\ sum\ to\ one\ *) \)\)\)}], "Input"], Cell[BoxData[ \({0.19999999999999998`, 0.1999999999999998`, 0.28500000000000014`, 0.2850000000000001`, 0.029999999999999978`}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ \(MatrixPower[M, 50] . s\)], "Input"], Cell[BoxData[ \({0.20000000000000015`, 0.20000000000000012`, 0.28500000000000025`, 0.28500000000000014`, 0.030000000000000023`}\)], "Output"] }, Open ]], Cell[BoxData[ \( (*\ q\ is\ eigenvector\ with\ eigenvalue\ 1; \ M^k\ times\ an\ initial\ guess\ converges\ to\ q\ *) \)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(\(\(x0\)\(=\)\({ .24, .31, .08, .18, .19}\)\(\ \)\( (*\ initial\ guess\ *) \)\)\)], "Input"], Cell[BoxData[ \({0.24`, 0.31`, 0.08`, 0.18`, 0.19`}\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ \(Norm[MatrixPower[M, 0] . x0 - q, 1]\), "\[IndentingNewLine]", \(Norm[MatrixPower[M, 1] . x0 - q, 1]\), "\[IndentingNewLine]", \(Norm[MatrixPower[M, 5] . x0 - q, 1]\), "\[IndentingNewLine]", \(Norm[MatrixPower[M, 10] . x0 - q, 1]\), "\[IndentingNewLine]", \(Norm[MatrixPower[M, 50] . x0 - q, 1]\)}], "Input"], Cell[BoxData[ \(0.6200000000000004`\)], "Output"], Cell[BoxData[ \(0.25500000000000045`\)], "Output"], Cell[BoxData[ \(0.13311159375000045`\)], "Output"], Cell[BoxData[ \(0.05906232130221714`\)], "Output"], Cell[BoxData[ \(0.00008872939911426861`\)], "Output"] }, Open ]], Cell[BoxData[ \( (*\ The\ rate\ at\ which\ these\ powers\ converge\ to\ q\ is\ dominated\ by\ \ the\ second\ largest\ eigenvalue\ of\ M\ *) \)], "Input"], Cell[CellGroupData[{ Cell[BoxData[ \(Abs[ev[\([1, 2]\)]]\)], "Input"], Cell[BoxData[ \(0.8500000000000002`\)], "Output"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ \(Norm[MatrixPower[M, 1] . x0 - q, 1]/ Norm[MatrixPower[M, 0] . x0 - q, 1]\), "\[IndentingNewLine]", \(Norm[MatrixPower[M, 5] . x0 - q, 1]/ Norm[MatrixPower[M, 4] . x0 - q, 1]\), "\[IndentingNewLine]", \(Norm[MatrixPower[M, 10] . x0 - q, 1]/ Norm[MatrixPower[M, 9] . x0 - q, 1]\), "\[IndentingNewLine]", \(Norm[MatrixPower[M, 20] . x0 - q, 1]/ Norm[MatrixPower[M, 19] . x0 - q, 1]\)}], "Input"], Cell[BoxData[ \(0.4112903225806456`\)], "Output"], Cell[BoxData[ \(0.8500000000000002`\)], "Output"], Cell[BoxData[ \(0.8499999999999991`\)], "Output"], Cell[BoxData[ \(0.8499999999999915`\)], "Output"] }, Open ]] }, Open ]] }, Open ]] }, FrontEndVersion->"5.0 for Macintosh", ScreenRectangle->{{0, 1276}, {0, 832}}, WindowSize->{1140, 805}, WindowMargins->{{4, Automatic}, {Automatic, 1}} ] (******************************************************************* Cached data follows. If you edit this Notebook file directly, not using Mathematica, you must remove the line containing CacheID at the top of the file. The cache data will then be recreated when you save this file from within Mathematica. *******************************************************************) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[CellGroupData[{ Cell[1776, 53, 83, 3, 168, "Title"], Cell[CellGroupData[{ Cell[1884, 60, 32, 0, 87, "Section"], Cell[CellGroupData[{ Cell[1941, 64, 390, 6, 90, "Input"], Cell[2334, 72, 350, 9, 141, "Output"] }, Open ]], Cell[2699, 84, 153, 3, 33, "Input"], Cell[CellGroupData[{ Cell[2877, 91, 83, 1, 33, "Input"], Cell[2963, 94, 338, 9, 123, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[3338, 108, 213, 4, 71, "Input"], Cell[3554, 114, 47, 1, 33, "Output"], Cell[3604, 117, 63, 1, 50, "Output"], Cell[3670, 120, 126, 2, 33, "Output"] }, Open ]], Cell[3811, 125, 141, 2, 33, "Input"], Cell[CellGroupData[{ Cell[3977, 131, 110, 2, 52, "Input"], Cell[4090, 135, 1497, 31, 65, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[5624, 171, 263, 4, 52, "Input"], Cell[5890, 177, 126, 2, 33, "Output"] }, Open ]], Cell[6031, 182, 101, 2, 33, "Input"], Cell[CellGroupData[{ Cell[6157, 188, 143, 3, 52, "Input"], Cell[6303, 193, 126, 2, 33, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[6478, 201, 36, 0, 87, "Section"], Cell[CellGroupData[{ Cell[6539, 205, 79, 1, 33, "Input"], Cell[6621, 208, 529, 11, 105, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[7187, 224, 68, 1, 33, "Input"], Cell[7258, 227, 1322, 25, 65, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[8617, 257, 205, 3, 52, "Input"], Cell[8825, 262, 126, 2, 33, "Output"] }, Open ]], Cell[8966, 267, 128, 3, 33, "Input"], Cell[CellGroupData[{ Cell[9119, 274, 55, 1, 33, "Input"], Cell[9177, 277, 128, 2, 33, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[9342, 284, 186, 4, 71, "Input"], Cell[9531, 290, 126, 2, 33, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[9694, 297, 298, 5, 71, "Input"], Cell[9995, 304, 110, 2, 36, "Output"], Cell[10108, 308, 110, 2, 36, "Output"], Cell[10221, 312, 63, 1, 36, "Output"] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[10333, 319, 46, 0, 87, "Section"], Cell[CellGroupData[{ Cell[10404, 323, 289, 4, 90, "Input"], Cell[10696, 329, 504, 10, 125, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[11237, 344, 68, 1, 33, "Input"], Cell[11308, 347, 1120, 21, 71, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[12465, 373, 205, 3, 52, "Input"], Cell[12673, 378, 150, 2, 33, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[12860, 385, 55, 1, 33, "Input"], Cell[12918, 388, 152, 2, 33, "Output"] }, Open ]], Cell[13085, 393, 141, 2, 33, "Input"], Cell[CellGroupData[{ Cell[13251, 399, 125, 2, 33, "Input"], Cell[13379, 403, 69, 1, 33, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[13485, 409, 348, 5, 109, "Input"], Cell[13836, 416, 53, 1, 33, "Output"], Cell[13892, 419, 54, 1, 33, "Output"], Cell[13949, 422, 54, 1, 33, "Output"], Cell[14006, 425, 54, 1, 33, "Output"], Cell[14063, 428, 57, 1, 33, "Output"] }, Open ]], Cell[14135, 432, 164, 3, 33, "Input"], Cell[CellGroupData[{ Cell[14324, 439, 52, 1, 33, "Input"], Cell[14379, 442, 53, 1, 33, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[14469, 448, 452, 8, 90, "Input"], Cell[14924, 458, 53, 1, 33, "Output"], Cell[14980, 461, 53, 1, 33, "Output"], Cell[15036, 464, 53, 1, 33, "Output"], Cell[15092, 467, 53, 1, 33, "Output"] }, Open ]] }, Open ]] }, Open ]] } ] *) (******************************************************************* End of Mathematica Notebook file. *******************************************************************)