0:00

We mentioned that there are two issues; two enhancements,

therefore, we'll provide to this matrix H. The first one goes back to the problem we

just briefly alluded to that, what if a node, say node four here, does not point

to any other nodes? It's got in degree of three, but out

degree of zero. So, O4 is zero, then what?

Well, you can't divide by zero and this presents a conceptual and a mathematical

challenge. For example, in this 4-node small graph,

we can write down the H matrix four by four very easily.

The first node points to the fourth node only, so it's zero, zero, zero, one.

The second node points to nodes one, three, and four, so out degree is three.

And on columns one, three and four, we write down one over three, one over three,

one over three. No self loop, that's zero.

Node three is one over three, one over three, zero, one over three.

So far so good. Node four, and that's the problematic one.

It's all zero. So, if we solve the linear equation associated with

this pi transpose equals pi transpose H, that means we have to solve

the following equations, one over three times pi two plus pi three equals pi one.

2:07

So, how can we solve this dangling node problem?

We refer to these nodes with no out degrees, or out degree being zero, as

dangling nodes. One possible solution is to say, well,

since you don't point to any other nodes, I will assume that you point to all nodes.

I will force you through a mandatory score spreading.

You have to spread your importance score and since you don't tell me which ones you

point to, I'm going to say, you point to all nodes, okay?

Either all the N minus one nodes, or for simplicity let's say, all the N nodes

including yourself, the self loop. For example, in the last graph here,

instead of this zero, zero, zero, zero, we'll say, it must be one fourth, one

fourth, one fourth, one fourth. Now, here's a shorthand notation to denote

this action of forced importance score spreading to all the nodes.

What we saw is that, we basically say that there is one over four times one, one,

one, one, okay? This is a vector of ones so we write it as

a bold face one, a vector one. Since, by convention of this

research field, I have to flip it over, so this is a row vector, okay?

So, it's one over N, this one-fourth here, times row vector of all ones, okay?

This is what we want to use but only for the dangling nodes.

So, I'll have to identify the dangling nodes.

In this case, the dangling node with a binary indicator is the last ones, the

fourth node. So, we write down one here in a four by

one vector. It's the indicator of all the dangling

nodes. If nodes one, two and three are not

dangling, dangling nodes, we'll just write down zero.

If it is a dangling node, we write down one.

And now, we can look at an outer product between this column vector and this row

vector, okay? Usually, when we write down two vectors

multiplying, a transpose b, we mean inner product, okay?

So, this column vector flipped, therefore it's one by N, and b is N by one column

vector, so the inner product is a scalar, one by one.

But in this case, we're talking about a column vector producting with a row

vector, not the other way around. So, we actually end up with a four by four

matrix. It's a little funny operation, but soon

you'll get used to this shorthand notation. In this four by four matrix, the first

entry is simply this times this. So, that's zero times one was still zero.

And then, you can see that this whole thing would be zero.

Similarly this second row is all zero, third row, all zero.

That's because, in this outer product, the indicator vector's first three entries all zeros,

so it doesn't matter what you have over there.

The last one is one times one fourth, one times one fourth, and so on.

So, you got, exactly what you want. Again, this is just the short hand matrix

notation. And we call this indicator function,

vector w, this vector is just one. So, we have w multiply one transpose, and

don't forget to normalize by the number of webpages one over N.

6:23

What this addition does is exactly take out all those all zero rows and substitute

with one over N over there. Again, the notation may take a little

getting used to but once that's done, you can easily see what's going on here.

Now, H is a very big matrix and this is also a very big matrix but this

actually is a simple matrix, forget about the scaling.

This is basically the same. I'm just putting down a bunch of ones in

certain rows, those rows that are indicated as dangling nodes.

And this, in particular, is called a rank one matrix.

So, we're adding a rank one matrix here which is simply a duplication of one, one,

one, one, one vectors to a very large but sparse matrix H.

So, sparsity helps and this low rank also helps cuz we can see the structures

embedded in this large matrix. We call this new matrix our second matrix,

give it a symbol H hat. And we can model this as so-called random

walk on a graph. Why?

Because once we've done this, there'll be no rows that are all zeros.

And by this normalization, we know all the rows will add up to one.

So, in the H hat matrix, we can view each row as a probability distribution.

8:06

This says, if you're on a certain page, what's the chance that you'll be going to

the other pages? Well, if there are hyperlinks, then you'll

be evenly likely go to any of the hyperlinked pages.

If there is none, then you'll be evenly likely to just terminate this and hop to

any of the pages out there. Now, is this a reasonable model, this

random walk on graph a reasonable model? Well, that depends on what you want to

model. If you try to model a lot of things, the

so called follows Markov chain structure, then sometimes it's pretty good.

In the case of navigating on the web, clearly, people don't exactly do uniformly

picking one of the hyperlinked text. It's a gross simplification but

nonetheless, this random walk on graph following this particular structure

represented by H hat matrix turns out to be a reasonable trade off between

realism and tractability.