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.

Â