[Script Info]
Title:
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,0:00:00.00,0:00:03.00,Default,,0000,0000,0000,,Just as a quick aside, if you're familiar with matrix multiplication,
Dialogue: 0,0:00:03.00,0:00:06.00,Default,,0000,0000,0000,,there is a very nice connection between this little algorithm
Dialogue: 0,0:00:06.00,0:00:08.00,Default,,0000,0000,0000,,that we're just working on and matrix multiplication.
Dialogue: 0,0:00:08.00,0:00:11.00,Default,,0000,0000,0000,,To appreciate that, the first thing you need to understand is that
Dialogue: 0,0:00:11.00,0:00:15.00,Default,,0000,0000,0000,,if we can represent a graph on a set of nodes as a matrix
Dialogue: 0,0:00:15.00,0:00:21.00,Default,,0000,0000,0000,,and it's a matrix that consists of all 0s and 1s and if it's a sparse graph, say mostly zeros.
Dialogue: 0,0:00:21.00,0:00:24.00,Default,,0000,0000,0000,,But if there's a link between node I and node J,
Dialogue: 0,0:00:24.00,0:00:30.00,Default,,0000,0000,0000,,then the corresponding position in the matrix has a number in it, number 1.
Dialogue: 0,0:00:30.00,0:00:32.00,Default,,0000,0000,0000,,That 1 there means that there is a link from I to J.
Dialogue: 0,0:00:32.00,0:00:36.00,Default,,0000,0000,0000,,The graphs that we've been talking about links are bidirectional.
Dialogue: 0,0:00:36.00,0:00:41.00,Default,,0000,0000,0000,,So if there's a 1 in this I-J position, then there is also a 1 in the J-I position,
Dialogue: 0,0:00:41.00,0:00:46.00,Default,,0000,0000,0000,,which in this picture seems like it'd be really nearby, which means that this matrix is symmetric,
Dialogue: 0,0:00:46.00,0:00:50.00,Default,,0000,0000,0000,,and I'm not going to get into matrix terminology but again if you're familiar with it,
Dialogue: 0,0:00:50.00,0:00:53.00,Default,,0000,0000,0000,,you'll recognize what a symmetric matrix is.
Dialogue: 0,0:00:53.00,0:00:56.00,Default,,0000,0000,0000,,The matrix equals a its own transpose if you flip things the other way.
Dialogue: 0,0:00:56.00,0:01:00.00,Default,,0000,0000,0000,,So basically it's natural, it means for just interchanging the nodes
Dialogue: 0,0:01:00.00,0:01:03.00,Default,,0000,0000,0000,,since the connections are bidirectional, we'll have the same matrix again.
Dialogue: 0,0:01:03.00,0:01:08.00,Default,,0000,0000,0000,,So let's call this matrix (M) and let's think about what it means to multiply (M) times itself.
Dialogue: 0,0:01:08.00,0:01:13.00,Default,,0000,0000,0000,,In matrix multiplication, the way we fill in the I-J entry of the product,
Dialogue: 0,0:01:13.00,0:01:18.00,Default,,0000,0000,0000,,we take the I row of the first matrix and J column of the second matrix
Dialogue: 0,0:01:18.00,0:01:22.00,Default,,0000,0000,0000,,and I always need two hands whenever I think about matrix multiplication
Dialogue: 0,0:01:22.00,0:01:25.00,Default,,0000,0000,0000,,and you across this one and down this one at the same time.
Dialogue: 0,0:01:25.00,0:01:29.00,Default,,0000,0000,0000,,And what we do in this case since it's all zeros and ones and it's a square matrix,
Dialogue: 0,0:01:29.00,0:01:31.00,Default,,0000,0000,0000,,but what we're going through and figure out.
Dialogue: 0,0:01:31.00,0:01:34.00,Default,,0000,0000,0000,,Anywhere where there is a 0 and 1, and a 0 and the other, it's going to be 0.
Dialogue: 0,0:01:34.00,0:01:38.00,Default,,0000,0000,0000,,Only if there is a 1 in both, is it going to be a product that's not 0.
Dialogue: 0,0:01:38.00,0:01:43.00,Default,,0000,0000,0000,,So this multiplication of this row times this column is exactly a count of the number of 1's
Dialogue: 0,0:01:43.00,0:01:46.00,Default,,0000,0000,0000,,that the two vectors have in exactly the same positions.
Dialogue: 0,0:01:46.00,0:01:49.00,Default,,0000,0000,0000,,What does it mean for them to have a 1 in the same position? Let's check.
Dialogue: 0,0:01:49.00,0:01:53.00,Default,,0000,0000,0000,,Let's imagine that there is a 1 in position K here and at the same time in position K here.
Dialogue: 0,0:01:53.00,0:01:58.00,Default,,0000,0000,0000,,This position here means that our graph had a link from I to K.
Dialogue: 0,0:01:58.00,0:02:00.00,Default,,0000,0000,0000,,There, that's what this means that there's a 1 there.
Dialogue: 0,0:02:00.00,0:02:05.00,Default,,0000,0000,0000,,And similarly, if there's a 1 in this position, it means that very same graph that we're talking about
Dialogue: 0,0:02:05.00,0:02:09.00,Default,,0000,0000,0000,,this graph that (M) is representing also has a link from K to J
Dialogue: 0,0:02:09.00,0:02:13.00,Default,,0000,0000,0000,,and what we're doing is counting up all the Ks that have the property
Dialogue: 0,0:02:13.00,0:02:17.00,Default,,0000,0000,0000,,that they would take as you can get from I to one of those and then to J from one of those.
Dialogue: 0,0:02:17.00,0:02:21.00,Default,,0000,0000,0000,,It's going to add all those up. That's exactly what matrix multiplication does.
Dialogue: 0,0:02:21.00,0:02:29.00,Default,,0000,0000,0000,,This value here is going to be filled in with precisely the number of 2-step path from I to J
Dialogue: 0,0:02:29.00,0:02:32.00,Default,,0000,0000,0000,,which is exactly what we needed in that other example hat we're basically counting up
Dialogue: 0,0:02:32.00,0:02:37.00,Default,,0000,0000,0000,,the comic books that are uncommon between some character I and some character J.
Dialogue: 0,0:02:37.00,0:02:41.00,Default,,0000,0000,0000,,In the case of the bipartite graph of the Marvel comic book characters,
Dialogue: 0,0:02:41.00,0:02:47.00,Default,,0000,0000,0000,,any 2-step path that starts at a character goes through a comic book and then a character.
Dialogue: 0,0:02:47.00,0:02:51.00,Default,,0000,0000,0000,,So this is counting up exactly the number of comic books that I and J are both in.
Dialogue: 0,0:02:51.00,0:02:54.00,Default,,0000,0000,0000,,There we go, the square of the matrix which represents
Dialogue: 0,0:02:54.00,0:02:56.00,Default,,0000,0000,0000,,the connections of the graph actually gives us the same answer.
Dialogue: 0,0:02:56.00,0:02:59.00,Default,,0000,0000,0000,,The running time of this algorithm, of course, is n³,
Dialogue: 0,0:02:59.00,0:03:03.00,Default,,0000,0000,0000,,because we're looping through for each of the entries of this matrix that we're going to fill in
Dialogue: 0,0:03:03.00,0:03:07.00,Default,,0000,0000,0000,,and there's n² to them, we're doing this row by column multiplication which also takes time in.
Dialogue: 0,0:03:07.00,0:03:11.00,Default,,0000,0000,0000,,So it's in cubed. The algorithm that we've just been talking about.
Dialogue: 0,0:03:11.00,0:03:15.00,Default,,0000,0000,0000,,Something more like number edges times the number of nodes.
Dialogue: 0,0:03:15.00,0:03:18.00,Default,,0000,0000,0000,,The number of edges here comes from the fact that we loop over
Dialogue: 0,0:03:18.00,0:03:22.00,Default,,0000,0000,0000,,each of the character book combinations that we have stored explicitly.
Dialogue: 0,0:03:22.00,0:03:25.00,Default,,0000,0000,0000,,And then for each of those, we examined which characters are there connected to it.
Dialogue: 0,0:03:25.00,0:03:31.00,Default,,0000,0000,0000,,It could be as bad as N*M. If (M) is dense matrix, then this is (N)²,
Dialogue: 0,0:03:31.00,0:03:36.00,Default,,0000,0000,0000,,so this algorithm ended up being in cubed again, but if it's a sparse matrix,
Dialogue: 0,0:03:36.00,0:03:38.00,Default,,0000,0000,0000,,so the number of edges is linear like in a planar graph, for example,
Dialogue: 0,0:03:38.00,0:03:41.00,Default,,0000,0000,0000,,then this is (N)² which is actually a lot better.