So the way that Google chose to explain the page rank concept was in terms of

what they call The Random Surfer. And The Random Surfer as it says surfs

the web at random and goes to random pages.

But there's a specific way that he does it in order to quantify the importance

score of each of these pages, which we'll look at.

But just conceptually right now, just to see what we mean.

and this graph on the right hand side, we have eight nodes.

And so suppose we're starting off at page A, right, and when we're on page A, we're

facing the decision. We have to click on one of the hyperlinks

on page A, right. So we can either go to B, we can go to E,

or we can go to D. So we choose one randomly.

We have a 1 3rd chance of each, because we're choosing randomly, and there's

three of them. And that brings us right down to page D.

And so, then, now we're on page D and then, again, we have to choose randomly

again. So we choose, well, we say there's a

third of a chance of each of these 1, 2, 3 and so we go over to page eight.

And then, now we're on page E. And then now, once were on e, then we say

maybe the person is bored, right? So maybe the person decided that he was

bored, and he didn't like what he was reading, and so he goes and enters a

random URL into his browser, www.something.com.

And so, now this action is just a random Not surfing, because he's not really

surfing and clicking on links, but is just a random entry of a URL.

So he's going to just end up somewhere else in the connectivity.

So he ends up on F. And so, this one actually that he just

made now did not follow the connectivity of the webgraph, but it's still an action

that we take into account within the random surfer.

And so -- and then, when he's on F again, he chooses one of the two hyperlinks, and

he decides to go to G and so on. So just to summarize, with the Random

Surfer, we define two possible actions. The first is to pick a hyperlink randomly

from the current page, right, so this is how we want to go next.

You can pick a hyperlink randomly from the current page, and that's this whole 1

3rd, 1 3rd, 1 3rd, business we were talking about, were you just choose one

where you go next, and the second is to enter a URL into the browser randomly.

And those are two actions. This one follows the connectivity, and

this one doesn't follow. And so, you can see already how This kind

of takes into account the importance of the lengths here because the lengths

which are coming from nodes, which themselves are more important are going

to get visited more often and going to be used more often.

And so the question that pagerank asks is what is the chance that a page is going

to be selected at any time? So, if we keep surfing over and over and

over and over and over again, how many fractions of the total number of searches

is each page going to get? Which ones are going to be visited more

frequently and we say those are the more important.

So what is the chance a page is selected at any time?

And that's the idea behind PageRank. So again now, the ones that are going to

get visited the more often are the ones that have links that are more likely to

be chosen. And the ones that have links that are

more likely to be chosen are in terms going to be from nodes that are visited

more often. So you can see sort of the logic that

keeps circling here. That important is dependent upon the

importance of the links, which is dependent upon the importance of the

nodes, which is then dependent upon the importantance of the links, and so on and

it gets kind of complicated. So we keep going back.

And, but, we'll see how we can quantify that pretty simply, just to see what the

importance scores mean and how the represented.

So, now let's talk a little more about the importance score.

Let's ignore the idea and the random surfing of getting bored for now, okay.

And we'll return back to our initial example with four nodes which we just ran

an in-degree version of importance on before.

And so Each node, we're going to say, has it's own importance score.

Okay. So, they have their importance score and

we can make, use lower letters for that. So, for big W we'll say the importance

score is w, or little w. For X, we'll say the importance score is

little x. For Y, we'll say it's little y.

And for Z, we'll say it's little z. And so now we have to figure out what are

the chances that each of these links are going to be visited.

So it's very simple, is that if we're on node W, okay, we only have two choices,

okay? If we ignore the idea of getting bored

and surfing randomly, okay for R and W we're going to follow the connectivity of

the web graph. I'm going to make that assumption.

So, we have to choose one of the two links.

We either choose this link or we choose this link.

Each of them is going to clearly have one half of a chance because there's two.

Right? So, it's like flipping a coin.

Just choose one of the two. [NOISE] Similarly for if we're already on

Node y for instance, y only has one outgoing link.

So, it's only one choice that you have to go to z next.

So, this is actually a chance of one. But now as we said we want to figure out

how important the links are and that's going to depend upon how important the

node is itself. Okay.

So, we in a sense need each of these nodes to be spreading their importance

score to this link. So, it should make sense then that we

should multiply this by w and say well this link is one half w.

This other link right here is also one half w.

And in that way then we can look at this much easier and say, okay when, when

we're at W. W.

starts with an importance score of W. Then this link is half of W, one-half W.

This other link is another half of W, because there's two of them.

So W gets divided by 2, and we say it spreads its score to those two links.

And similarly, for Y there's only one link right here, so all of Y's importance

gets put off on this one link. Okay.

And so the reason is first we're splitting half and half on each of the

links, and second is that we have to wait by the importance in the first place,

because that's how important the node is itself.

So, the more important node W is, then you see the higher the importance of each

of these links will be. So if W is an very important node then

that will mean a link from W will be Very important, you see, that's why there's

this w factor in here, which take care of that, of weighing the importance of the

nodes on the links themselves. So as we said, each node has its own

importance score and this spreads an equal amount of importance to each

outgoing link. And so we can also say that that's

related to the out-degree of a node. So we talked before about the in-degree,

which was the number of incoming links, and we used that as a measure of

importance. But now we're actually using the

out-degree as well and we're saying that basically we're dividing in each length

Gets a fraction of the out degree, right, because if the out degree is three then

each length gets a third, if the out degree is four then each length gets a

fourth of the important square of the node and so on, so it's just a way of

looking at it. This out degree of W right here is two,

so each of these gets one half. The out degree of y is one, so each of

these gets one... The out-degree of x is 2.

So each of these would get 1/2 x. 1/2 x.

We can right those equations. Now the out-degree of z is 3.

Cause z gets divided three times. So each of these is 1/3.

We have 1/3 z here, 1/3 z here, and 1/3 z here.

Now notice that if you add What's outgoing, you will get this importance

score in the beginning, and that's, again, the idea of spreading.

This is one-thirdsy, two-thirdsy, onesy, if we add all those up.

One half plus one half is one. One half plus one half is one.

One is just equal to one. 'Kay so that's what that whole

conservation principle, that we're only spreading the amount of importance.

Each node is only spreading the amount of importance that it has to begin with.

The "Random Surfer"

Networks Illustrated: Principles without Calculus

与讲师见面