Project1 (discussion)

The project is based on the Perron-Frobenius Theorem

Theorem: If M is a positive, column stochastic nxn matrix then the following statements are true:

1 is an eigenvalue of M, of multiplicity one

The eigenvalue 1 is the largest eigenvalue of M; all the other eigenvalues of M are strictly less than 1 in absolute value.

There exists a unique probabilistic eigenvector w corresponding to the eigenvalue 1.

(Power Method Convergence) Let v be a probabilistic vector. Then the sequence v, Mv, ... , Mkv converges to w as k goes to ∞.

Recall the following definitions:
      A square matrix is called column stochastic if all its entries are greater than or equal to 0, and the sum of the entries in each column is 1.
      A matrix is called positive if all of its entries are strictly greater than 0.
      A vector is called probabilistic (or a probability distribution vector) if all its entries are greater than or equal to 0 and the sum of all entries is 1.

Page Rank Algorithm

We use the Perron - Frobenius Theorem to give a rigorous mathematical justification for the Page Rank Algorithm.

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.

The Page Rank Algorithm was discussed in class last week. More details on the theoretical aspects can be found at the following link. 
http://www.math.cornell.edu/~mec/Winter2009/RalucaRemus/
Lecture #3 discusses Page Rank from several view points.

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.

Back to the Web Graph

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.

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.

Some of the graphs in the project might also have these problems, especially the randomly generated ones. Then we cannot simply find the “unique” 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

Dangling nodes

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!

H=Graph[{1->2, 3->2}, GraphStyle->"SmallNetwork", VertexSize->0.15];
TransitionH=Transpose[AdjacencyMatrix[H]];
GraphicsRow[{H,MatrixForm[TransitionH]}]

Perron-Frobenius Theorem cannot be directly applied! Still, let us see if the Power Method converges to something useful.

u={1/3,1/3,1/3}; MatrixForm[u]
For[k=1, k≤3, k++, Print[MatrixForm[MatrixPower[TransitionH,k].u]]]

We notice that the sequence of vectors u, Au, ..., (A^k)u 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!

A solution to the Dangling Nodes Problem

Change the transition matrix of the graph so that it becomes column stochastic. More specifically, change any 0-column in the transition matrix with a column where all elements are equal to 1/n.

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.

For[i=1,i≤3,i++, TransitionH[[i,2]]=1/3];
MatrixForm[TransitionH]

u={1/3,1/3,1/3}
For[k=1, k≤40, k++, Print[N[MatrixPower[TransitionH,k].u]]]

Disconnected components

Solution: 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 Page Rank matrix (also known as the Google matrix) of the graph to be 
M=(1-p)T+p(({{(1/n), (1/n), .., (1/n)}, {.., .., .., ..}, {(1/n), (1/n), .., (1/n)}}))

Theorem: If T is a column stochastic matrix, then M is a positive and column stochastic matrix.

The matrix M models the behaviour of the random surfer as follows: 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 “teleport” 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 (1/n) to be chosen. So the Internet graph becomes strongly connected.

An example of a graph with disconnected components

G2=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}, GraphStyle->"SmallNetwork"]

Find the transition matrix first and compute its eigenvalues:

Lout=VertexOutDegree[G2];
TA=Transpose[AdjacencyMatrix[G2]];
f[i_,j_]:=If[Lout[[j]]!=0,TA[[i]][[j]]/Lout[[j]],0];
T= Table[f[i,j],{i,Length[TA]},{j,Length[TA]}];
MatrixForm[T]

(({{0, 1, 0, 0, 0, 0, 0}, {1, 0, 0, 0, 0, 0, 0}, {0, 0, 0, (1/2), (1/2), 0, 0}, {0, 0, (1/4), 0, (1/2), 1, (1/2)}, {0, 0, (1/4), (1/2), 0, 0, (1/2)}, {0, 0, (1/4), 0, 0, 0, 0}, {0, 0, (1/4), 0, 0, 0, 0}}))

Eigenvalues[T]

{-1,1,1,-(1/2),(1/4) (-1+I (Sqrt[3])),(1/4) (-1-I (Sqrt[3])),0}

Eigensystem[T]

{{-1,1,1,-(1/2),(1/4) (-1+I (Sqrt[3])),(1/4) (-1-I (Sqrt[3])),0},{{-1,1,0,0,0,0,0},{0,0,4,(13/3),(11/3),1,1},{1,1,0,0,0,0,0},{0,0,0,-1,1,0,0},{0,0,-1+I (Sqrt[3]),-I (Sqrt[3]),-1,1,1},{0,0,-1-I (Sqrt[3]),I (Sqrt[3]),-1,1,1},{0,0,0,-1,1,-1,1}}}

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 (Subscript[u, 2]) and (Subscript[u, 3]), the sequences (Subscript[u, 2]), T(Subscript[u, 2]), ... T^k(Subscript[u, 2]).... and (Subscript[u, 3]), T(Subscript[u, 3]), ... T^k(Subscript[u, 3])  can converge to different limits, as one can see below:

n=Length[T];
u2=Table[1/n, {n}];
For[k=1, k≤10, k++, Print[N[MatrixPower[T,k].u2]]]

u3={1/2,1/2,0,0,0,0,0};
For[k=1, k≤10, k++, Print[N[MatrixPower[T,k].u3]]]

Let us now choose a damping factor p different from 0 and redo the previous computations.

B=Table[1/n,{n},{n}];
p=0.2;
M=(1-p)*T+p*B; MatrixForm[M]
For[k=1, k≤10, k++, Print[MatrixPower[M,k].u2]]

(({{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}}))

For[k=1, k≤20, k++, Print[MatrixPower[M,k].u3]]

Tips for the project:

Create a graph (random or taken from a list). Use the command Graph[{List of vertices}, {List of Edges}] 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 AdjacencyGraph[Matrix]. Do not use GraphPlot[...] 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 Mathematica algorithms for graphs will not work with Graphics objects.

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).

If n is the number of vertices of your graph, then generate an nxn matrix with all elements equal to 1/n.

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. Sort[List] will give the elements in increasing order.  Sort[List, Greater] 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.

Sort[{0.2,0.55,0.1,0.8}, Greater]

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.

Make sure first that your project works on the test graphs (and other fixed graphs)! Then make it work for random graphs.

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.

Working with random elements inside Manipulate - Easier or Harder?

How about generating random elements inside the body of Manipulate[ ...]? Should the code below reevaluate itself as fast as possible, each time generating a new random integer?

Manipulate[
x =RandomInteger[n],
{n,{10,100}}
]

Every time you evaluate RandomReal[...] or RandomInteger[...] or RandomGraph[...], you get a different answer, and you might think that an assignment like x=RandomReal[...] inside Manipulate[...] 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 "ticklish", 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.

Harder because ...

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.

Problem: 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.

Manipulate[
K=RandomGraph[{n,2*n}];
HighlightGraph[K,{u}, GraphStyle->"SmallNetwork"],
{n,{5,6,7,8}},
{u,1,n,1}
]

Making K a local variable inside Module[...] does not solve the problem, because the line K=RandomGraph[...] did not trigger by itself any reevaluations!

Manipulate[Module[{K},
K=RandomGraph[{n,2*n}];
HighlightGraph[K,{u}, GraphStyle->"SmallNetwork"]],
{n,{5,6,7,8}},
{u,1,n,1}
]

Making K a local variable inside a DynamicModule[ ...] solves the problem.

Manipulate[DynamicModule[{K},
K=RandomGraph[{n,2*n}];
Dynamic[HighlightGraph[K,{u}, GraphStyle->"SmallNetwork"]]],
{n,{5,6,7,8}},
{{u,1},1,n,1}
]

Now the model works, but one can make it fancier.

Manipulate[DynamicModule[{K},
K=RandomGraph[u=1;{n,2*n}];
Dynamic[HighlightGraph[K,{Style[u, color]}, GraphStyle->"SmallNetwork"]]],
Style["Select the number of nodes of the random graph:", 12, Bold],
{{n,7},{5,6,7,8}},
Delimiter,
Style["Select the vertex to highlight:", 12, Bold],
{{u,1,Style["vertex",10]},1,Dynamic[n],1},
Delimiter,
Style["Select the color to highlight:", 12, Bold],
{{color, Green}, ColorSlider}
]

Don’t be afraid to explore the options of Manipulate command to make your model look fancy! You can also read the Wolfram Tutorial on Advanced Manipulate Functionality:
http://reference.wolfram.com/language/tutorial/IntroductionToManipulate.html
http://reference.wolfram.com/language/tutorial/AdvancedManipulateFunctionality.html

Conclusion

For the project, you may consider using the following syntax:

Define functions & global variables

Manipulate[
      DynamicModule[{ graph g},
             Define graph g etc. according to the user choice;
               Dynamic[GraphicsRow, Row, Column, 
                              Grid or other     ... [{
                       Module[{all other local variables},
                           Your page - rank computations here;
                           HighlightGraph[ ...]
                        ]
                  }]]
       ],
 controls for sliders etc.,
 SaveDefinitions->True
 ]