Overview
Due Friday March 1 at 11:59pm.
In part 2a of this project, we discovered that while TFIDF
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 artificially 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 2a
by running the search engine against the
"wikipediawithspam" 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.
You will use these files from prior assignments:
src/main/java/datastructures/concrete/dictionaries/ChainedHashDictionary.java
src/main/java/datastructures/concrete/dictionaries/ArrayDictionary.java
src/main/java/datastructures/concrete/ArrayHeap.java
src/main/java/datastructures/concrete/ChainedHashSet.java
src/main/java/datastructures/concrete/DoubleLinkedList.java
src/main/java/misc/Sorter.java
You will be modifying the following file:
src/main/java/search/analyzers/PageRankAnalyzer.java
Additionally, here are a few more files that you might want to review
while completing the assignment (note that this is just a starting point,
not necessarily an exhaustive list):
src/main/java/search/models/Webpage.java
src/main/java/search/Main.java
Highlevel description
PageRank ignores the user's query and instead focuses on 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 that webpage A is most likely
"important" or "reputable," and many people are likely to naturally stumble across webpage A
just by following links.
Additionally, if a reputable webpage like A links to just one other webpage, webpage B, we
can assume that B is also rather reputable. Since webpage A also has many users, these users are
likely to click on that single link to B, which means that webpage A will "share" some of its
popularity with webpage B. Extrapolating from this logic, we can estimate that a webpage's
reputability is correlated with its "popularity," or number of users.
Because all these webpages end up sharing popularity with each other, calculating an actual
value for popularity is more mathematically complex than simply counting the number of incoming
links. To calculate this efficiently, PageRank uses a sort of simulation that very loosely
mimicks behavior of internet users over time.
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!
The exact algorithm will come later on this page, but here's a video from last quarter
providing a moredetailed version of this highlevel overview. The video is rather lengthy
and is not required to understand or implement the algorithm, but goes over a related example of
simulation using graphs that may help you understand the PageRank algorithm.
Part 2b i: Build the web graph
Task: Implement PageRankAnalyzer.makeGraph(...)
.
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:
You should represent this graph using an adjacency list.
Discuss with your partner: why is an adjacency matrix likely not the best
choice here?
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.
If a webpage links to itself, you should omit that link. That is, there should
be no selfloops in your graph.
Your makeGraph(...)
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
selfcontained: every edge should point to an existing vertex.
Please make sure to read the
other notes and hints section
from the part 2a spec—in particular, the bullet points about working with
iterators.
Part 2b ii: 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:

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.

Next, we will compute the new page rank by simulating
the expected behavior of our web surfers.
First, give every web page a new page rank of \(0.0\).
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 outgoing 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.
Finally, add \(\frac{1  d}{N}\) to 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 outoftheblue.

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 than some
userspecified value \(\epsilon\), we can stop recursing: we say
our page ranks have converged.
(Note: \(\epsilon\) is the Greek lowercase letter "epsilon",
and is traditionally used to represent some sort of very small
number.)
However, if any webpage has a difference greater
than \(\epsilon\), we replace the old page ranks with the
new ones we just computed and repeat step 2.
Final note: the description above is not the most efficient implementation of the PageRank
algorithm. You may combine or rearrange certain steps to improve efficiency, as long as you get
the same (or very similar) results in the end. Also note that an inefficient implementation may
have issues with floating point errors,
as described in part 2a.
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 outgoing 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).
Page A new rank: \(\underbrace{(d \cdot 0.25) / 1}_{\text{from page B}} + \underbrace{(d \cdot 0.25) / 1}_{\text{from page C}} + \underbrace{(d \cdot 0.25) / 1}_{\text{from page D}} + \underbrace{(1  d) / 4}_{\text{new surfers}} = 0.67500\)
Page B new rank: \(\underbrace{(d \cdot 0.25) / 3}_{\text{from page A}} + \underbrace{(1  d) / 4}_{\text{new surfers}} = 0.10833\)
Page C new rank: \(\underbrace{(d \cdot 0.25) / 3}_{\text{from page A}} + \underbrace{(1  d) / 4}_{\text{new surfers}} = 0.10833\)
Page D new rank: \(\underbrace{(d \cdot 0.25) / 3}_{\text{from page A}} + \underbrace{(1  d) / 4}_{\text{new surfers}} = 0.10833\)
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.
Page A new rank: \(\underbrace{(d \cdot 0.10833) / 1}_{\text{from page B}} + \underbrace{(d \cdot 0.10833) / 1}_{\text{from page C}} + \underbrace{(d \cdot 0.10833) / 1}_{\text{from page D}} + \underbrace{(1  d) / 4}_{\text{new surfers}} = 0.31375\)
Page B new rank: \(\underbrace{(d \cdot 0.67500) / 3}_{\text{from page A}} + \underbrace{(1  d) / 4}_{\text{new surfers}} = 0.22875\)
Page C new rank: \(\underbrace{(d \cdot 0.67500) / 3}_{\text{from page A}} + \underbrace{(1  d) / 4}_{\text{new surfers}} = 0.22875\)
Page D new rank: \(\underbrace{(d \cdot 0.67500) / 3}_{\text{from page A}} + \underbrace{(1  d) / 4}_{\text{new surfers}} = 0.22875\)
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 fastforward to iteration 100, our scores basically stop changing
and have settled down to this:
This final result represents our true page rank score.
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?
Here is a more complex example of a graph (which includes a page with no incoming
links).
Here is the result after iteration 1:
Page A new rank: \(
\underbrace{(d \cdot 0.2) / 1}_{\text{from page D}} +
\underbrace{(d \cdot 0.2) / 5}_{\text{from page C}} +
\underbrace{(1  d) / 5}_{\text{new surfers}} = 0.23400\)
Page B new rank: \(
\underbrace{(d \cdot 0.2) / 2}_{\text{from page A}} +
\underbrace{(d \cdot 0.2) / 5}_{\text{from page C}} +
\underbrace{(1  d) / 5}_{\text{new surfers}} = 0.14900\)
Page C new rank: \(
\underbrace{(d \cdot 0.2) / 2}_{\text{from page B}} +
\underbrace{(d \cdot 0.2) / 5}_{\text{from page C}} +
\underbrace{(1  d) / 5}_{\text{new surfers}} = 0.14900\)
Page D new rank: \(
\underbrace{(d \cdot 0.2) / 2}_{\text{from page A}} +
\underbrace{(d \cdot 0.2) / 2}_{\text{from page B}} +
\underbrace{(d \cdot 0.2) / 1}_{\text{from page E}} +
\underbrace{(d \cdot 0.2) / 5}_{\text{from page C}} +
\underbrace{(1  d) / 5}_{\text{new surfers}} = 0.40400\)
Page E new rank: \(
\underbrace{(d \cdot 0.2) / 5}_{\text{from page C}} +
\underbrace{(1  d) / 5}_{\text{new surfers}} = 0.06400\)
After iteration 2:
After iteration 3:
After iteration 100 (the final, converged ranks):
We recommend reading through all three examples before you begin writing code.
Part 2b iii: Rerun your search engine again
Task: Finish implementing PageRank.computePageRank(...)
and rerun your 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 precomputed 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.) The spam pages should now appear
appear several places lower on the page—try typing in "seattle"
and "computer science" again.
Ideally, the spam results would have vanished completely; part of the reason they
don't is that the set of web pages we're looking at is very minimal and
doesn't contain many other pages about Seattle or computer science.
If we had more legitimate pages about either topics, they would have pushed down
the spam results even further.
Of course, there are other limitations to PageRank: we were able to suppress 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 catandmouse.
So, what exactly is happening behind the scenes, mathematically speaking?
Well, to put it succiently, it turns out that what PageRank is really doing is
computing an approximation of the first principal eigenvector of a (diagonalizable)
Markov transition matrix representing the link structure of the internet via the power
method. This eigenvector is in fact exactly the vector we return from the
computePageRank(...)
method.
If you've never taken a linear algebra class before (e.g. Math 308), that
paragraph probably sounded like complete gibberish. That's ok—the punchline
is that you can basically go around telling your friends and family that
you just wrote an algorithm to "compute the eigenvector of the internet" and sound
all fancy and mysterious.
If you're curious and want to learn more, see the following links, which
go into a little more detail into the underlying math:
Part 2b iv: 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 .txt
form.
 Questions about the homework:
 What is your name and your partner's name?
 How was the homework? Did you enjoy it? Whats parts did you enjoy or not enjoy?
 Do you have any suggestions for improving the homework?
 Questions about your partner (skip if you worked solo):
 Which parts of the homework did you work on, and which
parts did your partner program?
 How was your partnership? Do you feel you and your partner
contributed equally to this homework?
Deliverables
The following deliverables are due on Friday March 1 at 11:59pm.
Submit by pushing your code to GitLab. If you intend to submit late, fill out
this late
submission form when you submit.
Before submitting, be sure to doublecheck and make sure that...
Both partners should turn in a .txt
file containing their
answers to the individual writeup on Canvas if you haven't
already. This is due at the same time as the rest of your project.