So we're going to provide a start on this code
and then we'll leave the crucial part of it
for you to do, as a quiz.
You should feel free, at any point,
to stop and try to figure out more of the code on your own.
There are lots of different ways to do this
and we'll show you one--
and you'll finish that as a quiz.
So the first thing we're going to do is define 2 constants.
So we're going to use "d" as the damping factor.
And I'll use 0.8 as my damping factor.
That's the probability, thinking about our random Web surfer--
that she selects the link on the current page,
rather than starting over with a new random page.
The other constant I'm going to define here,
we'll call "numloops".
That's the number of times we're going to go through the relaxation.
What we're computing is the value of rank
at some time step.
The number of times we go through that
is going to determine the accuracy of our ranks.
We'll use 10 as the number of loops.
You can experiment with changing that
and one of the questions in the homework assignment
will ask you to think about what happens when you change that.
So now we need to start--we said, initially,
the rank of each URL is 1 divided by the number of pages.
and so the dictionary ranks,
we want to initialize with those values.
So we're going to create and empty dictionary--we'll call it ranks.
The number of pages--the number of pages, we can get from the graph.
The graph has a dictionary of nodes
and len(graph) will tell us the number of entries in that dictionary.
So that's the number of nodes in the graph,
which is the number of pages that we crawled.
And now we want to go through the pages,
initializing each page to the value, 1.0 / npages.
And I'm remembering to use 1.0 here,
to make sure the division is done as floating point division
and we get an accurate number,
rather than integer division.
So now we've initialized the ranks.
We have a dictionary that maps each page to its current rank,
which is the 1.0 / npages.
So now we get to the interesting part.
We need a loop
that's going to go through
the number of times of numloops.
Each time through this loop what we want to do
is update the newranks,
based on this formula--using the oldranks.
And then, at the end of the loop, we're going to make
the variable ranks hold what was previously newranks--
and that way we can keep going.
Each time, we're going to get a new value for newranks.
At the end of doing all the updates
we're going to update ranks to refer to whatever newranks did.
So that means, each time through this loop,
we're going to create a new dictionary, called newranks,
that starts as empty
and we're going to add all the pages to newranks
as we update their rank.
So to do that, we need to go through the pages in the graph,
and for each page, what we want to do is compute
the newrank for that page.
And the first thing we'll do is this part--
The newrank is: (1 - d) / npages plus this summation.
So the first thing we'll do is introduce a new variable.
We'll call it newrank, and we'll assign it to this value.
Then we're going to update it, as we go through
the pages that link into this page.
So we'll start by initializing newrank as (1 -d) / npages.
So then what we need to do is update for the summation.
And I'm going to leave this blank, and I'm going to skip that for now.
This is going to be left, as a quiz.
We'll finish the rest of the code,
and then your quiz will be to finish this part of the code,
which is really the most interesting part of computing the Page Ranks.
Once we've done that--so we use newrank as our variable
to keep track of the rank for this page.
But we want to update our dictionary
so we're going to add an entry, newranks.
We're still within the foreloop--you're going to
put your code that sums up all the links here.
Once we've done that,
we've got the value of newrank that reflects both
the probability of starting from that page
and the popularity, from all the inlinks.
And so we'll update this to be newrank.
We've added that to our dictionary.
So once we've finished looping through all the pages in the graph--
well now we're ready for the next step.
So that means we want to make the variable, ranks,
refer to the newranks--
so we've changed the time step to the next time step.
And now we're going to go back through this loop.
And we go through this loop the number of loops times.
Each time, we're updating the ranks and when we're done,
what we want to return is ranks--that's the dictionary that maps each page to its rank.