(* Content-type: application/vnd.wolfram.mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 10.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 158, 7] NotebookDataLength[ 127464, 3463] NotebookOptionsPosition[ 118403, 3182] NotebookOutlinePosition[ 118852, 3201] CellTagsIndexPosition[ 118809, 3198] WindowFrame->Normal*) (* Beginning of Notebook Content *) Notebook[{ Cell[CellGroupData[{ Cell["Project1 (discussion)", "Title", CellChangeTimes->{{3.652698733023584*^9, 3.65269877333524*^9}}], Cell[CellGroupData[{ Cell["The project is based on the Perron-Frobenius Theorem", "Section", CellChangeTimes->{{3.620395501505601*^9, 3.620395502985736*^9}, { 3.620400088473547*^9, 3.620400114341177*^9}, {3.621129621462027*^9, 3.621129629100461*^9}}, FontSize->72], Cell[CellGroupData[{ Cell[TextData[{ StyleBox["Theorem:", FontWeight->"Bold", FontColor->GrayLevel[0]], StyleBox[" ", FontColor->GrayLevel[0]], StyleBox["If M is a positive, column stochastic nxn matrix then the \ following statements are true:", FontSize->48, FontColor->GrayLevel[0]] }], "Subsection", CellChangeTimes->{{3.6204001278932056`*^9, 3.620400184066436*^9}, { 3.652698819987252*^9, 3.652698821953609*^9}}], Cell[CellGroupData[{ Cell[TextData[StyleBox["1 is an eigenvalue of M, of multiplicity one ", FontSize->36]], "ItemNumbered", CellDingbat->"\[FilledSquare]", CellChangeTimes->{{3.620400208082406*^9, 3.620400306668828*^9}, 3.6204003551611156`*^9, {3.620400641006122*^9, 3.620400650937354*^9}, 3.6211277693958607`*^9, {3.697288125108738*^9, 3.697288126612952*^9}}, FontSize->16], Cell[TextData[StyleBox["The eigenvalue 1 is the largest eigenvalue of M; all \ the other eigenvalues of M are strictly less than 1 in absolute value. ", FontSize->36]], "ItemNumbered", CellDingbat->"\[FilledSquare]", CellChangeTimes->{{3.620400208082406*^9, 3.620400306668828*^9}, 3.6204003551611156`*^9, 3.620400641006122*^9}, FontSize->16], Cell[TextData[StyleBox["There exists a unique probabilistic eigenvector w \ corresponding to the eigenvalue 1. ", FontSize->36]], "ItemNumbered", CellDingbat->"\[FilledSquare]", CellChangeTimes->{{3.620400208082406*^9, 3.620400322306418*^9}, { 3.620400375193266*^9, 3.6204004747471943`*^9}, {3.621128387886396*^9, 3.6211283878899307`*^9}}, FontSize->16], Cell[TextData[{ StyleBox["(Power Method Convergence)", FontSize->36, FontWeight->"Bold"], StyleBox[" Let v be a probabilistic vector. Then the sequence v, Mv, ... , M", FontSize->36], Cell[BoxData[ FormBox[ SuperscriptBox["", "k"], TraditionalForm]], FontSize->36], StyleBox["v converges to w as k goes to \[Infinity].", FontSize->36] }], "ItemNumbered", CellDingbat->"\[FilledSquare]", CellChangeTimes->{{3.620400208082406*^9, 3.620400322306418*^9}, { 3.620400375193266*^9, 3.6204004747471943`*^9}, {3.621128387886396*^9, 3.6211284880665293`*^9}, 3.69728996449292*^9}, FontSize->16] }, Open ]] }, Open ]], Cell[TextData[{ "Recall the following definitions:\n ", StyleBox["A square matrix is called", FontColor->GrayLevel[0]], " ", StyleBox["column stochastic", FontSlant->"Italic"], " ", StyleBox["if all its entries are greater than or equal to 0, and the sum of \ the entries in each column is 1.", FontColor->GrayLevel[0]], "\n ", StyleBox["A matrix is called", FontColor->GrayLevel[0]], " ", StyleBox["positive", FontSlant->"Italic"], " ", StyleBox["if all of its entries are strictly greater than 0.", FontColor->GrayLevel[0]], "\n ", StyleBox["A vector is called", FontColor->GrayLevel[0]], " ", StyleBox["probabilistic", FontSlant->"Italic"], " (or a p", StyleBox["robability distribution vector", FontSlant->"Italic"], ") ", StyleBox["if all its entries are greater than or equal to 0 and the sum of \ all entries is 1.", FontColor->GrayLevel[0]], " " }], "Subsection", CellChangeTimes->{{3.6204009066315603`*^9, 3.62040091984623*^9}, { 3.620400957677389*^9, 3.620401130635096*^9}, {3.620401215778606*^9, 3.6204012372737494`*^9}, {3.620439262109868*^9, 3.620439277523871*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["Page Rank Algorithm", "Section", CellChangeTimes->{{3.652664008422885*^9, 3.652664013148789*^9}, { 3.652664059819646*^9, 3.65266406842835*^9}}], Cell[CellGroupData[{ Cell["\<\ We use the Perron - Frobenius Theorem to give a rigorous mathematical \ justification for the Page Rank Algorithm. \ \>", "Subsection", CellChangeTimes->{{3.652664073566296*^9, 3.652664174024207*^9}}], Cell["\<\ The PageRank algorithm provides the basis for Google' s web search tools. As \ we described in the lecture, PageRank is a recursive algorithm, and it works \ by counting the number and quality of links to a page to determine a rough \ estimate of how important the website is. The underlying assumption is that \ more important websites are likely to receive more links from other websites \ and therefore, the importance of any website can be judged by looking at the \ number and quality of the pages that link to it. Components of the PageRank \ vector serve as \"importance\" weights for web pages, independent of their \ textual content, solely based on the hyperlink structure of the web. \ \>", "Subsubsection", CellChangeTimes->{{3.652666436897311*^9, 3.652666445110886*^9}}, TextJustification->1., FontColor->GrayLevel[0]] }, Open ]], Cell[CellGroupData[{ Cell[TextData[{ "\nThe Page Rank Algorithm was discussed in class last week. More details on \ the theoretical aspects can be found at the ", ButtonBox["following link", BaseStyle->"Hyperlink", ButtonData->{ URL["http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/index.html"], None}, ButtonNote-> "http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/index.html"], ". \n", ButtonBox["http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/", BaseStyle->"Hyperlink", ButtonData->{ URL["http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/index.html"], None}, ButtonNote-> "http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/index.html"], "\nLecture #3 discusses Page Rank from several view points." }], "Subsection", CellChangeTimes->{{3.6972564577906847`*^9, 3.697256470148819*^9}, { 3.6972565128285627`*^9, 3.6972565390792217`*^9}, {3.6972566049148483`*^9, 3.6972566545557737`*^9}, {3.697257286045019*^9, 3.6972572860482187`*^9}, { 3.697257452519665*^9, 3.697257541415052*^9}, {3.697258049645111*^9, 3.697258117180893*^9}}], Cell[TextData[StyleBox["Given a graph, we first compute its transition \ matrix. If the transition matrix is positive and column stochastic, then the \ unique probabilistic eigenvector corresponding to the eigenvalue one is \ called the Page Rank vector of our graph. Its entries give the relative \ importance scores of the vertices of the graph.", FontColor->GrayLevel[0]]], "Subsubsection", CellChangeTimes->{{3.697257892265705*^9, 3.6972580265489817`*^9}}, FontSize->48] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Back to the Web Graph", "Section", CellChangeTimes->{{3.621127734367783*^9, 3.621127740702738*^9}}], Cell[TextData[StyleBox["When you code the algorithm, your first step should \ simply be to write a function which computes the transition matrix of a \ graph, as in the second homework assignment.", FontColor->GrayLevel[0]]], "Subsection", CellChangeTimes->{{3.697256149373416*^9, 3.697256201804558*^9}, { 3.69725628406348*^9, 3.697256332110938*^9}}], Cell["\<\ The Web Graph is not necessarily strongly connected, so its transition matrix \ need not be positive or column stochastic! The Web graph could have \ disconnected components or dangling nodes (nodes with no outgoing edges) \ which would correspond to 0 column vectors in the transition matrix. \ \>", "Subsection", CellChangeTimes->{{3.620402782060638*^9, 3.620402916919713*^9}, { 3.6204073086043262`*^9, 3.62040732544398*^9}, 3.621128546919327*^9, { 3.621134787982398*^9, 3.621134804535767*^9}, {3.6526988599122343`*^9, 3.652698860570876*^9}}], Cell["\<\ Some of the graphs in the project might also have these problems, especially \ the randomly generated ones. Then we cannot simply find the \ \[OpenCurlyDoubleQuote]unique\[CloseCurlyDoubleQuote] probabilistic \ eigenvector corresponding to the eigenvalue 1 and say that this is the Page \ Rank vector of our graph. We first need to adjust our algorithm slightly, to \ make it work also for graphs with dangling nodes and disconnected components\ \>", "Subsection", CellChangeTimes->{{3.621134814642476*^9, 3.621134899825863*^9}, { 3.6526989100930033`*^9, 3.652698972170815*^9}}, TextJustification->1., FontColor->GrayLevel[0]] }, Open ]], Cell[CellGroupData[{ Cell["Dangling nodes", "Section", CellChangeTimes->{{3.621128697234193*^9, 3.6211287010576973`*^9}}], Cell[CellGroupData[{ Cell["\<\ Consider the graph (tree) depicted below. Its transition matrix is given on \ the right, and we can see that it is not column stochastic or positive either!\ \>", "Subsection", CellDingbat->"\[SadSmiley]", CellChangeTimes->{{3.6526990299201183`*^9, 3.652699053917967*^9}, { 3.652699224819509*^9, 3.652699320684236*^9}, {3.697256438237062*^9, 3.697256440931898*^9}}], Cell[BoxData[{ RowBox[{ RowBox[{"H", "=", RowBox[{"Graph", "[", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"1", "\[Rule]", "2"}], ",", " ", RowBox[{"3", "\[Rule]", "2"}]}], "}"}], ",", " ", RowBox[{"GraphStyle", "\[Rule]", "\"\\""}], ",", " ", RowBox[{"VertexSize", "\[Rule]", "0.15"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"TransitionH", "=", RowBox[{"Transpose", "[", RowBox[{"AdjacencyMatrix", "[", "H", "]"}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"GraphicsRow", "[", RowBox[{"{", RowBox[{"H", ",", RowBox[{"MatrixForm", "[", "TransitionH", "]"}]}], "}"}], "]"}]}], "Input",\ CellChangeTimes->{{3.620402929009124*^9, 3.62040295147237*^9}, { 3.620402981597239*^9, 3.620403114508876*^9}}, FontSize->16, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ GraphicsBox[{{}, {InsetBox[ FormBox[ GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3}, {{{1, 2}, {3, 2}}, Null}, { GraphStyle -> "SmallNetwork", VertexSize -> {0.15}}]], Typeset`boxes, Typeset`boxes$s2d = GraphicsGroupBox[{{ Directive[ Hue[0.625, 0.5, 0.7], Thickness[Large], Opacity[1]], { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$1", Automatic, Center], DynamicLocation["VertexID$2", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$3", Automatic, Center], DynamicLocation["VertexID$2", Automatic, Center]}]}}, { Directive[ Hue[0.125, 0.7, 0.9], EdgeForm[]], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, { 0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{-0.0352941, 0.9294118}, {0.0352941, 0.9294118}, {0.0705882, 0.9294118}, { 0.0705882, 0.9647059}, {0.0705882, 1.0352941}, {0.0705882, 1.0705882}, {0.0352941, 1.0705882}, {-0.0352941, 1.0705882}, {-0.0705882, 1.0705882}, {-0.0705882, 1.0352941}, {-0.0705882, 0.9647059}, {-0.0705882, 0.9294118}, {-0.0352941, 0.9294118}}}], "DynamicName", BoxID -> "VertexID$1"], InsetBox[ FormBox["1", TraditionalForm], DynamicLocation["VertexID$1", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$1"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, { 0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 0.9647059, -0.0705882}, {1.0352941, -0.0705882}, { 1.0705882, -0.0705882}, {1.0705882, -0.0352941}, {1.0705882, 0.0352941}, {1.0705882, 0.0705882}, {1.0352941, 0.0705882}, { 0.9647059, 0.0705882}, {0.9294118, 0.0705882}, {0.9294118, 0.0352941}, {0.9294118, -0.0352941}, { 0.9294118, -0.0705882}, {0.9647059, -0.0705882}}}], "DynamicName", BoxID -> "VertexID$2"], InsetBox[ FormBox["2", TraditionalForm], DynamicLocation["VertexID$2", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$2"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, { 0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{0.9647059, 0.9294118}, {1.0352941, 0.9294118}, {1.0705882, 0.9294118}, { 1.0705882, 0.9647059}, {1.0705882, 1.0352941}, {1.0705882, 1.0705882}, {1.0352941, 1.0705882}, {0.9647059, 1.0705882}, { 0.9294118, 1.0705882}, {0.9294118, 1.0352941}, {0.9294118, 0.9647059}, {0.9294118, 0.9294118}, {0.9647059, 0.9294118}}}], "DynamicName", BoxID -> "VertexID$3"], InsetBox[ FormBox["3", TraditionalForm], DynamicLocation["VertexID$3", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$3"]}}], $CellContext`flag}, TagBox[ DynamicBox[GraphComputation`NetworkGraphicsBox[ 3, Typeset`graph, Typeset`boxes, $CellContext`flag], { CachedValue :> Typeset`boxes, SingleEvaluation -> True, SynchronousUpdating -> False, TrackedSymbols :> {$CellContext`flag}}, ImageSizeCache->{{5.760693309010094, 479.2393066909899}, {-480.2393066909899, -6.760693309010094}}], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False, UnsavedVariables:>{$CellContext`flag}]], DefaultBaseStyle->{ "NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FrameTicks->None, GridLinesStyle->Directive[ GrayLevel[0.5, 0.4]]], TraditionalForm], {192., -189.}, {Center, Center}, {360., 360.}], StyleBox[InsetBox[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", "0", "0"}, {"1", "0", "1"}, {"0", "0", "0"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[ SparseArray[ Automatic, {3, 3}, 0, { 1, {{0, 0, 2, 2}, {{1}, {3}}}, {1, 1}}]]]], {576., -189.}, { Center, Center}, {360., 360.}], FontSize->72, FontWeight->"Bold"]}, {}}, ContentSelectable->True, ImageSize->{Automatic, 525.6344926075269}, PlotRangePadding->{6, 5}]], "Input", CellChangeTimes->{3.6204031236544437`*^9}] }, Open ]], Cell[CellGroupData[{ Cell["\<\ Perron-Frobenius Theorem cannot be directly applied! Still, let us see if the \ Power Method converges to something useful. \ \>", "Subsection", CellDingbat->"\[SadSmiley]", CellChangeTimes->{{3.621129037918044*^9, 3.621129071593487*^9}, { 3.621134920286354*^9, 3.6211349208781023`*^9}, {3.621135032199753*^9, 3.621135033149583*^9}, {3.652699359273796*^9, 3.652699387433634*^9}, { 3.652699428075115*^9, 3.65269945172964*^9}, {3.652699703046954*^9, 3.652699715802581*^9}}, FontSize->18], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"u", "=", RowBox[{"{", RowBox[{ RowBox[{"1", "/", "3"}], ",", RowBox[{"1", "/", "3"}], ",", RowBox[{"1", "/", "3"}]}], "}"}]}], ";", " ", RowBox[{"MatrixForm", "[", "u", "]"}]}], "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"k", "=", "1"}], ",", " ", RowBox[{"k", "\[LessEqual]", "3"}], ",", " ", RowBox[{"k", "++"}], ",", " ", RowBox[{"Print", "[", RowBox[{"MatrixForm", "[", RowBox[{ RowBox[{"MatrixPower", "[", RowBox[{"TransitionH", ",", "k"}], "]"}], ".", "u"}], "]"}], "]"}]}], "]"}]}], "Input", CellChangeTimes->{{3.620403153519567*^9, 3.620403213254784*^9}, { 3.620403244040474*^9, 3.620403322682033*^9}}, FontSize->72, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", TagBox[GridBox[{ { FractionBox["1", "3"]}, { FractionBox["1", "3"]}, { FractionBox["1", "3"]} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.5599999999999999]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], Column], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]], "Output", CellChangeTimes->{3.621128620468309*^9}, FontSize->18, FontWeight->"Bold"], Cell[CellGroupData[{ Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", TagBox[GridBox[{ {"0"}, { FractionBox["2", "3"]}, {"0"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.5599999999999999]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], Column], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]], "Print", CellChangeTimes->{3.621128620471374*^9}, FontSize->48, FontWeight->"Bold"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", TagBox[GridBox[{ {"0"}, {"0"}, {"0"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.5599999999999999]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], Column], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[ SparseArray[Automatic, {3}, 0, {1, {{0, 0}, {}}, {}}]]]]], "Print", CellChangeTimes->{3.621128620473456*^9}, FontSize->48, FontWeight->"Bold"], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", TagBox[GridBox[{ {"0"}, {"0"}, {"0"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.5599999999999999]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], Column], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[ SparseArray[Automatic, {3}, 0, {1, {{0, 0}, {}}, {}}]]]]], "Print", CellChangeTimes->{3.621128620476905*^9}, FontSize->48, FontWeight->"Bold"] }, Open ]] }, Open ]], Cell[TextData[{ "We notice that the sequence of vectors u, Au, ..., ", Cell[BoxData[ FormBox[ RowBox[{ SuperscriptBox["A", "k"], "u"}], TraditionalForm]]], " converges to the 0-vector. Therefore, in this case, the rank of every page \ is 0. This is counterintuitive, as page 2 has two incoming links, so it must \ have some importance! " }], "Text", CellChangeTimes->{{3.6211288506111193`*^9, 3.621128901148509*^9}, { 3.621128973500038*^9, 3.621129005356771*^9}, 3.621129121030654*^9, { 3.621135007839069*^9, 3.621135013190206*^9}, {3.69725818042826*^9, 3.697258182009272*^9}}, TextJustification->1., FontSize->16] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["A solution to the Dangling Nodes Problem", "Section", CellDingbat->"\[HappySmiley]", CellChangeTimes->{{3.62112913635992*^9, 3.6211291478629427`*^9}}, FontSize->24], Cell[TextData[{ "Change the transition matrix of the graph so that it becomes ", StyleBox["column stochastic", FontWeight->"Bold"], ". More specifically, change any 0-column in the transition matrix with a \ column where all elements are equal to 1/n. " }], "Text", CellChangeTimes->{{3.6211292106247673`*^9, 3.621129445633459*^9}, { 3.6211295879726152`*^9, 3.621129596796549*^9}}, TextJustification->1., FontSize->16], Cell[TextData[StyleBox["This models the behavior of a random surfer that \ after viewing a web page with no outgoing edges, will simply choose another \ page from the Web with equal probability 1/n and go there.", FontSize->48]], "Text", CellChangeTimes->{ 3.6211294530031*^9, {3.621129555436688*^9, 3.62112956608328*^9}}, TextJustification->1., FontSize->16], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"For", "[", RowBox[{ RowBox[{"i", "=", "1"}], ",", RowBox[{"i", "\[LessEqual]", "3"}], ",", RowBox[{"i", "++"}], ",", " ", RowBox[{ RowBox[{"TransitionH", "[", RowBox[{"[", RowBox[{"i", ",", "2"}], "]"}], "]"}], "=", RowBox[{"1", "/", "3"}]}]}], "]"}], ";"}], "\[IndentingNewLine]", RowBox[{"MatrixForm", "[", "TransitionH", "]"}]}], "Input", CellChangeTimes->{{3.6211307502723093`*^9, 3.621130779944311*^9}, 3.621130810888795*^9, {3.621132001604165*^9, 3.621132033172035*^9}, { 3.621132072399886*^9, 3.621132127464967*^9}}, FontSize->72, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0", FractionBox["1", "3"], "0"}, {"1", FractionBox["1", "3"], "1"}, {"0", FractionBox["1", "3"], "0"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[ SparseArray[ Automatic, {3, 3}, 0, { 1, {{0, 1, 4, 5}, {{2}, {1}, {3}, {2}, {2}}}, { Rational[1, 3], 1, 1, Rational[1, 3], Rational[1, 3]}}]]]]], "Output", CellChangeTimes->{3.6211321296052103`*^9}, FontSize->72, FontWeight->"Bold"] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{"u", "=", RowBox[{"{", RowBox[{ RowBox[{"1", "/", "3"}], ",", RowBox[{"1", "/", "3"}], ",", RowBox[{"1", "/", "3"}]}], "}"}]}], "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"k", "=", "1"}], ",", " ", RowBox[{"k", "\[LessEqual]", "40"}], ",", " ", RowBox[{"k", "++"}], ",", " ", RowBox[{"Print", "[", RowBox[{"N", "[", RowBox[{ RowBox[{"MatrixPower", "[", RowBox[{"TransitionH", ",", "k"}], "]"}], ".", "u"}], "]"}], "]"}]}], "]"}]}], "Input", CellChangeTimes->{{3.620403153519567*^9, 3.620403213254784*^9}, { 3.620403244040474*^9, 3.620403322682033*^9}, {3.621132194874023*^9, 3.621132285032642*^9}, {3.621132359415555*^9, 3.621132359842704*^9}}, FontSize->48, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"{", RowBox[{ FractionBox["1", "3"], ",", FractionBox["1", "3"], ",", FractionBox["1", "3"]}], "}"}]], "Output", CellChangeTimes->{{3.621132181490285*^9, 3.6211322871351213`*^9}, 3.621132362424485*^9}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"{", RowBox[{ "0.1111111111111111`", ",", "0.7777777777777778`", ",", "0.1111111111111111`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362427546*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.25925925925925924`", ",", "0.48148148148148145`", ",", "0.25925925925925924`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362429064*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.16049382716049382`", ",", "0.6790123456790124`", ",", "0.16049382716049382`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323624318027`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.22633744855967078`", ",", "0.5473251028806584`", ",", "0.22633744855967078`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362434558*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.18244170096021947`", ",", "0.635116598079561`", ",", "0.18244170096021947`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362437274*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.211705532693187`", ",", "0.5765889346136259`", ",", "0.211705532693187`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362439975*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19219631153787534`", ",", "0.6156073769242494`", ",", "0.19219631153787534`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362442691*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20520245897474979`", ",", "0.5895950820505005`", ",", "0.20520245897474979`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362445403*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19653169401683349`", ",", "0.6069366119663331`", ",", "0.19653169401683349`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362448121*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.2023122039887777`", ",", "0.5953755920224446`", ",", "0.2023122039887777`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323624508333`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.1984585306741482`", ",", "0.6030829386517036`", ",", "0.1984585306741482`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362453562*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.2010276462172345`", ",", "0.597944707565531`", ",", "0.2010276462172345`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362456253*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19931490252184364`", ",", "0.6013701949563127`", ",", "0.19931490252184364`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.62113236245949*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20045673165210423`", ",", "0.5990865366957915`", ",", "0.20045673165210423`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362462722*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19969551223193052`", ",", "0.600608975536139`", ",", "0.19969551223193052`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323624660187`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20020299184537965`", ",", "0.5995940163092407`", ",", "0.20020299184537965`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323624687243`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19986467210308023`", ",", "0.6002706557938395`", ",", "0.19986467210308023`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362471382*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.2000902185979465`", ",", "0.599819562804107`", ",", "0.2000902185979465`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362474064*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19993985426803565`", ",", "0.6001202914639286`", ",", "0.19993985426803565`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362476774*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20004009715464288`", ",", "0.5999198056907142`", ",", "0.20004009715464288`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362479455*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.1999732685635714`", ",", "0.6000534628728572`", ",", "0.1999732685635714`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362482122*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20001782095761905`", ",", "0.5999643580847619`", ",", "0.20001782095761905`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323624848146`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19998811936158728`", ",", "0.6000237612768254`", ",", "0.19998811936158728`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362487494*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20000792042560847`", ",", "0.599984159148783`", ",", "0.20000792042560847`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.62113236249021*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.199994719716261`", ",", "0.6000105605674779`", ",", "0.199994719716261`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362492887*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20000352018915932`", ",", "0.5999929596216813`", ",", "0.20000352018915932`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362495552*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19999765320722712`", ",", "0.6000046935855458`", ",", "0.19999765320722712`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323624982357`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20000156452851525`", ",", "0.5999968709429695`", ",", "0.20000156452851525`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.62113236250095*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19999895698098982`", ",", "0.6000020860380203`", ",", "0.19999895698098982`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362503665*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20000069534600678`", ",", "0.5999986093079864`", ",", "0.20000069534600678`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362506351*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19999953643599547`", ",", "0.600000927128009`", ",", "0.19999953643599547`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323625090303`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.2000003090426697`", ",", "0.5999993819146606`", ",", "0.2000003090426697`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362511765*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19999979397155357`", ",", "0.600000412056893`", ",", "0.19999979397155357`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362514453*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20000013735229766`", ",", "0.5999997252954048`", ",", "0.20000013735229766`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323625171432`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19999990843180154`", ",", "0.6000001831363967`", ",", "0.19999990843180154`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362519825*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20000006104546558`", ",", "0.5999998779090687`", ",", "0.20000006104546558`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362522533*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19999995930302295`", ",", "0.6000000813939542`", ",", "0.19999995930302295`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323625251913`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20000002713131806`", ",", "0.5999999457373639`", ",", "0.20000002713131806`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323625279007`*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19999998191245463`", ",", "0.6000000361750908`", ",", "0.19999998191245463`"}], "}"}]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.621132362530595*^9}], Cell[BoxData[ StyleBox[ RowBox[{"{", RowBox[{ "0.20000001205836357`", ",", "0.5999999758832728`", ",", "0.20000001205836357`"}], "}"}], FontSize->168]], "Print", CellChangeTimes->{{3.621132181493249*^9, 3.6211322871394987`*^9}, 3.6211323625332737`*^9}] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Disconnected components", "Section", CellChangeTimes->{{3.6211287281485033`*^9, 3.62112873385161*^9}}, FontSize->120], Cell[TextData[{ StyleBox["Solution:", FontSize->48, FontColor->GrayLevel[0]], StyleBox[" Let T be the transition matrix of the Web graph. T is an nxn \ matrix, where n is huge. Fix a positive constant p between 0 and 1, called \ the damping factor (a typical value for p is 0.15). Define the ", FontSize->48], StyleBox["Page Rank matrix (also known as the Google matrix)", FontSize->48, FontColor->RGBColor[0.5, 0, 0.5]], StyleBox[" of the graph to be", FontSize->48], " \n", StyleBox["M=(1-p)T+p", FontSize->72, Background->RGBColor[1, 1, 0.85]], Cell[BoxData[ RowBox[{"(", "\[NoBreak]", GridBox[{ { FractionBox["1", "n"], FractionBox["1", "n"], "..", FractionBox["1", "n"]}, {"..", "..", "..", ".."}, { FractionBox["1", "n"], FractionBox["1", "n"], "..", FractionBox["1", "n"]} }], "\[NoBreak]", ")"}]], FontSize->72, FontWeight->"Bold", Background->RGBColor[1, 1, 0.85]] }], "Subsection", CellDingbat->"\[HappySmiley]", CellChangeTimes->{{3.620402200933195*^9, 3.620402226083322*^9}, { 3.620402281056072*^9, 3.6204023746260157`*^9}, 3.620403352211932*^9, { 3.6204034188682947`*^9, 3.620403538339012*^9}}], Cell[TextData[{ StyleBox["Theorem:", FontColor->GrayLevel[0]], " If T is a column stochastic matrix, then M is a positive and column \ stochastic matrix." }], "Subsection", CellChangeTimes->{{3.620403601985428*^9, 3.6204036498197403`*^9}, 3.620403702943022*^9, {3.620405028664054*^9, 3.620405034429226*^9}}], Cell[TextData[{ StyleBox["The matrix M models the behaviour of the random surfer as follows:", FontColor->GrayLevel[0]], " most of the time, a surfer will follow links from the current page he/she \ is viewing. From a page i, the surfer will follow the outgoing links and move \ on to one of the neighbors of page i. A smaller, but positive percentage of \ the time, the surfer will dump the current page and choose arbitrarily a \ different page from the web and \[OpenCurlyDoubleQuote]teleport\ \[CloseCurlyDoubleQuote] there. The damping factor p reflects the probability \ that the surfer quits the current page and goes to a new one. Since he/she \ can teleport to any web page, each page has equal probability ", Cell[BoxData[ FractionBox["1", "n"]], FontWeight->"Bold"], " to be chosen. So the Internet graph becomes strongly connected. " }], "Subsection", CellChangeTimes->{{3.620403714701315*^9, 3.620403719661592*^9}, { 3.620403764275714*^9, 3.6204039108040447`*^9}, 3.620404010477684*^9, { 3.621132626743765*^9, 3.621132644510645*^9}}] }, Open ]], Cell[CellGroupData[{ Cell["An example of a graph with disconnected components ", "Section", CellChangeTimes->{{3.621461218742148*^9, 3.6214612899623413`*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"G2", "=", RowBox[{"Graph", "[", RowBox[{ RowBox[{"{", RowBox[{ "1", ",", "2", ",", "3", ",", "4", ",", "5", ",", "6", ",", "7"}], "}"}], ",", " ", RowBox[{"{", RowBox[{ RowBox[{"1", "\[Rule]", "2"}], ",", " ", RowBox[{"2", "\[Rule]", "1"}], ",", " ", RowBox[{"3", "\[Rule]", "4"}], ",", " ", RowBox[{"4", "\[Rule]", "3"}], ",", " ", RowBox[{"4", "\[Rule]", "5"}], ",", " ", RowBox[{"5", "\[Rule]", "4"}], ",", " ", RowBox[{"5", "\[Rule]", "3"}], ",", " ", RowBox[{"3", "\[Rule]", "5"}], ",", " ", RowBox[{"3", "\[Rule]", "6"}], ",", " ", RowBox[{"6", "\[Rule]", "4"}], ",", " ", RowBox[{"7", "\[Rule]", "5"}], ",", RowBox[{"7", "\[Rule]", "4"}], ",", RowBox[{"3", "\[Rule]", "7"}]}], "}"}], ",", " ", RowBox[{"GraphStyle", "\[Rule]", "\"\\""}]}], "]"}]}]], "Input", CellChangeTimes->{{3.621132896259478*^9, 3.621132970746809*^9}, { 3.621133541731759*^9, 3.621133554379478*^9}, {3.6211337098680468`*^9, 3.621133725674616*^9}}, FontSize->36, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ GraphicsBox[ NamespaceBox["NetworkGraphics", DynamicModuleBox[{Typeset`graph = HoldComplete[ Graph[{1, 2, 3, 4, 5, 6, 7}, {{{1, 2}, {2, 1}, {3, 4}, {4, 3}, {4, 5}, {5, 4}, {5, 3}, {3, 5}, { 3, 6}, {6, 4}, {7, 5}, {7, 4}, {3, 7}}, Null}, { GraphStyle -> "SmallNetwork"}]], Typeset`boxes, Typeset`boxes$s2d = GraphicsGroupBox[{{ Directive[ Hue[0.625, 0.5, 0.7], Thickness[Large], Opacity[1]], { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$1", Automatic, Center], { 0.7358482383136193, -1.6941102163421569`}, DynamicLocation["VertexID$2", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$2", Automatic, Center], { 0.7358482383136208, -1.365228721978834}, DynamicLocation["VertexID$1", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$3", Automatic, Center], { 1.3993272120341633`, -0.6468636518809233}, DynamicLocation["VertexID$4", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$3", Automatic, Center], { 1.8609028788474156`, -0.5184014718084906}, DynamicLocation["VertexID$5", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$3", Automatic, Center], DynamicLocation["VertexID$6", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$3", Automatic, Center], DynamicLocation["VertexID$7", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$4", Automatic, Center], { 1.1565972130116697`, -0.6467823373611671}, DynamicLocation["VertexID$3", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$4", Automatic, Center], { 1.7394142565098447`, -0.887384312647787}, DynamicLocation["VertexID$5", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$5", Automatic, Center], { 1.6043182536142784`, -0.8173710172457336}, DynamicLocation["VertexID$3", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[ BezierCurveBox[{ DynamicLocation["VertexID$5", Automatic, Center], { 1.725559630299196, -1.1864351726054618`}, DynamicLocation["VertexID$4", Automatic, Center]}]]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$6", Automatic, Center], DynamicLocation["VertexID$4", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$7", Automatic, Center], DynamicLocation["VertexID$4", Automatic, Center]}]}, { Arrowheads[{{0.04, 1, { GraphicsBox[ FilledCurveBox[{{{0, 2, 0}, {0, 1, 0}, {0, 1, 0}}}, {{{-0.6666528591843921, -0.3333333333333333}, \ {-0.533327810340424, 6.903741136987662*^-6}, {-0.6666528591843921, 0.3333333333333333}, {0., 6.903741136987662*^-6}}}]], 0.533327810340424}}}], ArrowBox[{ DynamicLocation["VertexID$7", Automatic, Center], DynamicLocation["VertexID$5", Automatic, Center]}]}}, { Directive[ Hue[0.125, 0.7, 0.9], EdgeForm[]], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 1.2083040264002582`, -1.5847578929866897`}, { 1.263392450226983, -1.5847578929866897`}, { 1.2909366621403453`, -1.5847578929866897`}, { 1.2909366621403453`, -1.5572136810733275`}, { 1.2909366621403453`, -1.5021252572466026`}, { 1.2909366621403453`, -1.4745810453332404`}, { 1.263392450226983, -1.4745810453332404`}, { 1.2083040264002582`, -1.4745810453332404`}, { 1.180759814486896, -1.4745810453332404`}, { 1.180759814486896, -1.5021252572466026`}, { 1.180759814486896, -1.5572136810733275`}, { 1.180759814486896, -1.5847578929866897`}, { 1.2083040264002582`, -1.5847578929866897`}}}], "DynamicName", BoxID -> "VertexID$1"], InsetBox[ FormBox["1", TraditionalForm], DynamicLocation["VertexID$1", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$1"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 0.2083040264002583, -1.5847578929866897`}, { 0.26339245022698304`, -1.5847578929866897`}, { 0.2909366621403454, -1.5847578929866897`}, { 0.2909366621403454, -1.5572136810733275`}, { 0.2909366621403454, -1.5021252572466026`}, { 0.2909366621403454, -1.4745810453332404`}, { 0.26339245022698304`, -1.4745810453332404`}, { 0.2083040264002583, -1.4745810453332404`}, { 0.18075981448689593`, -1.4745810453332404`}, { 0.18075981448689593`, -1.5021252572466026`}, { 0.18075981448689593`, -1.5572136810733275`}, { 0.18075981448689593`, -1.5847578929866897`}, { 0.2083040264002583, -1.5847578929866897`}}}], "DynamicName", BoxID -> "VertexID$2"], InsetBox[ FormBox["2", TraditionalForm], DynamicLocation["VertexID$2", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$2"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 1.2505416234358788`, -0.33288792034810566`}, { 1.3056300472626037`, -0.33288792034810566`}, { 1.3331742591759659`, -0.33288792034810566`}, { 1.3331742591759659`, -0.3053437084347433}, { 1.3331742591759659`, -0.25025528460801855`}, { 1.3331742591759659`, -0.22271107269465618`}, { 1.3056300472626037`, -0.22271107269465618`}, { 1.2505416234358788`, -0.22271107269465618`}, { 1.2229974115225166`, -0.22271107269465618`}, { 1.2229974115225166`, -0.25025528460801855`}, { 1.2229974115225166`, -0.3053437084347433}, { 1.2229974115225166`, -0.33288792034810566`}, { 1.2505416234358788`, -0.33288792034810566`}}}], "DynamicName", BoxID -> "VertexID$3"], InsetBox[ FormBox["3", TraditionalForm], DynamicLocation["VertexID$3", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$3"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 1.2502943777832305`, -1.0709349165472846`}, { 1.3053828016099553`, -1.0709349165472846`}, { 1.3329270135233175`, -1.0709349165472846`}, { 1.3329270135233175`, -1.0433907046339224`}, { 1.3329270135233175`, -0.9883022808071976}, { 1.3329270135233175`, -0.9607580688938352}, { 1.3053828016099553`, -0.9607580688938352}, { 1.2502943777832305`, -0.9607580688938352}, { 1.2227501658698683`, -0.9607580688938352}, { 1.2227501658698683`, -0.9883022808071976}, { 1.2227501658698683`, -1.0433907046339224`}, { 1.2227501658698683`, -1.0709349165472846`}, { 1.2502943777832305`, -1.0709349165472846`}}}], "DynamicName", BoxID -> "VertexID$4"], InsetBox[ FormBox["4", TraditionalForm], DynamicLocation["VertexID$4", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$4"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 2.159591085199087, -1.1130614163594483`}, { 2.2146795090258116`, -1.1130614163594483`}, { 2.242223720939174, -1.1130614163594483`}, { 2.242223720939174, -1.0855172044460861`}, { 2.242223720939174, -1.0304287806193613`}, { 2.242223720939174, -1.002884568705999}, { 2.2146795090258116`, -1.002884568705999}, { 2.159591085199087, -1.002884568705999}, { 2.1320468732857245`, -1.002884568705999}, { 2.1320468732857245`, -1.0304287806193613`}, { 2.1320468732857245`, -1.0855172044460861`}, { 2.1320468732857245`, -1.1130614163594483`}, { 2.159591085199087, -1.1130614163594483`}}}], "DynamicName", BoxID -> "VertexID$5"], InsetBox[ FormBox["5", TraditionalForm], DynamicLocation["VertexID$5", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$5"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 0.2083040264002583, -0.7019736792959174}, { 0.26339245022698304`, -0.7019736792959174}, { 0.2909366621403454, -0.7019736792959174}, { 0.2909366621403454, -0.6744294673825549}, { 0.2909366621403454, -0.6193410435558303}, { 0.2909366621403454, -0.5917968316424679}, { 0.26339245022698304`, -0.5917968316424679}, { 0.2083040264002583, -0.5917968316424679}, { 0.18075981448689593`, -0.5917968316424679}, { 0.18075981448689593`, -0.6193410435558303}, { 0.18075981448689593`, -0.6744294673825549}, { 0.18075981448689593`, -0.7019736792959174}, { 0.2083040264002583, -0.7019736792959174}}}], "DynamicName", BoxID -> "VertexID$6"], InsetBox[ FormBox["6", TraditionalForm], DynamicLocation["VertexID$6", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$6"], TagBox[{ TagBox[ FilledCurveBox[{{{0, 2, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}, {0, 1, 1}, {1, 2, 2}}}, {{{ 2.1595091703756193`, -0.2909366621403455}, { 2.2145975942023437`, -0.2909366621403455}, { 2.2421418061157063`, -0.2909366621403455}, { 2.2421418061157063`, -0.26339245022698315`}, { 2.2421418061157063`, -0.2083040264002584}, { 2.2421418061157063`, -0.18075981448689604`}, { 2.2145975942023437`, -0.18075981448689604`}, { 2.1595091703756193`, -0.18075981448689604`}, { 2.1319649584622566`, -0.18075981448689604`}, { 2.1319649584622566`, -0.2083040264002584}, { 2.1319649584622566`, -0.26339245022698315`}, { 2.1319649584622566`, -0.2909366621403455}, { 2.1595091703756193`, -0.2909366621403455}}}], "DynamicName", BoxID -> "VertexID$7"], InsetBox[ FormBox["7", TraditionalForm], DynamicLocation["VertexID$7", None, Center], BaseStyle -> "Graphics"]}, "DynamicName", BoxID -> "VertexLabelID$7"]}}], $CellContext`flag}, TagBox[ DynamicBox[GraphComputation`NetworkGraphicsBox[ 3, Typeset`graph, Typeset`boxes, $CellContext`flag], { CachedValue :> Typeset`boxes, SingleEvaluation -> True, SynchronousUpdating -> False, TrackedSymbols :> {$CellContext`flag}}, ImageSizeCache->{{9.738695154015772, 695.2613048459842}, {-269.2613048459842, 236.36820082949754`}}], MouseAppearanceTag["NetworkGraphics"]], AllowKernelInitialization->False, UnsavedVariables:>{$CellContext`flag}]], DefaultBaseStyle->{ "NetworkGraphics", FrontEnd`GraphicsHighlightColor -> Hue[0.8, 1., 0.6]}, FrameTicks->None, GridLinesStyle->Directive[ GrayLevel[0.5, 0.4]], ImageSize->{706.046875, Automatic}]], "Output", CellChangeTimes->{{3.6211329496244497`*^9, 3.621132973962286*^9}, 3.621133556860367*^9, 3.621133728517798*^9}, FontSize->72] }, Open ]], Cell["\<\ Find the transition matrix first and compute its eigenvalues:\ \>", "Text", CellChangeTimes->{{3.621461297853692*^9, 3.621461312017555*^9}}, FontSize->16], Cell[BoxData[{ RowBox[{ RowBox[{"Lout", "=", RowBox[{"VertexOutDegree", "[", "G2", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"TA", "=", RowBox[{"Transpose", "[", RowBox[{"AdjacencyMatrix", "[", "G2", "]"}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"f", "[", RowBox[{"i_", ",", "j_"}], "]"}], ":=", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"Lout", "[", RowBox[{"[", "j", "]"}], "]"}], "!=", "0"}], ",", RowBox[{ RowBox[{ RowBox[{"TA", "[", RowBox[{"[", "i", "]"}], "]"}], "[", RowBox[{"[", "j", "]"}], "]"}], "/", RowBox[{"Lout", "[", RowBox[{"[", "j", "]"}], "]"}]}], ",", "0"}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"T", "=", " ", RowBox[{"Table", "[", RowBox[{ RowBox[{"f", "[", RowBox[{"i", ",", "j"}], "]"}], ",", RowBox[{"{", RowBox[{"i", ",", RowBox[{"Length", "[", "TA", "]"}]}], "}"}], ",", RowBox[{"{", RowBox[{"j", ",", RowBox[{"Length", "[", "TA", "]"}]}], "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"MatrixForm", "[", "T", "]"}]}], "Input", CellChangeTimes->{{3.620394711204328*^9, 3.6203947729384403`*^9}, { 3.620394808733617*^9, 3.620394835626976*^9}, {3.620394873195034*^9, 3.620394873860927*^9}, {3.6203962964348907`*^9, 3.620396303986541*^9}, { 3.620396368743454*^9, 3.62039637111765*^9}, {3.620396511251704*^9, 3.6203965257801123`*^9}, {3.6203969486872597`*^9, 3.6203969716098337`*^9}, { 3.620397089051959*^9, 3.620397173132559*^9}, {3.6203988541011953`*^9, 3.620398862275489*^9}, {3.621133100457562*^9, 3.6211332304124928`*^9}}, FontSize->16, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ { StyleBox["0", FontColor->RGBColor[0, 0, 1]], StyleBox["1", FontColor->RGBColor[0, 0, 1]], "0", "0", "0", "0", "0"}, { StyleBox["1", FontColor->RGBColor[0, 0, 1]], StyleBox["0", FontColor->RGBColor[0, 0, 1]], "0", "0", "0", "0", "0"}, {"0", "0", StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox[ FractionBox["1", "2"], FontColor->RGBColor[1, 0, 0]], StyleBox[ FractionBox["1", "2"], FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]]}, {"0", "0", StyleBox[ FractionBox["1", "4"], FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox[ FractionBox["1", "2"], FontColor->RGBColor[1, 0, 0]], StyleBox["1", FontColor->RGBColor[1, 0, 0]], StyleBox[ FractionBox["1", "2"], FontColor->RGBColor[1, 0, 0]]}, {"0", "0", StyleBox[ FractionBox["1", "4"], FontColor->RGBColor[1, 0, 0]], StyleBox[ FractionBox["1", "2"], FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox[ FractionBox["1", "2"], FontColor->RGBColor[1, 0, 0]]}, {"0", "0", StyleBox[ FractionBox["1", "4"], FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]]}, {"0", "0", StyleBox[ FractionBox["1", "4"], FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]], StyleBox["0", FontColor->RGBColor[1, 0, 0]]} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]]], "Input", CellChangeTimes->{3.621459323808022*^9}, FontSize->72], Cell[BoxData[ RowBox[{"Eigenvalues", "[", "T", "]"}]], "Input", CellChangeTimes->{{3.621133288453536*^9, 3.621133324837489*^9}}, FontSize->18, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"-", "1"}], ",", StyleBox["1", FontColor->RGBColor[0, 0, 1]], ",", StyleBox["1", FontColor->RGBColor[0, 0, 1]], ",", RowBox[{"-", FractionBox["1", "2"]}], ",", RowBox[{ FractionBox["1", "4"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "+", RowBox[{"\[ImaginaryI]", " ", SqrtBox["3"]}]}], ")"}]}], ",", RowBox[{ FractionBox["1", "4"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "-", RowBox[{"\[ImaginaryI]", " ", SqrtBox["3"]}]}], ")"}]}], ",", "0"}], "}"}]], "Input", CellChangeTimes->{3.621460999070333*^9}, FontSize->72], Cell[BoxData[ RowBox[{"Eigensystem", "[", "T", "]"}]], "Input", CellChangeTimes->{{3.621133344946342*^9, 3.6211333495454073`*^9}}, FontSize->18, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"-", "1"}], ",", StyleBox["1", FontColor->RGBColor[0, 0, 1]], ",", StyleBox["1", FontColor->RGBColor[0, 0, 1]], ",", RowBox[{"-", FractionBox["1", "2"]}], ",", RowBox[{ FractionBox["1", "4"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "+", RowBox[{"\[ImaginaryI]", " ", SqrtBox["3"]}]}], ")"}]}], ",", RowBox[{ FractionBox["1", "4"], " ", RowBox[{"(", RowBox[{ RowBox[{"-", "1"}], "-", RowBox[{"\[ImaginaryI]", " ", SqrtBox["3"]}]}], ")"}]}], ",", "0"}], "}"}], ",", RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"-", "1"}], ",", "1", ",", "0", ",", "0", ",", "0", ",", "0", ",", "0"}], "}"}], ",", RowBox[{"{", StyleBox[ RowBox[{"0", ",", "0", ",", "4", ",", FractionBox["13", "3"], ",", FractionBox["11", "3"], ",", "1", ",", "1"}], FontColor->RGBColor[0, 0, 1]], "}"}], ",", RowBox[{"{", StyleBox[ RowBox[{ "1", ",", "1", ",", "0", ",", "0", ",", "0", ",", "0", ",", "0"}], FontColor->RGBColor[0, 0, 1]], "}"}], ",", RowBox[{"{", RowBox[{"0", ",", "0", ",", "0", ",", RowBox[{"-", "1"}], ",", "1", ",", "0", ",", "0"}], "}"}], ",", RowBox[{"{", RowBox[{"0", ",", "0", ",", RowBox[{ RowBox[{"-", "1"}], "+", RowBox[{"\[ImaginaryI]", " ", SqrtBox["3"]}]}], ",", RowBox[{ RowBox[{"-", "\[ImaginaryI]"}], " ", SqrtBox["3"]}], ",", RowBox[{"-", "1"}], ",", "1", ",", "1"}], "}"}], ",", RowBox[{"{", RowBox[{"0", ",", "0", ",", RowBox[{ RowBox[{"-", "1"}], "-", RowBox[{"\[ImaginaryI]", " ", SqrtBox["3"]}]}], ",", RowBox[{"\[ImaginaryI]", " ", SqrtBox["3"]}], ",", RowBox[{"-", "1"}], ",", "1", ",", "1"}], "}"}], ",", RowBox[{"{", RowBox[{"0", ",", "0", ",", "0", ",", RowBox[{"-", "1"}], ",", "1", ",", RowBox[{"-", "1"}], ",", "1"}], "}"}]}], "}"}]}], "}"}]], "Input", CellChangeTimes->{3.621461029832028*^9}, FontSize->48], Cell[CellGroupData[{ Cell[TextData[{ "The eigenspace corresponding to the eigenvalue 1 is now two-dimensional! So \ there are many probabilistic eigenvectors corresponding to the eigenvalue 1. \ So for different choices of initial probabilistic vectors ", Cell[BoxData[ FormBox[ SubscriptBox["u", "2"], TraditionalForm]]], " and ", Cell[BoxData[ FormBox[ SubscriptBox["u", "3"], TraditionalForm]]], ", the sequences ", Cell[BoxData[ FormBox[ SubscriptBox["u", "2"], TraditionalForm]]], ", T", Cell[BoxData[ FormBox[ SubscriptBox["u", "2"], TraditionalForm]]], ", ... T^k", Cell[BoxData[ FormBox[ SubscriptBox["u", "2"], TraditionalForm]]], ".... and ", Cell[BoxData[ FormBox[ SubscriptBox["u", "3"], TraditionalForm]]], ", T", Cell[BoxData[ FormBox[ SubscriptBox["u", "3"], TraditionalForm]]], ", ... T^k", Cell[BoxData[ FormBox[ SubscriptBox["u", "3"], TraditionalForm]]], " can converge to different limits, as one can see below:" }], "Subsection", CellChangeTimes->{{3.621134396757024*^9, 3.621134416621093*^9}, { 3.621134720591331*^9, 3.6211347466226177`*^9}, {3.621460725005662*^9, 3.6214609100172777`*^9}}], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"n", "=", RowBox[{"Length", "[", "T", "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"u2", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"1", "/", "n"}], ",", " ", RowBox[{"{", "n", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"k", "=", "1"}], ",", " ", RowBox[{"k", "\[LessEqual]", "10"}], ",", " ", RowBox[{"k", "++"}], ",", " ", RowBox[{"Print", "[", RowBox[{"N", "[", RowBox[{ RowBox[{"MatrixPower", "[", RowBox[{"T", ",", "k"}], "]"}], ".", "u2"}], "]"}], "]"}]}], "]"}]}], "Input", CellChangeTimes->{{3.620403153519567*^9, 3.620403213254784*^9}, { 3.620403244040474*^9, 3.620403322682033*^9}, {3.621132194874023*^9, 3.621132285032642*^9}, {3.621132359415555*^9, 3.621132359842704*^9}, { 3.621133429016123*^9, 3.6211334724185743`*^9}, {3.62113363201539*^9, 3.621133656516343*^9}, {3.621133783794557*^9, 3.6211337839870033`*^9}}, FontSize->72, Background->RGBColor[0.87, 0.94, 1]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.32142857142857145`", ",", "0.17857142857142858`", ",", "0.03571428571428571`", ",", "0.03571428571428571`"}], "}"}]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.6211337863390713`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.25`", ",", "0.17857142857142858`", ",", "0.21428571428571427`", ",", "0.03571428571428571`", ",", "0.03571428571428571`"}], "}"}]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.621133786341139*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.19642857142857142`", ",", "0.22321428571428573`", ",", "0.16964285714285715`", ",", "0.0625`", ",", "0.0625`"}], "}"}]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.621133786343603*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.19642857142857142`", ",", "0.22767857142857142`", ",", "0.19196428571428573`", ",", "0.049107142857142856`", ",", "0.049107142857142856`"}], "}"}]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.621133786344644*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.20982142857142858`", ",", "0.21875`", ",", "0.1875`", ",", "0.049107142857142856`", ",", "0.049107142857142856`"}], "}"}]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.621133786345682*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.203125`", ",", "0.21986607142857142`", ",", "0.18638392857142858`", ",", "0.052455357142857144`", ",", "0.052455357142857144`"}], "}"}]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.621133786346681*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.203125`", ",", "0.22265625`", ",", "0.18694196428571427`", ",", "0.05078125`", ",", "0.05078125`"}], "}"}]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.621133786347652*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.20479910714285715`", ",", "0.22042410714285715`", ",", "0.1875`", ",", "0.05078125`", ",", "0.05078125`"}], "}"}]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.621133786348626*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.20396205357142858`", ",", "0.22112165178571427`", ",", "0.18680245535714285`", ",", "0.05119977678571429`", ",", "0.05119977678571429`"}], "}"}]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.621133786349585*^9}}], Cell[BoxData[ StyleBox[ RowBox[{"{", RowBox[{ "0.14285714285714285`", ",", "0.14285714285714285`", ",", "0.20396205357142858`", ",", "0.22119140625`", ",", "0.18715122767857142`", ",", "0.050990513392857144`", ",", "0.050990513392857144`"}], "}"}], FontSize->48]], "Print", CellChangeTimes->{ 3.621133660150117*^9, {3.621133765752186*^9, 3.621133786350543*^9}}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[{ RowBox[{ RowBox[{"u3", "=", RowBox[{"{", RowBox[{ RowBox[{"1", "/", "2"}], ",", RowBox[{"1", "/", "2"}], ",", "0", ",", "0", ",", "0", ",", "0", ",", "0"}], "}"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"k", "=", "1"}], ",", " ", RowBox[{"k", "\[LessEqual]", "10"}], ",", " ", RowBox[{"k", "++"}], ",", " ", RowBox[{"Print", "[", RowBox[{"N", "[", RowBox[{ RowBox[{"MatrixPower", "[", RowBox[{"T", ",", "k"}], "]"}], ".", "u3"}], "]"}], "]"}]}], "]"}]}], "Input", CellChangeTimes->{{3.620403153519567*^9, 3.620403213254784*^9}, { 3.620403244040474*^9, 3.620403322682033*^9}, {3.621132194874023*^9, 3.621132285032642*^9}, {3.621132359415555*^9, 3.621132359842704*^9}, { 3.621133429016123*^9, 3.6211334724185743`*^9}, {3.62113363201539*^9, 3.621133656516343*^9}, {3.621133783794557*^9, 3.6211337839870033`*^9}, { 3.6211344394709044`*^9, 3.6211345400257063`*^9}}, FontSize->72, Background->RGBColor[0.87, 0.94, 1]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.6211345434644403`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.621134543468543*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.6211345434719133`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.621134543475113*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.621134543478136*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.6211345434810553`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.621134543483983*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.621134543486883*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.621134543489785*^9}}], Cell[BoxData[ StyleBox[ RowBox[{"{", RowBox[{ "0.5`", ",", "0.5`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`", ",", "0.`"}], "}"}], FontSize->96]], "Print", CellChangeTimes->{{3.621134506819436*^9, 3.621134543492723*^9}}] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["\<\ Let us now choose a damping factor p different from 0 and redo the previous \ computations.\ \>", "Subsection", CellChangeTimes->{{3.621460924347661*^9, 3.6214609782810707`*^9}}], Cell[BoxData[{ RowBox[{ RowBox[{"B", "=", RowBox[{"Table", "[", RowBox[{ RowBox[{"1", "/", "n"}], ",", RowBox[{"{", "n", "}"}], ",", RowBox[{"{", "n", "}"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"p", "=", "0.2"}], ";"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"M", "=", RowBox[{ RowBox[{ RowBox[{"(", RowBox[{"1", "-", "p"}], ")"}], "*", "T"}], "+", RowBox[{"p", "*", "B"}]}]}], ";", " ", RowBox[{"MatrixForm", "[", "M", "]"}]}], "\[IndentingNewLine]", RowBox[{"For", "[", RowBox[{ RowBox[{"k", "=", "1"}], ",", " ", RowBox[{"k", "\[LessEqual]", "10"}], ",", " ", RowBox[{"k", "++"}], ",", " ", RowBox[{"Print", "[", RowBox[{ RowBox[{"MatrixPower", "[", RowBox[{"M", ",", "k"}], "]"}], ".", "u2"}], "]"}]}], "]"}]}], "Input", CellChangeTimes->{{3.620404337769456*^9, 3.62040451437879*^9}, 3.620404604611856*^9, {3.620404807790077*^9, 3.620404863388134*^9}, { 3.620405061769307*^9, 3.620405062374915*^9}, {3.621134026372072*^9, 3.62113405582751*^9}, {3.621134105384095*^9, 3.621134122135354*^9}, 3.6211341587916813`*^9, 3.6211342177013073`*^9, {3.621134248829068*^9, 3.621134249332255*^9}, {3.621134566586175*^9, 3.621134571289679*^9}, 3.621134610643564*^9}, FontSize->16, Background->RGBColor[0.87, 0.94, 1]], Cell[CellGroupData[{ Cell[BoxData[ StyleBox[ TagBox[ RowBox[{"(", "\[NoBreak]", GridBox[{ {"0.02857", "0.82857", "0.02857", "0.02857", "0.02857", "0.02857", "0.02857"}, {"0.82857", "0.02857", "0.02857", "0.02857", "0.02857", "0.02857", "0.02857"}, {"0.02857", "0.02857", "0.02857", "0.42857", "0.42857", "0.02857", "0.02857"}, {"0.02857", "0.02857", "0.22857", "0.02857", "0.42857", "0.82857", "0.42857"}, {"0.02857", "0.02857", "0.22857", "0.42857", "0.02857", "0.02857", "0.42857"}, {"0.02857", "0.02857", "0.22857", "0.02857", "0.02857", "0.02857", "0.02857"}, {"0.02857", "0.02857", "0.22857", "0.02857", "0.02857", "0.02857", "0.02857"} }, GridBoxAlignment->{ "Columns" -> {{Center}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], "\[NoBreak]", ")"}], Function[BoxForm`e$, MatrixForm[BoxForm`e$]]], FontColor->RGBColor[1, 0, 0]]], "Input", CellChangeTimes->{ 3.652700017015407*^9, {3.6527000680533113`*^9, 3.652700291627816*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714282`", ",", "0.14285714285714282`", ",", "0.14285714285714285`", ",", "0.2857142857142857`", ",", "0.17142857142857143`", ",", "0.05714285714285715`", ",", "0.05714285714285715`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.621134613543118*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.1428571428571429`", ",", "0.1428571428571429`", ",", "0.21142857142857147`", ",", "0.19428571428571428`", ",", "0.1942857142857143`", ",", "0.057142857142857155`", ",", "0.057142857142857155`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.62113461354418*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714293`", ",", "0.14285714285714293`", ",", "0.18400000000000002`", ",", "0.2171428571428572`", ",", "0.17142857142857146`", ",", "0.07085714285714288`", ",", "0.07085714285714288`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.621134613546331*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.1428571428571429`", ",", "0.1428571428571429`", ",", "0.18400000000000008`", ",", "0.21897142857142865`", ",", "0.18057142857142866`", ",", "0.06537142857142858`", ",", "0.06537142857142858`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.621134613547297*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714293`", ",", "0.14285714285714293`", ",", "0.18838857142857154`", ",", "0.21604571428571434`", ",", "0.1791085714285715`", ",", "0.0653714285714286`", ",", "0.0653714285714286`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.621134613548259*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714296`", ",", "0.14285714285714296`", ",", "0.18663314285714294`", ",", "0.21633828571428584`", ",", "0.1788160000000001`", ",", "0.0662491428571429`", ",", "0.0662491428571429`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.621134613549232*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714296`", ",", "0.14285714285714296`", ",", "0.18663314285714297`", ",", "0.21692342857142868`", ",", "0.1789330285714287`", ",", "0.06589805714285718`", ",", "0.06589805714285718`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.621134613550221*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.142857142857143`", ",", "0.142857142857143`", ",", "0.18691401142857156`", ",", "0.2165489371428573`", ",", "0.17902665142857158`", ",", "0.06589805714285718`", ",", "0.06589805714285718`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.621134613551186*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714296`", ",", "0.14285714285714296`", ",", "0.18680166400000017`", ",", "0.21664256000000018`", ",", "0.17893302857142873`", ",", "0.06595423085714291`", ",", "0.06595423085714291`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.621134613552149*^9}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14285714285714302`", ",", "0.14285714285714302`", ",", "0.18680166400000014`", ",", "0.2166500498285716`", ",", "0.17897047771428587`", ",", "0.06593176137142862`", ",", "0.06593176137142862`"}], "}"}]], "Print", CellChangeTimes->{3.62113425278716*^9, 3.621134574035973*^9, 3.621134613553187*^9}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"For", "[", RowBox[{ RowBox[{"k", "=", "1"}], ",", " ", RowBox[{"k", "\[LessEqual]", "20"}], ",", " ", RowBox[{"k", "++"}], ",", " ", RowBox[{"Print", "[", RowBox[{ RowBox[{"MatrixPower", "[", RowBox[{"M", ",", "k"}], "]"}], ".", "u3"}], "]"}]}], "]"}]], "Input", CellChangeTimes->{{3.621134623232485*^9, 3.621134666350918*^9}}, FontSize->16, Background->RGBColor[0.87, 0.94, 1]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"{", RowBox[{ "0.4285714285714286`", ",", "0.4285714285714286`", ",", "0.02857142857142857`", ",", "0.02857142857142857`", ",", "0.02857142857142857`", ",", "0.02857142857142857`", ",", "0.02857142857142857`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.62113467351558*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.37142857142857155`", ",", "0.37142857142857155`", ",", "0.051428571428571435`", ",", "0.08000000000000002`", ",", "0.05714285714285715`", ",", "0.034285714285714294`", ",", "0.034285714285714294`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.6211346735174847`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.3257142857142859`", ",", "0.3257142857142859`", ",", "0.08342857142857145`", ",", "0.1028571428571429`", ",", "0.0845714285714286`", ",", "0.03885714285714287`", ",", "0.03885714285714287`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.62113467351974*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.2891428571428573`", ",", "0.2891428571428573`", ",", "0.10354285714285719`", ",", "0.12571428571428578`", ",", "0.1019428571428572`", ",", "0.04525714285714287`", ",", "0.04525714285714287`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.621134673520728*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.2598857142857145`", ",", "0.2598857142857145`", ",", "0.11963428571428579`", ",", "0.14436571428571435`", ",", "0.11766857142857148`", ",", "0.04928000000000002`", ",", "0.04928000000000002`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.62113467352169*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.23648000000000025`", ",", "0.23648000000000025`", ",", "0.13338514285714292`", ",", "0.15870171428571445`", ",", "0.12995657142857153`", ",", "0.052498285714285754`", ",", "0.052498285714285754`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.6211346735226593`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.21775542857142882`", ",", "0.21775542857142882`", ",", "0.14403474285714302`", ",", "0.17022902857142871`", ",", "0.13972845714285728`", ",", "0.055248457142857185`", ",", "0.055248457142857185`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.6211346735236397`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.20277577142857162`", ",", "0.20277577142857162`", ",", "0.152554422857143`", ",", "0.17956790857142876`", ",", "0.14756937142857157`", ",", "0.05737837714285719`", ",", "0.05737837714285719`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.621134673524621*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.19079204571428587`", ",", "0.19079204571428587`", ",", "0.15942634057142874`", ",", "0.18696411428571447`", ",", "0.15386082742857157`", ",", "0.05908231314285721`", ",", "0.05908231314285721`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.62113467352561*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.1812050651428574`", ",", "0.1812050651428574`", ",", "0.16490140525714303`", ",", "0.1928998034285716`", ",", "0.15887526765714302`", ",", "0.06045669668571434`", ",", "0.06045669668571434`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.621134673526599*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.17353548068571456`", ",", "0.17353548068571456`", ",", "0.16928145700571448`", ",", "0.1976498527085716`", ",", "0.16289430966857163`", ",", "0.06155170962285722`", ",", "0.06155170962285722`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.621134673527575*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.16739981312000035`", ",", "0.16739981312000035`", ",", "0.17278909352228597`", ",", "0.2014474953874289`", ",", "0.16610834490514315`", ",", "0.06242771997257153`", ",", "0.06242771997257153`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.6211346735285683`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.16249127906742888`", ",", "0.16249127906742888`", ",", "0.17559376468845744`", ",", "0.2044858492050289`", ",", "0.16867933341988597`", ",", "0.06312924727588581`", ",", "0.06312924727588581`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.62113467352955*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.15856445182537177`", ",", "0.15856445182537177`", ",", "0.1778375016213946`", ",", "0.2069170116081375`", ",", "0.170736220101486`", ",", "0.0636901815091201`", ",", "0.0636901815091201`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.621134673530559*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.15542299003172605`", ",", "0.15542299003172605`", ",", "0.17963272125527807`", ",", "0.2088616347472461`", ",", "0.17238180614261064`", ",", "0.06413892889570755`", ",", "0.06413892889570755`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.621134673531529*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.1529098205968094`", ",", "0.1529098205968094`", ",", "0.18106880492737132`", ",", "0.21041740995437755`", ",", "0.17369819827966568`", ",", "0.06449797282248422`", ",", "0.06449797282248422`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.621134673532549*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.15089928504887617`", ",", "0.15089928504887617`", ",", "0.18221767186504595`", ",", "0.21166203625575022`", ",", "0.1747513426676476`", ",", "0.06478518955690289`", ",", "0.06478518955690289`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.6211346735335197`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14929085661052952`", ",", "0.14929085661052952`", ",", "0.18313678014078777`", ",", "0.21265772747978032`", ",", "0.17559385326949908`", ",", "0.06501496294443782`", ",", "0.06501496294443782`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.6211346735345097`*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14800411385985224`", ",", "0.14800411385985224`", ",", "0.18387206087114039`", ",", "0.2134542814407112`", ",", "0.17626786076927345`", ",", "0.06519878459958617`", ",", "0.06519878459958617`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.62113467353548*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ "0.14697471965931053`", ",", "0.14697471965931053`", ",", "0.18446028545542253`", ",", "0.21409152657286948`", ",", "0.17680706716177572`", ",", "0.0653458407456567`", ",", "0.0653458407456567`"}], "}"}]], "Print", CellChangeTimes->{{3.621134626696238*^9, 3.621134673536434*^9}}] }, Open ]] }, Open ]] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Tips for the project:", "Section", CellChangeTimes->{{3.621135065662195*^9, 3.621135070221874*^9}, { 3.621135252234126*^9, 3.621135254218314*^9}}], Cell[CellGroupData[{ Cell[TextData[{ "Create a graph (random or taken from a list). Use the command ", StyleBox["Graph[{List of vertices}, {List of Edges}]", FontWeight->"Bold"], " to create a graph starting from a set of vertices and edges. You can also \ create a graph starting from the adjacency matrix if you use the command ", StyleBox["AdjacencyGraph[Matrix]", FontWeight->"Bold"], ". Do not use ", StyleBox["GraphPlot[...]", FontWeight->"Bold"], " to create graphs, use it only for display, because it creates a Graphics \ object, and not a Graph object. So you will end up with an object that can be \ nicely plotted, but most of the ", StyleBox["Mathematica", FontSlant->"Italic"], " algorithms for graphs will not work with Graphics objects." }], "Item", CellChangeTimes->{{3.621135081669848*^9, 3.621135240954721*^9}, { 3.62113527378305*^9, 3.6211354755463343`*^9}, 3.652663554133258*^9}, TextJustification->1., FontSize->16], Cell["\<\ Find the Transition Matrix of the graph, using the function that you wrote \ for HW2. Change the Transition Matrix to get rid of the Dangling Nodes (that \ is, change the 0-columns, if any). \ \>", "Item", CellChangeTimes->{{3.621135081669848*^9, 3.621135240954721*^9}, { 3.62113527378305*^9, 3.621135578154253*^9}, {3.6211356166016207`*^9, 3.621135661658819*^9}, {3.6211803747650757`*^9, 3.6211804099827223`*^9}}, TextJustification->1., FontSize->16], Cell["\<\ If n is the number of vertices of your graph, then generate an nxn matrix \ with all elements equal to 1/n.\ \>", "Item", CellChangeTimes->{{3.621135081669848*^9, 3.621135240954721*^9}, { 3.62113527378305*^9, 3.621135578154253*^9}, {3.6211356166016207`*^9, 3.6211356919991493`*^9}, {3.621135739036528*^9, 3.6211357390402727`*^9}}, TextJustification->1., FontSize->16], Cell[TextData[{ "Find the unique probabilistic eigenvector corresponding to the eigenvalue \ 1. Since you have to higlight the most important 5 vertices, you may need to \ sort your page-rank vector. ", StyleBox["Sort[List] ", FontWeight->"Bold"], "will give the elements in increasing order. ", StyleBox["Sort[List, Greater] ", FontWeight->"Bold"], "sorts the list in decreasing order, as you can see by executing the \ one-line code below. You can then use the top 5 values to highlight the most \ important nodes in the graph." }], "Item", CellChangeTimes->{{3.621135081669848*^9, 3.621135240954721*^9}, { 3.62113527378305*^9, 3.621135578154253*^9}, {3.6211356166016207`*^9, 3.6211356919991493`*^9}, {3.621135739036528*^9, 3.621135784459478*^9}, { 3.62113610228976*^9, 3.621136183796381*^9}, {3.6211362973709517`*^9, 3.6211363358481503`*^9}, {3.621136392401271*^9, 3.6211363924077578`*^9}, { 3.621136654825543*^9, 3.621136659425664*^9}, {3.621136693370592*^9, 3.621136714297945*^9}, {3.621180436928877*^9, 3.6211804645931063`*^9}, { 3.621459384170936*^9, 3.621459406818742*^9}}, TextJustification->1., FontSize->16] }, Open ]], Cell[BoxData[ RowBox[{"Sort", "[", RowBox[{ RowBox[{"{", RowBox[{"0.2", ",", "0.55", ",", "0.1", ",", "0.8"}], "}"}], ",", " ", "Greater"}], "]"}]], "Input", CellChangeTimes->{{3.6211805035380373`*^9, 3.621180531048592*^9}}, FontSize->16, Background->RGBColor[0.87, 0.94, 1]], Cell[CellGroupData[{ Cell["\<\ To show a step-by-step computation of the page-rank vector, one needs to \ start with a probabilistic eigenvector u and multiply u by successive powers \ of the (modified) Transition Matrix. At first run, you can assume that k<=50 \ and color the vertices according to the ranks given by u, Tu, T^2u, ... \ ,T^ku. The sequence should converge exponentially fast to the page-rank \ vector, so you should see the relative rankings stabilizing after a couple of \ steps. If you discover than a bigger value of k is needed, you can adjust k \ afterwards. \ \>", "Item", CellChangeTimes->{{3.621135081669848*^9, 3.621135240954721*^9}, { 3.62113527378305*^9, 3.621135578154253*^9}, {3.6211356166016207`*^9, 3.6211356919991493`*^9}, {3.621135739036528*^9, 3.621135784459478*^9}, { 3.62113610228976*^9, 3.621136183796381*^9}, {3.6211362973709517`*^9, 3.6211363358481503`*^9}, {3.621136392401271*^9, 3.621136643391029*^9}, { 3.62117598698378*^9, 3.6211760707853823`*^9}, {3.621177150128793*^9, 3.621177268779331*^9}, {3.697258508881261*^9, 3.6972585326759567`*^9}}, TextJustification->1., FontSize->16], Cell["\<\ Make sure first that your project works on the test graphs (and other fixed \ graphs)! Then make it work for random graphs. \ \>", "Item", CellChangeTimes->{{3.621135081669848*^9, 3.621135240954721*^9}, { 3.62113527378305*^9, 3.621135578154253*^9}, {3.6211356166016207`*^9, 3.6211356919991493`*^9}, {3.621135739036528*^9, 3.621135784459478*^9}, { 3.62113610228976*^9, 3.621136183796381*^9}, {3.6211362973709517`*^9, 3.6211363358481503`*^9}, {3.621136392401271*^9, 3.621136643385819*^9}, { 3.6211802980568953`*^9, 3.621180337839795*^9}, {3.621459429631958*^9, 3.6214594296592197`*^9}, {3.6972585561315403`*^9, 3.6972585570594807`*^9}}, TextJustification->1., FontSize->16], Cell["\<\ Working with random graphs inside Manipulate[...] can be a little bit tricky \ if you have a couple of sliders. In particular, you may discover that a new \ graph is generated each time you move a slider, even if the slider has no \ connection with the graph. The examples below should help see why.\ \>", "Item", CellChangeTimes->{{3.621135081669848*^9, 3.621135240954721*^9}, { 3.62113527378305*^9, 3.621135578154253*^9}, {3.6211356166016207`*^9, 3.6211356919991493`*^9}, {3.621135739036528*^9, 3.621135784459478*^9}, { 3.62113610228976*^9, 3.621136183796381*^9}, {3.6211362973709517`*^9, 3.6211363358481503`*^9}, {3.621136392401271*^9, 3.621136643385819*^9}, { 3.6211802980568953`*^9, 3.621180337839795*^9}, {3.621459429631958*^9, 3.621459569739394*^9}}, TextJustification->1., FontSize->16] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["\<\ Working with random elements inside Manipulate - Easier or Harder?\ \>", "Section", CellChangeTimes->{{3.621175941801478*^9, 3.6211759581244907`*^9}, { 3.621179448673835*^9, 3.621179455673559*^9}}], Cell[TextData[{ StyleBox["How about generating random elements inside the body of ", Background->RGBColor[1, 0.85, 0.85]], StyleBox["Manipulate[ ...]", FontWeight->"Bold", Background->RGBColor[1, 0.85, 0.85]], StyleBox["?", Background->RGBColor[1, 0.85, 0.85]], " Should the code below reevaluate itself as fast as possible, each time \ generating a new random integer?" }], "Text", CellChangeTimes->{{3.621179819232498*^9, 3.6211798678393927`*^9}, { 3.6214597140119133`*^9, 3.621459758904436*^9}}, FontSize->16], Cell[BoxData[ RowBox[{"Manipulate", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{"x", " ", "=", RowBox[{"RandomInteger", "[", "n", "]"}]}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"n", ",", RowBox[{"{", RowBox[{"10", ",", "100"}], "}"}]}], "}"}]}], "\[IndentingNewLine]", "]"}]], "Input", CellChangeTimes->{{3.621175967657094*^9, 3.6211759710325403`*^9}, { 3.621176296891788*^9, 3.621176451471263*^9}, {3.621176578999605*^9, 3.6211765810677557`*^9}, {3.6211783204439697`*^9, 3.6211783220668993`*^9}, { 3.621178361634738*^9, 3.6211784704234858`*^9}, {3.6211785175603313`*^9, 3.6211785210230103`*^9}}, FontSize->16, Background->RGBColor[0.87, 0.94, 1]], Cell[TextData[{ "Every time you evaluate ", StyleBox["RandomReal[...]", FontWeight->"Bold"], " or ", StyleBox["RandomInteger[...]", FontWeight->"Bold"], " or ", StyleBox["RandomGraph[...]", FontWeight->"Bold"], ", you get a different answer, and you might think that an assignment like \ ", StyleBox["x=RandomReal[...]", FontWeight->"Bold"], " inside ", StyleBox["Manipulate[...]", FontWeight->"Bold"], " should therefore constantly update itself as fast as possible. But this \ would normally not be useful, and would in fact have negative consequences \ for a number of algorithms that use randomness internally. For this reason, \ these functions are not \"", StyleBox["ticklish", FontWeight->"Bold", FontColor->RGBColor[1, 0, 0]], "\", in the sense that they do not trigger updates. If you want to see \ actually new random numbers, you have to use Refresh to specify how \ frequently you want the output updated. " }], "Text", CellChangeTimes->{{3.621176831728299*^9, 3.621176855505334*^9}, 3.6211769105862217`*^9, {3.6211769840836573`*^9, 3.621176992916872*^9}, { 3.62117731140322*^9, 3.621177392721541*^9}, {3.621178243427885*^9, 3.621178286569848*^9}}, TextJustification->1., FontSize->16] }, Open ]], Cell[CellGroupData[{ Cell["Harder because ...", "Section", CellChangeTimes->{{3.6211794774585133`*^9, 3.621179515233142*^9}}], Cell["\<\ In the next example, we want to build an interactive model with two controls, \ n and u, that generates a random graph called K with n vertices and 2n edges \ and highlights vertex u of graph K.\ \>", "Text", CellChangeTimes->{{3.621460321022421*^9, 3.621460416232041*^9}, { 3.653097651968685*^9, 3.653097663367029*^9}}, FontSize->16], Cell[TextData[{ StyleBox["Problem:", FontWeight->"Bold", FontColor->RGBColor[1, 0, 0]], " A new graph should be generated only when we change n, the number of \ nodes. However, when the vertex u is changed, the graph changes as well! So \ each time we change u, we highlight vertex u of a different graph." }], "Text", CellDingbat->"\[WatchIcon]", CellChangeTimes->{{3.6211792977584143`*^9, 3.6211793545760527`*^9}, { 3.621179408305175*^9, 3.621179410305584*^9}, {3.621460110690237*^9, 3.62146019072269*^9}, {3.653102324536306*^9, 3.653102326034692*^9}}, FontSize->16], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Manipulate", "[", "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{"K", "=", RowBox[{"RandomGraph", "[", RowBox[{"{", RowBox[{"n", ",", RowBox[{"2", "*", "n"}]}], "}"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"HighlightGraph", "[", RowBox[{"K", ",", RowBox[{"{", "u", "}"}], ",", " ", RowBox[{"GraphStyle", "\[Rule]", "\"\\""}]}], "]"}]}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"n", ",", RowBox[{"{", RowBox[{"5", ",", "6", ",", "7", ",", "8"}], "}"}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"u", ",", "1", ",", "n", ",", "1"}], "}"}]}], "\[IndentingNewLine]", "]"}]], "Input", CellChangeTimes->{{3.621177559783477*^9, 3.621177653008875*^9}, { 3.621177775302866*^9, 3.621177939557502*^9}, {3.621177993424965*^9, 3.621178023536051*^9}, {3.621178061145659*^9, 3.621178073704356*^9}, { 3.621178131641036*^9, 3.621178136775504*^9}}, FontSize->36, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ TagBox[ StyleBox[ DynamicModuleBox[{$CellContext`n$$ = 8, $CellContext`u$$ = 8, Typeset`show$$ = True, Typeset`bookmarkList$$ = {}, Typeset`bookmarkMode$$ = "Menu", Typeset`animator$$, Typeset`animvar$$ = 1, Typeset`name$$ = "\"untitled\"", Typeset`specs$$ = {{ Hold[$CellContext`n$$], {5, 6, 7, 8}}, { Hold[$CellContext`u$$], 1, Dynamic[$CellContext`n$$], 1}}, Typeset`size$$ = {360., {122., 129.}}, Typeset`update$$ = 0, Typeset`initDone$$, Typeset`skipInitDone$$ = True, $CellContext`n$16028$$ = 0, $CellContext`u$16029$$ = 0}, DynamicBox[Manipulate`ManipulateBoxes[ 1, StandardForm, "Variables" :> {$CellContext`n$$ = 5, $CellContext`u$$ = 1}, "ControllerVariables" :> { Hold[$CellContext`n$$, $CellContext`n$16028$$, 0], Hold[$CellContext`u$$, $CellContext`u$16029$$, 0]}, "OtherVariables" :> { Typeset`show$$, Typeset`bookmarkList$$, Typeset`bookmarkMode$$, Typeset`animator$$, Typeset`animvar$$, Typeset`name$$, Typeset`specs$$, Typeset`size$$, Typeset`update$$, Typeset`initDone$$, Typeset`skipInitDone$$}, "Body" :> (K = RandomGraph[{$CellContext`n$$, 2 $CellContext`n$$}]; HighlightGraph[K, {$CellContext`u$$}, GraphStyle -> "SmallNetwork"]), "Specifications" :> {{$CellContext`n$$, {5, 6, 7, 8}}, {$CellContext`u$$, 1, Dynamic[$CellContext`n$$], 1}}, "Options" :> {}, "DefaultOptions" :> {}], ImageSizeCache->{409., {188., 196.}}, SingleEvaluation->True], Deinitialization:>None, DynamicModuleValues:>{}, SynchronousInitialization->True, UndoTrackedVariables:>{Typeset`show$$, Typeset`bookmarkMode$$}, UnsavedVariables:>{Typeset`initDone$$}, UntrackedVariables:>{Typeset`size$$}], "Manipulate", Deployed->True, StripOnInput->False], Manipulate`InterpretManipulate[1]]], "Output", CellChangeTimes->{3.6211781401340017`*^9, 3.653096280402663*^9}] }, Open ]], Cell[CellGroupData[{ Cell["\<\ Making K a local variable inside Module[...] does not solve the problem, \ because the line K=RandomGraph[...] did not trigger by itself any \ reevaluations!\ \>", "Subsection", CellChangeTimes->{{3.621179952520317*^9, 3.62117999706319*^9}, { 3.6214604644019136`*^9, 3.6214604963700314`*^9}, {3.654491807615303*^9, 3.654491808430666*^9}}, TextJustification->1.], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Manipulate", "[", RowBox[{ RowBox[{"Module", "[", RowBox[{ RowBox[{"{", "K", "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"K", "=", RowBox[{"RandomGraph", "[", RowBox[{"{", RowBox[{"n", ",", RowBox[{"2", "*", "n"}]}], "}"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"HighlightGraph", "[", RowBox[{"K", ",", RowBox[{"{", "u", "}"}], ",", " ", RowBox[{"GraphStyle", "\[Rule]", "\"\\""}]}], "]"}]}]}], "]"}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"n", ",", RowBox[{"{", RowBox[{"5", ",", "6", ",", "7", ",", "8"}], "}"}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"u", ",", "1", ",", "n", ",", "1"}], "}"}]}], "\[IndentingNewLine]", "]"}]], "Input", CellChangeTimes->{{3.621177559783477*^9, 3.621177653008875*^9}, { 3.621177775302866*^9, 3.621177939557502*^9}, {3.621177993424965*^9, 3.621178023536051*^9}, {3.621178061145659*^9, 3.621178073704356*^9}, { 3.621178131641036*^9, 3.621178136775504*^9}, {3.621179129448821*^9, 3.62117917011154*^9}}, FontSize->72, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ TagBox[ StyleBox[ DynamicModuleBox[{$CellContext`n$$ = 7, $CellContext`u$$ = 6, Typeset`show$$ = True, Typeset`bookmarkList$$ = {}, Typeset`bookmarkMode$$ = "Menu", Typeset`animator$$, Typeset`animvar$$ = 1, Typeset`name$$ = "\"untitled\"", Typeset`specs$$ = {{ Hold[$CellContext`n$$], {5, 6, 7, 8}}, { Hold[$CellContext`u$$], 1, Dynamic[$CellContext`n$$], 1}}, Typeset`size$$ = {360., {81., 89.}}, Typeset`update$$ = 0, Typeset`initDone$$, Typeset`skipInitDone$$ = True, $CellContext`n$35074$$ = 0, $CellContext`u$35075$$ = 0}, DynamicBox[Manipulate`ManipulateBoxes[ 1, StandardForm, "Variables" :> {$CellContext`n$$ = 5, $CellContext`u$$ = 1}, "ControllerVariables" :> { Hold[$CellContext`n$$, $CellContext`n$35074$$, 0], Hold[$CellContext`u$$, $CellContext`u$35075$$, 0]}, "OtherVariables" :> { Typeset`show$$, Typeset`bookmarkList$$, Typeset`bookmarkMode$$, Typeset`animator$$, Typeset`animvar$$, Typeset`name$$, Typeset`specs$$, Typeset`size$$, Typeset`update$$, Typeset`initDone$$, Typeset`skipInitDone$$}, "Body" :> Module[{K$}, K$ = RandomGraph[{$CellContext`n$$, 2 $CellContext`n$$}]; HighlightGraph[K$, {$CellContext`u$$}, GraphStyle -> "SmallNetwork"]], "Specifications" :> {{$CellContext`n$$, {5, 6, 7, 8}}, {$CellContext`u$$, 1, Dynamic[$CellContext`n$$], 1}}, "Options" :> {}, "DefaultOptions" :> {}], ImageSizeCache->{409., {147., 155.}}, SingleEvaluation->True], Deinitialization:>None, DynamicModuleValues:>{}, SynchronousInitialization->True, UndoTrackedVariables:>{Typeset`show$$, Typeset`bookmarkMode$$}, UnsavedVariables:>{Typeset`initDone$$}, UntrackedVariables:>{Typeset`size$$}], "Manipulate", Deployed->True, StripOnInput->False], Manipulate`InterpretManipulate[1]]], "Output", CellChangeTimes->{3.653102363605974*^9}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["\<\ Making K a local variable inside a DynamicModule[ ...] solves the problem.\ \>", "Subsection", CellChangeTimes->{{3.621180595242331*^9, 3.621180635924445*^9}}], Cell[CellGroupData[{ Cell[BoxData[ StyleBox[ RowBox[{"Manipulate", "[", RowBox[{ RowBox[{"DynamicModule", "[", RowBox[{ RowBox[{"{", "K", "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"K", "=", RowBox[{"RandomGraph", "[", RowBox[{"{", RowBox[{"n", ",", RowBox[{"2", "*", "n"}]}], "}"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Dynamic", "[", RowBox[{"HighlightGraph", "[", RowBox[{"K", ",", RowBox[{"{", "u", "}"}], ",", " ", RowBox[{"GraphStyle", "\[Rule]", "\"\\""}]}], "]"}], "]"}]}]}], "]"}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{"n", ",", RowBox[{"{", RowBox[{"5", ",", "6", ",", "7", ",", "8"}], "}"}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"u", ",", "1"}], "}"}], ",", "1", ",", "n", ",", "1"}], "}"}]}], "\[IndentingNewLine]", "]"}], FontSize->48]], "Input", CellChangeTimes->{{3.621177559783477*^9, 3.621177653008875*^9}, { 3.621177775302866*^9, 3.621177939557502*^9}, {3.621177993424965*^9, 3.621178023536051*^9}, {3.621178061145659*^9, 3.621178073704356*^9}, { 3.621178131641036*^9, 3.621178136775504*^9}, {3.621179129448821*^9, 3.62117917011154*^9}, {3.621179205481122*^9, 3.621179235424777*^9}, { 3.62118064875171*^9, 3.621180725168351*^9}, {3.621181426625471*^9, 3.6211814753929367`*^9}, {3.621181724951091*^9, 3.621181733752616*^9}, { 3.621181767051732*^9, 3.621181769108181*^9}, {3.6211841155665817`*^9, 3.621184116580236*^9}, {3.621184147675808*^9, 3.6211841490674143`*^9}, { 3.697258637255443*^9, 3.697258639654256*^9}, {3.6972587261070833`*^9, 3.697258726608994*^9}, {3.69725885147003*^9, 3.6972589122601013`*^9}, { 3.6972613639959517`*^9, 3.697261422124773*^9}, {3.697261465341619*^9, 3.69726156025449*^9}}, FontSize->16, Background->RGBColor[0.87, 0.94, 1]], Cell[BoxData[ TagBox[ StyleBox[ DynamicModuleBox[{$CellContext`n$$ = 5, $CellContext`u$$ = 2, Typeset`show$$ = True, Typeset`bookmarkList$$ = {}, Typeset`bookmarkMode$$ = "Menu", Typeset`animator$$, Typeset`animvar$$ = 1, Typeset`name$$ = "\"untitled\"", Typeset`specs$$ = {{ Hold[$CellContext`n$$], {5, 6, 7, 8}}, {{ Hold[$CellContext`u$$], 1}, 1, Dynamic[$CellContext`n$$], 1}}, Typeset`size$$ = {360., {168., 176.}}, Typeset`update$$ = 0, Typeset`initDone$$, Typeset`skipInitDone$$ = True, $CellContext`n$189576$$ = 0, $CellContext`u$189577$$ = 0}, DynamicBox[Manipulate`ManipulateBoxes[ 1, StandardForm, "Variables" :> {$CellContext`n$$ = 5, $CellContext`u$$ = 1}, "ControllerVariables" :> { Hold[$CellContext`n$$, $CellContext`n$189576$$, 0], Hold[$CellContext`u$$, $CellContext`u$189577$$, 0]}, "OtherVariables" :> { Typeset`show$$, Typeset`bookmarkList$$, Typeset`bookmarkMode$$, Typeset`animator$$, Typeset`animvar$$, Typeset`name$$, Typeset`specs$$, Typeset`size$$, Typeset`update$$, Typeset`initDone$$, Typeset`skipInitDone$$}, "Body" :> DynamicModule[{K}, K = RandomGraph[{$CellContext`n$$, 2 $CellContext`n$$}]; Dynamic[ HighlightGraph[ K, {$CellContext`u$$}, GraphStyle -> "SmallNetwork"]]], "Specifications" :> {{$CellContext`n$$, {5, 6, 7, 8}}, {{$CellContext`u$$, 1}, 1, Dynamic[$CellContext`n$$], 1}}, "Options" :> {}, "DefaultOptions" :> {}], ImageSizeCache->{409., {234., 242.}}, SingleEvaluation->True], Deinitialization:>None, DynamicModuleValues:>{}, SynchronousInitialization->True, UndoTrackedVariables:>{Typeset`show$$, Typeset`bookmarkMode$$}, UnsavedVariables:>{Typeset`initDone$$}, UntrackedVariables:>{Typeset`size$$}], "Manipulate", Deployed->True, StripOnInput->False], Manipulate`InterpretManipulate[1]]], "Output", CellChangeTimes->{3.697292726556078*^9}] }, Open ]] }, Open ]], Cell[CellGroupData[{ Cell["Now the model works, but one can make it fancier.", "Subsection", CellChangeTimes->{{3.621180595242331*^9, 3.621180635924445*^9}, { 3.697263615255281*^9, 3.6972636399983807`*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"Manipulate", "[", RowBox[{ RowBox[{"DynamicModule", "[", RowBox[{ RowBox[{"{", "K", "}"}], ",", "\[IndentingNewLine]", RowBox[{ RowBox[{"K", "=", RowBox[{"RandomGraph", "[", RowBox[{ RowBox[{"u", "=", "1"}], ";", RowBox[{"{", RowBox[{"n", ",", RowBox[{"2", "*", "n"}]}], "}"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"Dynamic", "[", RowBox[{"HighlightGraph", "[", RowBox[{"K", ",", RowBox[{"{", RowBox[{"Style", "[", RowBox[{"u", ",", " ", "color"}], "]"}], "}"}], ",", " ", RowBox[{"GraphStyle", "\[Rule]", "\"\\""}]}], "]"}], "]"}]}]}], "]"}], ",", "\[IndentingNewLine]", RowBox[{"Style", "[", RowBox[{ "\"\\"", ",", " ", "12", ",", " ", "Bold"}], "]"}], ",", "\[IndentingNewLine]", RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"u", ",", "1", ",", RowBox[{"Style", "[", RowBox[{"\"\\"", ",", "10"}], "]"}]}], "}"}], ",", "1", ",", RowBox[{"Dynamic", "[", "n", "]"}], ",", "1"}], "}"}], ",", "\[IndentingNewLine]", "Delimiter", ",", "\[IndentingNewLine]", RowBox[{"Style", "[", RowBox[{ "\"\