Project 3, part 3: Implementing PageRank

Due

In part 2 of this project, we discovered that while TF-IDF works fine in many cases, it's also exploitable.

Websites that want to maximize search traffic to gain more ad revenue or attract more customers can artifically inflate their score by keyword stuffing: by stuffing each webpage full of as many different words and phrases as possible.

We saw this for ourselves in part 2 by running the search engine against the "wikipedia-with-spam" dataset, which contains a mixture of legitimate webpages and spam webpages. We get some useful results, but an alarming amount of spam.

We need a second metric to help penalize that behavior. We will use a simplified version of PageRank, an algorithm invented by (and named after) Larry Page, one of the founders of Google. PageRank is not the only algorithm Google uses, but is one of their more widely known ones.

Part 3a: Build the web graph

Task: Implement PageRankAnalyzer.buildGraph(...).

PageRank works by analyzing a directed graph representing the internet: each webpage is a vertex, and each link is an edge. So, if we want to implement PageRank, we need to first build this graph!

Some notes:

  1. You should represent this graph using an adjacency list. Discuss with your partner: why is an adjacency matrix likely not the best choice here?

  2. If a webpage has multiple outgoing links to the same destination, you should add only a single edge to your graph. That is, there should be no duplicate edges.

  3. If a webpage links to itself, you should omit that link. That is, there should be no self-loops in your graph.

  4. Your buildGraph(...) method will be given a set of web pages as input. If any of those web pages links to something that is not contained within that set, ignore that link. We want our graph to be self-contained: every edge should point to an existing vertex.

Part 3b: Implement PageRank

Task: Implement PageRankAnalyzer.makePageRanks(...).

Next, you will implement the makePageRanks(...) method, which will precompute the page rank for every webpage in your graph. This method should implement the core algorithm as described below:

Core algorithm

PageRank works by ignoring the user's query and instead computing the relative "importance" or "reputability" of a webpage based on what webpages link to it. The intuition is that if many different webpages link to webpage A, then many people are likely to naturally stumble across webpage A just by following links. As a result, we can conclude that webpage A is most likely "important" or "reputable".

Similarly, if webpage A has so many visitors and if webpage A links to just one other webpage, webpage B, we can assume that many users of webpage A are likely to click on that single link B. This means that webpage B will "share" some of the importance of webpage A.

To put it another way, we are looking at the graph representing the internet and trying to emulate how people will naturally traverse that graph!

PageRank works by emulating the above process using the below algorithm:

  1. Initialize step:

    Initially, give each webpage a rank of \(\frac{1}{N}\), where \(N\) is the total number of webpages.

    Intuitively, we're saying that at the very start, about \(\frac{1}{N}\) of all web surfers will start on that webpage: each webpage initially has an equal percentage of visitors.

  2. Update step:

    Next, we will compute the new page rank by simulating the expected behavior of our web surfers.

    1. First, give every web page a new page rank of \(0.0\).

    2. Next, we will take the old page rank for every webpage and equally share it with every web page it links to.

      That is, we loop through each vertex (each webpage) and increase the new rank for every adjacent vertex by the following amount:

      $$ d \times \frac{\text{old page rank}}{\text{number of unique links}} $$

      Here, \(d\) is the "decay" factor: it's a parameter that represents the rate at which your surfers are willing to "continue clicking" a link. We usually set \(d\) equal to roughly \(0.85\): this means that about 85% of your users will be willing to continue visiting new web pages. The other 15% simply stop where they are.

      This decay factor also helps our page ranks converge: they ensure that every time we run the update step, our page ranks change less and less. Note that the closer we set \(d\) to 0, the faster we converge (but the more inaccurate are results are likely to be).

      What happens if a web page has zero out-going links? There are no pages to update, so what happens to the 85% of our visitors who randomly click on links?

      If the web page has no links, we assume those visitors jump to a random webpage. That is, if the current page has no outgoing links, increase the new page rank of every webpage by:

      $$d \times \frac{\text{old page rank}}{N}$$

      That is, we pretend those surfers "jump" to some random page.

    3. Finally, add \(\frac{1 - d}{N}\) every web page's new page rank.

      The technical reason we do this is to make sure our page ranks in total represent a valid probability distribution: we don't want to actually "lose" web surfers when we apply the decay factor.

      Alternatively, you can think of this value as representing the probability some random person starts on the current webpage out-of-the-blue.

  3. Convergence check step:

    We have just completed one iteration of the page rank algorithm! We now need to decide if we need to keep going or if it's ok to stop.

    Compare the difference between the old page rank and the new page rank for each individual webpage. If the difference between the two for every single webpage is less then some user-specified value \(\epsilon\), we can stop recursing: we say our page ranks have converged.

    (Note: \(\epsilon\) is the Greek lower-case letter "epsilon", and is traditionally used to represent some sort of very small number.)

    However, if even a single webpage has a difference greater then \(\epsilon\), we replace the old page ranks with the new ones we just computed and repeat step 2.

Final note: you are not required to implement the PageRank algorithm exactly as described above. You may combine or rearrange certain steps to make your algorithm more efficient if you wish, as long as you get the same (or close to similar) results in the end.

Example 1: Simple graph

Initialize step

Let's look an example of PageRank in action. Suppose we have four web pages arranged like below. Each square is a webpage, and the arrows represent out-going links. Here, page A is basically acting like the "main page": it links to all the pages, and pages B, C, and D all link to it.

After the initialize step runs, we give each page an initial rank of 0.25:

Update step: Iteration 1

We then run the update step once, to obtain the following new ranks. We update the scores of each web pages by the following. (Note: we've picked \(d = 0.85\) as our decay rate here).

So, here is what the graph looks like after iteration 1 is finished:

Remember, the score represents "the percentage of surfers present on the page". So, after iteration 1, about 67.5% percent of our web surfers are present on page A. Pages B, C, and D all have about 10.8333...% of the surfers each. This seems to roughly be what we want! If more surfers are on page A, then it's likely that it's a "more important page".

Update step: iteration 2

We repeat this process again on the next iteration.

This produces the following graph. Now, as the web surfers move again, page A now only has about 31.4% of the web surfers; pages B, C, and D all have about 22.88% each.

Update step: iteration 3

After repeating this process, we get the following results (we omit the calculations this time to save space). Notice that these scores are pretty similar to iteration 1, but are starting to settle down somewhere between iteration 1 and iteration 2's scores:

Update step: iteration 4

And if we repeat again, the scores are similar to iteration 2's, but are starting to settle down even more. The intuition here is that the web surfers are "sloshing" back and forth between page A and pages B, C, and D. However, due to our decay factor, the percentage of surfers that moves between each page decreases slowly over time, so the page's scores start stablizing and converging:

Update step: iteration 100

And finally, if we fast-forward to iteration 100, our scores basically stop changing and have settled down to this:

This final result represents our true page rank score.

Example 2: Cycle

Here is another example of a graph after we run one iteration of PageRank. Interestingly, it turns out no matter how many iterations we run, the result will be exactly the same? Why do you suppose that is?

Example 3: Complex

Here is a more complex example of a graph (which includes a page with no incoming links.

Here is the result after iteration 1:

After iteration 2:

After iteration 3:

After iteration 100 (the final, converged ranks):

Part 3c: Report and analyze results

Task: Finish implementing PageRank.computePageRank(...) and re-run search engine.

Finally, finish implementing the computePageRank(...) method. This method should be just one line: we don't need to do any work since we already pre-computed everything.

Now, try running your search engine against the "spam" dataset again. As before, the setup phase may take some time; the engine should still answer queries nearly instantaneously. And if we try loading the "wikipedia" and "wikipedia-with-spam" pages, the spam pages should be completely filtered out now!

Of course, PageRank isn't perfect. We were able to beat the spam pages that relied on keyword stuffing, but we have almost no defense against other kinds of search manipulation results: in particular, we're now vulnerable to link manipulation.

For example, what if we try constructing web pages that artificially create a large network of links? Or what if we purchase an ad on a popular website/bribe the owner to link back to our site?

It's an endless game of cat-and-mouse.

Part 3d: Complete writeup

Task: submit answers to the following questions.

Each group member should answer and submit these questions independently at this canvas page.

You must submit your answers in either .txt or .pdf form.

  1. Questions about the project:
    1. What is your name and your partner's name?
    2. How was the project? Did you enjoy it?
    3. Do you have any suggestions for improving the project?
  2. Questions about your partner (skip if you worked solo):
    1. Which parts of the project did you work on, and which parts did your partner program? Did you try pair programming?
    2. How was your partnership? Do you feel you and your partners contributed equally to this project?

Deliverables

The following deliverables are due on .

A single person in your group should submit the entire contents of your src folder on Canvas.

Please follow the above instructions EXACTLY. In particular, DO NOT rename your "src" folder before zipping it or modify the folder structure in any way.

Before submitting, be sure to double-check and make sure that...

Both partners should turn in a .txt or .pdf file containing their answers to part 3d at this canvas link. This is due at the same time as the rest of your project.