WEBVTT
NOTE Paragraph
00:00:00.000 --> 00:00:03.000
Just as a quick aside, if you're familiar with matrix multiplication,
00:00:03.000 --> 00:00:06.000
there is a very nice connection between this little algorithm
00:00:06.000 --> 00:00:08.000
that we're just working on and matrix multiplication.
00:00:08.000 --> 00:00:11.000
To appreciate that, the first thing you need to understand is that
00:00:11.000 --> 00:00:15.000
if we can represent a graph on a set of nodes as a matrix
00:00:15.000 --> 00:00:21.000
and it's a matrix that consists of all 0s and 1s and if it's a sparse graph, say mostly zeros.
00:00:21.000 --> 00:00:24.000
But if there's a link between node I and node J,
00:00:24.000 --> 00:00:30.000
then the corresponding position in the matrix has a number in it, number 1.
00:00:30.000 --> 00:00:32.000
That 1 there means that there is a link from I to J.
00:00:32.000 --> 00:00:36.000
The graphs that we've been talking about links are bidirectional.
00:00:36.000 --> 00:00:41.000
So if there's a 1 in this I-J position, then there is also a 1 in the J-I position,
00:00:41.000 --> 00:00:46.000
which in this picture seems like it'd be really nearby, which means that this matrix is symmetric,
00:00:46.000 --> 00:00:50.000
and I'm not going to get into matrix terminology but again if you're familiar with it,
00:00:50.000 --> 00:00:53.000
you'll recognize what a symmetric matrix is.
00:00:53.000 --> 00:00:56.000
The matrix equals a its own transpose if you flip things the other way.
00:00:56.000 --> 00:01:00.000
So basically it's natural, it means for just interchanging the nodes
00:01:00.000 --> 00:01:03.000
since the connections are bidirectional, we'll have the same matrix again.
00:01:03.000 --> 00:01:08.000
So let's call this matrix (M) and let's think about what it means to multiply (M) times itself.
00:01:08.000 --> 00:01:13.000
In matrix multiplication, the way we fill in the I-J entry of the product,
00:01:13.000 --> 00:01:18.000
we take the I row of the first matrix and J column of the second matrix
00:01:18.000 --> 00:01:22.000
and I always need two hands whenever I think about matrix multiplication
00:01:22.000 --> 00:01:25.000
and you across this one and down this one at the same time.
00:01:25.000 --> 00:01:29.000
And what we do in this case since it's all zeros and ones and it's a square matrix,
00:01:29.000 --> 00:01:31.000
but what we're going through and figure out.
00:01:31.000 --> 00:01:34.000
Anywhere where there is a 0 and 1, and a 0 and the other, it's going to be 0.
00:01:34.000 --> 00:01:38.000
Only if there is a 1 in both, is it going to be a product that's not 0.
00:01:38.000 --> 00:01:43.000
So this multiplication of this row times this column is exactly a count of the number of 1's
00:01:43.000 --> 00:01:46.000
that the two vectors have in exactly the same positions.
00:01:46.000 --> 00:01:49.000
What does it mean for them to have a 1 in the same position? Let's check.
00:01:49.000 --> 00:01:53.000
Let's imagine that there is a 1 in position K here and at the same time in position K here.
00:01:53.000 --> 00:01:58.000
This position here means that our graph had a link from I to K.
00:01:58.000 --> 00:02:00.000
There, that's what this means that there's a 1 there.
00:02:00.000 --> 00:02:05.000
And similarly, if there's a 1 in this position, it means that very same graph that we're talking about
00:02:05.000 --> 00:02:09.000
this graph that (M) is representing also has a link from K to J
00:02:09.000 --> 00:02:13.000
and what we're doing is counting up all the Ks that have the property
00:02:13.000 --> 00:02:17.000
that they would take as you can get from I to one of those and then to J from one of those.
00:02:17.000 --> 00:02:21.000
It's going to add all those up. That's exactly what matrix multiplication does.
00:02:21.000 --> 00:02:29.000
This value here is going to be filled in with precisely the number of 2-step path from I to J
00:02:29.000 --> 00:02:32.000
which is exactly what we needed in that other example hat we're basically counting up
00:02:32.000 --> 00:02:37.000
the comic books that are uncommon between some character I and some character J.
00:02:37.000 --> 00:02:41.000
In the case of the bipartite graph of the Marvel comic book characters,
00:02:41.000 --> 00:02:47.000
any 2-step path that starts at a character goes through a comic book and then a character.
00:02:47.000 --> 00:02:51.000
So this is counting up exactly the number of comic books that I and J are both in.
00:02:51.000 --> 00:02:54.000
There we go, the square of the matrix which represents
00:02:54.000 --> 00:02:56.000
the connections of the graph actually gives us the same answer.
00:02:56.000 --> 00:02:59.000
The running time of this algorithm, of course, is n³,
00:02:59.000 --> 00:03:03.000
because we're looping through for each of the entries of this matrix that we're going to fill in
00:03:03.000 --> 00:03:07.000
and there's n² to them, we're doing this row by column multiplication which also takes time in.
00:03:07.000 --> 00:03:11.000
So it's in cubed. The algorithm that we've just been talking about.
00:03:11.000 --> 00:03:15.000
Something more like number edges times the number of nodes.
00:03:15.000 --> 00:03:18.000
The number of edges here comes from the fact that we loop over
00:03:18.000 --> 00:03:22.000
each of the character book combinations that we have stored explicitly.
00:03:22.000 --> 00:03:25.000
And then for each of those, we examined which characters are there connected to it.
00:03:25.000 --> 00:03:31.000
It could be as bad as N*M. If (M) is dense matrix, then this is (N)²,
00:03:31.000 --> 00:03:36.000
so this algorithm ended up being in cubed again, but if it's a sparse matrix,
00:03:36.000 --> 00:03:38.000
so the number of edges is linear like in a planar graph, for example,
00:03:38.000 --> 00:03:41.000
then this is (N)² which is actually a lot better.