MAT 331: Project 1

Project description:

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. 
In this project we are interested in the theoretical foundations of the PageRank algorithm, in computing the Page Rank of small-scale graphs and in the effects of particular aspects of web graph structure on the Page Rank vector.

Tasks:

Browse the web and read about the importance of the PageRank algorithm for web searches. Ranking algorithms such as PageRank have also found applications in other areas (population models, biology, article citations, hotel ranking systems, etc.). Give concrete examples of the applications of Page Rank to search engines and to at least three other real life problems. In each case, briefly describe how the ranking algorithm is applied. Please include all relevant references.

Describe how the Page Rank algorithm works. Investigate possible ways to compute the Page Rank vector of a graph (that is, computing eigenvalues, or rather applying the Power Method) and describe their advantages and drawbacks as the size of the graph gets bigger and bigger.

Explain the mathematics behind PageRank.  The algorithm can be explained using ideas from several fields of Mathematics, like probability, linear algebra, dynamical systems or analysis. You can choose the mathematical language that you feel more comfortable with. Feel free to use external sources and articles and include references to any relevant theorems and proofs that you may decide to use. If you decide to follow the steps explained in the lecture notes, then take a look at the lemmas listed at the end and fill in the proofs.

You will next build an interactive model in Mathematica for calculating the Page Rank vector of small scale web graphs, with nodes representing websites and edges representing hyperlinks. The number of nodes is assumed reasonably small, so that your algorithm works relatively fast. Your model should work with random graphs, graphs with dangling nodes, as well as some fixed test graphs, given below. The basic model should display the graph with the first five most important nodes highlighted in different colors and with increased sizes, and the (modified?) transition matrix A of the graph. The extended model should include a step-by step computation of the page-rank vector (at each step, one computes  (A^k)v and highlights the most important 5 vertices according to the page-rank approximation (A^k)v). There are several aspects that your interactive model should take into account:

You should include controls that enable the user to select the desired type of graph and the number of nodes.

The damping factor p should be given as a parameter, with values between 0.01 and 0.5.

The power k should also be given as a parameter, with values between 1 and 50, and with step size 1.

Give some brief instructions on how your model should be tested (how to use the controls, etc.).

Conclusions. Formulate your findings after testing your interactive model on a couple of examples. Is the Page Rank vector in agreement with your natural understanding of the relative importance of nodes? What values of the damping factor seem to give more accurate rankings? You can also copy paste in here any interesting examples that you may have discovered when testing your model.

References. Include all relevant references here.

General considerations:

You will be graded on the quality and maturity of your mathematical explanations, as well as on the efficiency of the Mathematica code that you develop. Your interactive model should reevaluate itself only when the controls are changed (i.e. we change the position of a slider, etc.). When possible, try to avoid performing unnecessary computations (for example, do not use Eigensystem[A] if you are only interested in the eigenspace corresponding to the eigenvalue 1; you may choose not to use MatrixPower[A,k] if you have to compute (A^k) for many successive values of k; etc.) Try to have a nice coding style and use functions when appropriate. Use different names for your variables! Do not include all intermediate output that you may have obtained by testing small parts of your code. All your code, including functions/variable definitions and  Manipulate[..] should be contained in one single Mathematica cell bracket. Before you start working on your project, look also through the Wolfram Demonstration Projects, to get an idea of how a project should look like.

Mathematics:

When explaining the Mathematics behind the Page Rank Algorithm, if you decide to follow the plan outlined in the lectures, don’t forget to give justifications for the following statements:

If A is a column stochastic nxn matrix and v∈(ℝ^n) is a probabilistic vector, then Av is a probabilistic vector.

Hint: By the definition of matrix multiplication, the i-th entry of the vector Av is (Subscript[(Av), i]) = (∑_(j=1)^n)(Subscript[a, ij])(Subscript[v, j]).

If A is a positive nxn matrix and v∈(ℝ^n) a probabilistic vector with non-negative entries, then Av is a vector with all entries positive.

If A is a column stochastic nxn matrix, B is the nxn matrix with all entries equal to 1 and p∈(0,1], then the matrix (1-p)A + p(1/n)B is positive and column stochastic. The number p is called the damping factor.

Let u and v be two probabilistic vectors in (ℝ^n). Define the distance between u and v to be  d(u,v)=(1/2)  (∑_(i=1)^n)|(Subscript[u, i])-(Subscript[v, i])|.

Show first that d verifies the three properties of a distance (metric):

d (u, v) = d (v, u)

d(u, v) ⩽ d(u, w) + d(w, v) where u,v,w are any three vectors in (ℝ^n).

d(u, v) ⩾ 0 for any two vectors u,v and d(u, v) = 0 if and only if u = v.

Next assume that u and v are two probabilistic vectors in (ℝ^n). Show that the distance function is bounded

d(u, v) ⩽ 1.

Assume that u and v are two probabilistic vectors in (ℝ^n). Let S = {1⩽i⩽n,  (Subscript[u, i])> (Subscript[v, i])} be the set of indices i for which the i-th entry of u is strictly greater than the j-th entry of v.

Show that S is a proper subset of {1,2,...,n}, that is, S is nonempty and S≠{1,2,...,n}.

Show that d(u, v)=(Underscript[ ∑, i∈S])(Subscript[u, i])-(Subscript[v, i]) and that d(u, v)<1.

Let A be a positive column stochastic nxn matrix. Show that there exists a real number r, with 0<r<1, such that  d(Au, Av) ⩽ (1-r) d(u, v), for any two probabilistic vectors u and v in (ℝ^n).

Hint: Consider the sets S={1⩽i⩽n,  (Subscript[u, i])> (Subscript[v, i])} and Q={1⩽i⩽n,  (Subscript[(Au), i])> (Subscript[(Av), i])}. Use Lemmas 0.1 and 0.4 to show that these are proper subsets of {1,2,...,n}. Next show that there exists a number r with 0<r<1 such that for any fixed column j of the matrix A, we have the inequality(Underscript[ ∑, i∈Q])(Subscript[a, ij]) < 1-r. The number r can be chosen so that 0<r<min0⩽i,j⩽n{(Subscript[a, ij])}. Then use the definition of matrix multiplication and Lemma 0.4.

Use Lemma 0.6 to show that if A is a positive column stochastic matrix, then there exists a unique probabilistic eigenvector corresponding to the eigenvalue 1.

Let A be a positive column stochastic nxn matrix. Let v be a probabilistic vector of size n. Use Lemma 0.5 and Lemma 0.6  and the ideas discussed in the lecture to show that the sequence v, Av, (A^2)v... , (A^k)v converges to the unique probabilistic eigenvector corresponding to the eigenvalue 1.

Some test graphs:

G1=Graph[{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}, {1->4, 1->6, 1->10,1->11, 2->6, 2->13, 3->1,3->7,3->11, 4->1, 4->11, 5->2, 6->1,6->15,7->1, 7->14,   8->6,8->16, 9->1,9->10,9->14, 10->1, 11->3, 12->8, 13->5,13-> 6, 14->1,14->3,  14->9,15->13,  15->16, 16->12, 16->6, 15->17,17->10,17->18,18->19,18->20,19->20,20->19},GraphStyle->"SmallNetwork", GraphLayout->"SpringEmbedding"]

G2=Graph[{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}, {2->1,  2->6, 3->1,3->7, 4->1, 4->11, 5->2, 5->9, 6->1,6->15,7->1, 7->14, 8->1, 8->4, 8->6, 9->10,9->14, 10->2,10->1,11->12, 11->3, 12->8, 13->5,14->1,14->3,  15->13,  15->16, 16->12},GraphStyle->"SmallNetwork", GraphLayout->"SpringEmbedding"]

G3=Graph[{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}, {1->4, 1->10, 1->6, 2->1,  2->6, 2->13, 3->1,3->7, 4->1, 4->11, 5->2, 5->9,6->15,7->1, 7->14, 8->1, 8->4, 8->6,8->16, 9->10,9->14, 10->2,10->1,11->12, 11->3, 12->8, 13->5,13-> 6, 14->1,14->3,  15->13,  15->16, 16->12, 16->6 },GraphStyle->"SmallNetwork", GraphLayout->"SpringEmbedding"]

G4=Graph[{1,2,3,4,5,6,7,8,9,10,11,12,13,14}, {1->4, 1->10,1->11, 2->6,2->5, 2->13, 3->1,3->7,3->11, 4->1, 4->11, 5->2,5->6, 6->5, 7->1, 7->14,   8->5, 9->1,9->10,9->14, 10->1, 11->3, 12->5, 13->5,13->2, 13-> 6, 14->1,14->3,  14->9},GraphStyle->"SmallNetwork", GraphLayout->"SpringEmbedding"]