What makes WiFi faster at home than at a coffee shop? How does Google order its search results from the trillions of webpages on the Internet? Why does Verizon charge $15 for every GB of data we use? Is it really true that we are connected in six social steps or less? These are just a few of the many intriguing questions we can ask about the social and technical networks that form integral parts of our daily lives. This course is about exploring the answers, using a language that anyone can understand. We will focus on fundamental principles like “sharing is hard”, “crowds are wise”, and “network of networks” that have guided the design and sustainability of today’s networks, and summarize the theories behind everything from the social connections we make on platforms like Facebook to the technology upon which these websites run. Unlike other networking courses, the mathematics included here are no more complicated than adding and multiplying numbers. While mathematical details are necessary to fully specify the algorithms and systems we investigate, they are not required to understand the main ideas. We use illustrations, analogies, and anecdotes about networks as pedagogical tools in lieu of detailed equations. Please note that per Princeton University policy, no certificates, credentials or reports are awarded in connection with this course.
PageRank Example Calculation
Loading...
From the course by Princeton University
Networks Illustrated: Principles without Calculus
40 ratings
From the lesson
PageRank by Google
In this lesson, we will take a look at PageRank, Google's famous algorithm for ordering the results on its search page. PageRank is a prime example of how coming up with the right "ranking" of a set of items is a difficult yet important question in networking.
Meet the Instructors
Christopher BrintonLecturer
Electrical Engineering
Mung ChiangProfessor
Electrical Engineering
So now, we'll run through the calculation for the importance score, so you had to
go about that. And you'll see it's, it's very
mechanized. So, you can use this and you can you can
do this for basically any web graph that you're given and follow kind of the same
procedure and it'll all work out. so this, here's our web graph over here
again. We've noted the links accordingly, with
their values. For instance, w over 2, z over 3, and so
on, the spreading of the important scores.
And we'll tabulate our equations that we just got in the last video over here
because we'll need them to solve for the important scores.
Because these equations give the relationship amongst the different
important scores. And so, one thing you'll notice right
here is that we have 4 equations, right? So, we have 4 equations, one per node.
We went W, and then we went to x, and then we went to y, and then we went to z.
And we got one equation each and we have 4 unknowns.
Which are the important scores, w, x, y, and z, as you said before.
And so, you'll probably remember from an Algebra class or something, we have one
equation and one unknown. And then, you can solve for that unknown.
So, for instance, if you had 2x plus 3 is equal to 5, right.
And you could say that 2x is equal to 2, and then that would mean that x is equal
to 1. So, and then if you have two equations,
and two unknowns that's okay also. So, when you have two unknowns, you need
two equations right because need two, two equations in order to solve for any one
of those variables. Then for three unknowns, you need three
equations, and for four unknowns, you need four equations, five unknowns you
need five equations, and so on. You need the number of unknowns and the
number of equations to be the same if you want to have a unique solution.
So, to make things a little easier, we're going to look at what each of these
important scores represents. So, you remember what we said before,
that they're really probabilities. And so, each of these w, x, y, and z is
each the probability that at any given time you're going to be on one of those
nodes. And we said that the higher that chance
is, the more important the page is, and so on.
Well, things about probability is first of all they have to always be between
zero and one, zero meaning it will never happen, 100%.
Or 1, meaning that it's certain to happen.
So, if you add up w, x, y and z, that has to be equal to 1 because logically
speaking you have to be on one of the nodes at any given time.
So, they have to add to one because you are 100% certain that you will be on
either w or x or y or z at any given time.
So, we can make things easier by knowing that these probabilities must sum to 1.
And so, we can say that w plus x plus y plus z must be equal to 1.
So now, you're probably wondering, well, now we have five equations, right.
And that might be problematic because we only have four unknowns.
Not saying that we couldn't do it because as it turns out you could still solve
this using the five equations, as we will technically do.
But we won't make use of each of the five equations when we do it.
But basically you only need four equations at any given time to relate
these variables to one another, but this equation is much easier to use.
And easier to look at than, for instance, this equation right here.
This equation's a little more complicated, we have a lot of divisions
and things along those sorts. So, this normalization equation is much
easier to use, so we'll stick with that for now, and we, we will not use this
equation. We could have also not used this one, or
this one, or this one, but these are easier to look at because they don't
relate all the variables at once. All right, this one only relates two,
this one relates three, this only also relates three.
This one relates all four of them, so we use this equation with this equation,
this equation and this equation. Second is that we have to choose one of
the important scores as a reference. So, we don't have to, but it's just
easier to do that, to choose one of them as a reference.
And the one that we want to choose as a reference is going to be the one that we
can then go ahead and plug into this equation.
So, then we can say suppose we got everything in y, then we have some
function of y some function of y some function of y equals 1.
Then, we can plug that in, and then solve for y, right?
And then, everything else would fall out of it.
So, let's first look at these equations, these three equations right here and see
which of the variables would be the easiest to work with as our reference.
So, let's use z as our reference here, because we can pretty easily get
everything in terms of z, right? We already have w in terms of z.
Then, we can get x in terms of z because we'll have w in terms of z.
And then, we can also get y in terms of z using this last equation.
So, that'll be probably the least tedious path now.
Again, you could choose any one of them and it won't matter.
It's just, we're trying to make the math as simple as possible here because we
don't want to deal with heavy math. So, we'll choose our reference value to
be z. So, to start off, then we'll go w, x, and
then y, and try to get them all in terms of z.
So, for w, we'll just use the first equation.
We already know that w is equal to z over 3.
So, that's easy because then, when we plug in here, we just have w equal z over
3, so we're done with that for now. Now, let's move onto x.
Now, we want to get x in terms of z. So, we have x equals w over 2 plus z over
3. So now, we already have w in terms of z,
though. We know that w is equal to z over 3.
So, we can say that x is equal to w over 2 plus z over 3.
Which is equal to, and then on this side, this w term over here is z over 3,
divided by 2, because this is just equal to z over 3, plus z over 3 again.
That's z over 6 plus z over 3. And then, if we, we can, for instance,
make each of them common a denominators. So that we have z over 6 plus 2z over 6,
which is then 3z over 6 which is equal to z over 2, 1 half z.
So, we have w equals z over 3 and x is equal to z over 2.
So, you can already tell them now that since z is between 0 and 1 that x is
going to have a higher importance score than w because w is just 1 3rd of z
whereas x is only 1 half of z. Now, we can move onto y.
So, rather than using, again, this equation where we'd have to plug in
everything for w and even x. Why don't we just work with this equation
down here because we already have and we can say that y is equal to z minus x over
2. So, we'll say y is equal to z minus x
over 2. Right because we already have y on this
side, so we can just subtract x over 2 from both sides.
And then, we have x as before, z over 2. So, this is z minus z over 2, over 2,
which is z minus z over 4, which is just 3z over four, 3 4ths z.
Now, I have that y is equal to 3z over 4. So, notice a few things.
First of all is that we chose each of these three equations up here to get w, x
and y in terms of the reference variable z.
And now, we have those three relationships that we need in order to
plug back into this equation. And then, we can solve for z using one
equation and one unknown which is the basis for everything here.
And also, notice that we chose the simplest equation to work with first,
right. Simply that w is equal to z over 3.
We didn't have to do any substitution or anything in that equation.
And then, we moved on to the more complicated equations.
And everything kind of fell out. And we used what we had before to solve
for what we needed to do at the present. So, that's the way to go about this, is
that you sort of, unlock different pieces of the puzzle, so to speak, as you go on.
And then, you use what you've unlocked in terms of what variables you've already
gotten in terms of z to keep moving forward in the process.
So, moving along then, we can tabulate our equations again.
Now, we'll just have it at the reference equations because those are much easier
to work with. And z equals z obviously, so plugging in,
we can solve for z. So, remember we had w plus x plus y plus
z equals 1. Now, w is z over 3, so we have z over 3,
plus x which is z over 2, plus y which is 3z over 4, plus z has to be equal to 1.
So now, we need to find a common denominator in order to be able to solve
for z easily or we can use the calculator to, it's either way it's fine, but just
just to illustrate this here. the first common denominator we get would
be 12, right? Because 4 goes into 12, 2 goes into 12, 3
also goes into 12 and obviously one goes into twelve.
So then, we have to take 3 times 4 to be 12.
So, we have 4z over 12 over here, plus then 6z, because 6 times 2 is 12 over 12
plus, you know we multiply this by 3 and we get 9z over 12 plus 12z over 12.
Has to be equal to 1. Right, so then, adding this up, 4 plus 6
plus 9 plus 12 is 31. So, we have 31z over 12 has to be equal
to 1. Which then means that z is equal to 12
over 31, which is equal to 0.387. It's easier to look at these in decimals,
because then we can more easily compare them.
So, now that we've solved for z, everything else will just fall out easily
because we already have w, x, and y in terms of z from our reference equations
right up here. So, we can backtrack for the rest.
We get w is equal to z over 3, which is equal to 12 over 31 divided by 3, which
is just 4 over 31 which is 0.129. We have x equals z over 2.
Which is 6 over 31. Which is 0.258.
And we have y equals 3z over 4, which is, which is 9 over 31, which is 0.290.
So now, we can easily rank these. We see that z is the most important with
0.387, followed by y, then followed by x and then followed by w.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
