1 23:59:59,952 --> 00:00:05,618 [MUSIC]. 2 00:00:05,618 --> 00:00:08,023 So what are some more sophisticated structural analytics tasks we can do with 3 00:00:08,023 --> 00:00:10,836 a graph? Well, one is to the find diameter of the 4 00:00:10,836 --> 00:00:13,622 graph. So this is the longest of all the 5 00:00:13,622 --> 00:00:16,375 shortest paths in the graph. So what's the shortest path? 6 00:00:16,375 --> 00:00:19,714 Well, given an x, well, given a vertex x and a vertex y, find all the different 7 00:00:19,714 --> 00:00:23,870 ways of reaching y from x and take the shortest one of those. 8 00:00:23,870 --> 00:00:26,580 That's the shortest path. Now, do that again, for all possible 9 00:00:26,580 --> 00:00:30,168 pairs of vertices in the graphs. The longest of all those shortest paths 10 00:00:30,168 --> 00:00:33,342 is the diameter, and so intuitively, what this is measuring is, you know, the width 11 00:00:33,342 --> 00:00:36,818 of the graph. What's the longest sort of, path you have 12 00:00:36,818 --> 00:00:40,990 to take to get from one place to another? Okay, and this gives us a measure of how 13 00:00:40,990 --> 00:00:43,415 much work we have to do, when we're transversing the graph. 14 00:00:43,415 --> 00:00:47,100 Okay, so if everything is very tightly connected, then the diameter will be very 15 00:00:47,100 --> 00:00:49,564 short, right? It only takes a few hops to get from 16 00:00:49,564 --> 00:00:53,372 anywhere to anywhere. and if the diameter is much longer, then 17 00:00:53,372 --> 00:00:57,030 it could potentially take longer then. So this gives you kind of the six degrees 18 00:00:57,030 --> 00:01:00,230 of separation, you know, six degrees of Kevin Bacon sort of, sort of measure, 19 00:01:00,230 --> 00:01:03,700 fine. So what is the diameter of this graph 20 00:01:03,700 --> 00:01:06,994 here. Well, we're looking for shortest paths, 21 00:01:06,994 --> 00:01:10,770 so, so let's look at some possible candidates. 22 00:01:10,770 --> 00:01:14,424 Well, things like a to f and a to b and d to c are all going to be shortest path 23 00:01:14,424 --> 00:01:18,350 one. So let's look a little closer at ones 24 00:01:18,350 --> 00:01:23,380 that appear to be far apart on the, you know, page here. 25 00:01:23,380 --> 00:01:25,820 So a to c, what's the shortest path there? 26 00:01:25,820 --> 00:01:31,260 Well, one path is a to b, b to e, e to g, and g to c. 27 00:01:31,260 --> 00:01:34,420 And that's a path, that's a path of length four, but there's a shorter one. 28 00:01:34,420 --> 00:01:39,872 There's a to b, b to d, and d to, and d to c, and so, a to c, the shortest path 29 00:01:39,872 --> 00:01:45,360 is three. So let's look at other ones. 30 00:01:45,360 --> 00:01:48,726 Well, f to anywhere, well you can't reach anywhere from f, because all the edges 31 00:01:48,726 --> 00:01:51,684 point inward and we're assuming a directed graph for this particular 32 00:01:51,684 --> 00:01:57,610 exercise. and g, similarly, you can't get anywhere. 33 00:01:57,610 --> 00:02:00,990 You can get to c, but c you can't get anywhere except back to g. 34 00:02:00,990 --> 00:02:04,524 So it looks like starting back from a, a to g, how many hops does it take to get 35 00:02:04,524 --> 00:02:09,956 there? 1, 2, 3, so a to g is 3 And that should 36 00:02:09,956 --> 00:02:18,800 be the longest ones. So the diameter of this graph is 3. 37 00:02:18,800 --> 00:02:21,400 So we can also measure the connectivity coefficient of a graph as a structural 38 00:02:21,400 --> 00:02:24,736 analysis task. So this is the minimum number of vertices 39 00:02:24,736 --> 00:02:27,900 you need to remove that will disconnect the graph. 40 00:02:27,900 --> 00:02:30,600 And so this, you can think of this intuitively as a sense of the measure of 41 00:02:30,600 --> 00:02:34,200 the fragility of the graph, right? How, how much redundancy is built into 42 00:02:34,200 --> 00:02:37,020 it? So if you're designing a network and it 43 00:02:37,020 --> 00:02:39,970 turns out the connectivity coefficient of the graph is 1. 44 00:02:39,970 --> 00:02:42,833 That means that if one machine, potentially, if one machine goes down. 45 00:02:42,833 --> 00:02:45,472 You could partition the network where nobody could communicate. 46 00:02:45,472 --> 00:02:47,782 Okay, so, if you're an advertiser, you might be interested in the connectivity 47 00:02:47,782 --> 00:02:51,384 coefficient of a graph. If you're trying to reach as many people 48 00:02:51,384 --> 00:02:54,360 as possible, it could be that if a few people don't pay attention to the ads, 49 00:02:54,360 --> 00:02:57,432 then a whole bunch of people won't send the message, if you're sort of in viral 50 00:02:57,432 --> 00:03:01,658 advertising or social media advertising, okay? 51 00:03:01,658 --> 00:03:04,807 And so, remember in the cap theorem that we discussed in the no sequel lectures, p 52 00:03:04,807 --> 00:03:07,674 was partitioning, right, so this was the, if your, if your system becomes 53 00:03:07,674 --> 00:03:11,920 partitioned. If your network becomes partitioned, can 54 00:03:11,920 --> 00:03:15,410 the system still function? And so connectivity coefficient could be 55 00:03:15,410 --> 00:03:18,014 a measure to help you estimate how likely it is that your network is going to be 56 00:03:18,014 --> 00:03:21,454 partitioned. Okay, so what is the connectivity 57 00:03:21,454 --> 00:03:25,376 coefficient of this graph? Well, depends on exactly what we mean by 58 00:03:25,376 --> 00:03:28,654 connectivity first. So we can say that a, that two vertices x 59 00:03:28,654 --> 00:03:32,188 and y are strongly connected if x is reachable from y and y is reachable from 60 00:03:32,188 --> 00:03:36,290 x, okay. Okay, and we might say that they are just 61 00:03:36,290 --> 00:03:40,632 connected if x is reachable from y or y is reachable from x. 62 00:03:40,632 --> 00:03:45,580 And so, this is sort of equivalent to ignoring the directionality of the edges. 63 00:03:45,580 --> 00:03:49,424 So if we just assume that everything is undirected, then we'll be using the 64 00:03:49,424 --> 00:03:52,510 second definition. So, let's assume that for a second. 65 00:03:52,510 --> 00:03:56,536 Let's assume we just mean connected here. Well, look, if, if we don't care about 66 00:03:56,536 --> 00:04:01,232 direction of traversing. Then if we remove e, is the graph 67 00:04:01,232 --> 00:04:05,803 disconnected? No because you can still reach everything 68 00:04:05,803 --> 00:04:11,330 through this other edge up there. And so, the only node here that appears 69 00:04:11,330 --> 00:04:15,050 to not be redundant here is b, and so, if you remove b though, you'll have two 70 00:04:15,050 --> 00:04:20,490 partitions in the network, a and f, and all the other ones here. 71 00:04:22,620 --> 00:04:27,430 So, the connectivity coefficient of this graph is one, because we can a vertex 72 00:04:27,430 --> 00:04:32,055 that if we remove it It'll partitioned at work. 73 00:04:32,055 --> 00:04:36,470 Okay, and we already discussed why you might want to compute this. 74 00:04:39,870 --> 00:04:43,006 So the connectivity coefficient is a measure of the graph itself and doesn't 75 00:04:43,006 --> 00:04:47,585 really give us a way to understand the relative importance of a single vertex. 76 00:04:47,585 --> 00:04:50,860 And so for this purpose has been various notion of centrality to find. 77 00:04:50,860 --> 00:04:53,500 So one is the closeness of centrality of a vertex, which is the average length of 78 00:04:53,500 --> 00:04:56,360 all the shortest paths that pass through it. 79 00:04:56,360 --> 00:04:57,874 Right? So this, intuitively this is, you can 80 00:04:57,874 --> 00:05:00,610 maybe compare this with a diameter of the graph, right? 81 00:05:00,610 --> 00:05:04,768 If the diameter is long, and the average length of all the shortest paths that go 82 00:05:04,768 --> 00:05:08,863 through a particular vertex is short, then it's not part of the diameter of the 83 00:05:08,863 --> 00:05:13,710 paths that define the diameter of the graph. 84 00:05:13,710 --> 00:05:16,488 And so, in some sense, it's maybe less central or less important. 85 00:05:16,488 --> 00:05:20,392 Okay, so another that may be more common is the between the centrality of a 86 00:05:20,392 --> 00:05:24,424 vertex, and this is the fraction of all the shortest paths in the whole graph 87 00:05:24,424 --> 00:05:30,606 that pass through this vertex. All right, so if you need to, if you need 88 00:05:30,606 --> 00:05:34,340 to go, you know, all roads lead through Rome. 89 00:05:34,340 --> 00:05:36,600 Right? If you need to go from Seattle to Atlanta 90 00:05:36,600 --> 00:05:40,080 in the US, then perhaps all paths go through one of two different major 91 00:05:40,080 --> 00:05:44,100 highways, or one or two, maybe one or two major cities, the northern route and the 92 00:05:44,100 --> 00:05:50,999 southern route or something. And so, the betweenness centrality of 93 00:05:50,999 --> 00:05:56,180 these two intermediate hubs is high. And so, if you think about a s-, a, a 94 00:05:56,180 --> 00:05:59,755 public transportation system where all trains lead into some central hub and 95 00:05:59,755 --> 00:06:03,220 then go out again, that central hub will have a high betweeness centrality, 96 00:06:03,220 --> 00:06:06,630 because the shortest path to get from point A to point B always goes through 97 00:06:06,630 --> 00:06:13,062 this one central vertex, okay? So what is the betweenness centrality of 98 00:06:13,062 --> 00:06:17,532 vertex e in this case? Well, there's a shortest path a to b to d 99 00:06:17,532 --> 00:06:22,460 to c that we found. The shortest path from a to c goes 100 00:06:22,460 --> 00:06:29,433 through there and the shortest path from a to g, ab, eg is, is 3. 101 00:06:29,433 --> 00:06:34,862 So, if you sort of add all these up, you'll see that the e is only involved in 102 00:06:34,862 --> 00:06:40,113 a, b, e, g and then a bunch of ones that are rooted in e itself, e to c and e to 103 00:06:40,113 --> 00:06:49,044 g, so between the centrality of e is 3. Oh, I'm sorry, 3 divided by the total 104 00:06:49,044 --> 00:06:52,846 number of shortest paths in the graph. Okay? 105 00:06:52,846 --> 00:06:55,973 It's the fraction.