So let's see if we can take what we just did and apply it to actually computing
some of these important scores. Or coming up with a way to equate the
important scores to one another. So if we consider our graph again, let's
just write down what we had before in terms of spreading the scores.
We saw before this link would have been W over 2.
This one also W over 2, Z, since there's three links, each one's Z over 3, Z over
3 and Z over 3. X gets X over 2, because there's two
links, the outgoing, out degrees two. And Y gets just one, because there's only
one outgoing link, just Y. And this is a really good way to
visualize it by the way, because then you can see how each of them have to sum to
one. Our [LAUGH], [INAUDIBLE] have to sum up
to the importance of the nodes, so this is W, again, this is X , this is Y and
this is Z. So, these, each of the outgoing degrees
sum to the incoming one. And so now, what you have to also realize
is that, we just said how each of these nodes spreads their importance scores.
But now we can write each node's score in terms of the scores on its incoming
links. So the idea behind page rank is that we
should be able to write each of these important scores at node x in terms of
what's coming into it. So that's going to define how important
it is. Something coming from W, something coming
from Z and the exact values that we use are the W over 2 value here.
Because that's the importance that W spreads on to its link, and Z over 3,
because that's the importance that Z spreads onto this link.
So we just write an equation at each node in terms of the incoming lengths.
So, for X, we can get that X equals W over 2, plus Z over 3, right?
Because when you, if you start at W, the only way you can, because the only way
you can get to X is by either being on W or Z if we're neglecting the idea of
surfing randomly right now. And if you're on w, there's a w over two
chance then that you're going to come to x because it splits half and half.
And if you're on z, there's a Z over 3 chance you're going to come to X, because
it splits in, into thirds. Now let's try to write the equation for
node W, and w's important score. W can only get, you can only get to w in
one step, at least, if you come from z, right?
So, W then has to be equal to Z over 3, because when you're on Z, there's a
third, only a third of a chance of getting over to W.
So, we say that, W is equal to Z over 3. Now we did w and X, let's do Y.
Now Y has three incoming lengths. Okay, because we said before it has an n
degree of 3 and that's why before at least we thought it was the most
important node with the N degree. So you can get to y if you're on W, X or
Z. So coming from W there's half of a chance
so we say that Y equals W over 2 plus then coming from X there's also half a
chance plus X over 2. Then coming from Z there's a third of a
chance, so we say plus Z over 3. And then now if we look at from Z's
perspective, Z being the last node over here.
From Z we can only get to it from either Y or X.
So, from Y it's actually guaranteed, if you're following hyperlink.
It's the only, Y is only out degree is only to Z.
So, Y only points to Z. So Z is equal to Y plus, and then from X
it's half, so plus X over 2. So these equations right here, you can
say that they are all dependent on each other, right?
X is dependent upon W, W is dependent upon Z, Z is dependent upon X in turn, Y
is dependent upon w, x, and z and so on. And so this whole idea of X being
dependent upon w, which is then dependent upon Z, which then dependent X, and so on
as a circle. That's the idea of recursion.
It's seemingly circular logic, but it turns out that we can actually solve if
we take all these equations together. We can actually solve for one solution of
the equations. guaranteed to provide that we make some
assumptions about how the equations are built, we'll look at that too, a little
bit. But if we can come up with a solution to
these equation, that's going to give us the page rank solution.
And each page's page rank importance. So we have to come up with values of W,
X, Y and Z. That will satisfy each of these equations
at the same time. Now when you solve a system of equations,
there's two, there's three possibilities. The first possibilities are there's no
solution. So there may not be values of X, W, Y,
and Z that can solve each of these four, say one, two, three, four.
There may not be values that can do it. The second is that there's a unique
solution [SOUND]. And unique means that there's only one.
There's one unique way of doing it. We could pick, we could find one value of
W, X, Y and Z at the same time that will work for all these.
And the third one is at, there's multiple solutions, so we'll write this, multiple.
So we want to make it so that we have a unique solution.
And as we'll see there is a unique solution to this set of equations it
turns out. But we're going to have to make a few
modifications in the end of this, as you'll see, in order to guarantee that
there's not either multiple solutions or no solution.
Christopher BrintonLecturer
Mung ChiangProfessor
