1 23:59:59,954 --> 00:00:05,449 [MUSIC]. 2 00:00:05,449 --> 00:00:08,959 So, we talked about structural analytics tasks as broken down by this paper in 3 00:00:08,959 --> 00:00:11,150 2012. What are some examples of traversal 4 00:00:11,150 --> 00:00:14,100 tasks? So, one is to find the minimum spanning 5 00:00:14,100 --> 00:00:17,426 tree of a graph. And, so that is the smallest subset of 6 00:00:17,426 --> 00:00:21,740 edges that connect the graph by some notion, notion of connectivity. 7 00:00:21,740 --> 00:00:25,578 So if we ignore directionality, we can talk about weakly connected graphs. 8 00:00:25,578 --> 00:00:30,070 So what is the minimum spanning tree of this graph? 9 00:00:30,070 --> 00:00:31,820 So we're looking for the smallest set of edges. 10 00:00:31,820 --> 00:00:33,804 A minimum spanning tree of this graph, cause there might be many that have the 11 00:00:33,804 --> 00:00:38,124 same number of edges in them. A minimum spanning tree of this graph. 12 00:00:38,124 --> 00:00:41,569 Well, we can get from a to b, and again we're going to ignore directionality, so 13 00:00:41,569 --> 00:00:45,610 there's actually two edges from a to b. So we take one of those. 14 00:00:45,610 --> 00:00:48,790 Then we can get from b to f, then we can from b to e, and we get from b to d, then 15 00:00:48,790 --> 00:00:53,640 we get from d to c, and e to g. And so that's one edge, two edge, three 16 00:00:53,640 --> 00:00:58,321 edge, four edge, five edge, six edge. And so the minimum spanning tree, the 17 00:00:58,321 --> 00:01:01,420 number of edges in the minimum spanning tree is six. 18 00:01:01,420 --> 00:01:08,030 Another way to get six is, go from a to b and a to f, and then the same otherwise. 19 00:01:08,030 --> 00:01:11,620 B to d, b to e, d to c, and e to g. Okay. 20 00:01:11,620 --> 00:01:15,037 So there's two different minimum spanning trees with the same number of edges in 21 00:01:15,037 --> 00:01:18,250 them, and there are fast algorithms to compute this, so we're not initially 22 00:01:18,250 --> 00:01:21,362 going to go into. This is sort of a guided tour of various 23 00:01:21,362 --> 00:01:23,154 tasks you might want to compute, but we're not necessarily going to describe 24 00:01:23,154 --> 00:01:25,291 the algorithms in every case. Right? 25 00:01:25,291 --> 00:01:31,940 So another traversal oriented task is, finding paths and circuits. 26 00:01:31,940 --> 00:01:36,165 And so the, you know, classic example of this is Euler's Bridges of Konigsberg 27 00:01:36,165 --> 00:01:40,390 problem, where the task is to find a, a path where we visit every vertex, and yet 28 00:01:40,390 --> 00:01:47,180 cross every bridge in this graph here in the picture only, once. 29 00:01:47,180 --> 00:01:50,764 And so the observation was made here is well, if you enter by a bridge, you must 30 00:01:50,764 --> 00:01:54,240 also leave by a bridge. And you can't leave by the same one you 31 00:01:54,240 --> 00:01:56,790 came in on, because that's the definition of the problem. 32 00:01:56,790 --> 00:01:59,370 So this suggests that there needs to be an even number of bridges to every 33 00:01:59,370 --> 00:02:01,570 vertex, right? You, you have to have one to come in on, 34 00:02:01,570 --> 00:02:03,670 and one to go out on. And then you can come back, come back to 35 00:02:03,670 --> 00:02:07,067 this vertex as many times as you want. And so there's two sort of related 36 00:02:07,067 --> 00:02:10,107 results here. If you, going from the bottom one here 37 00:02:10,107 --> 00:02:13,812 first, if you actually want to start in on the same vertex, well the condition is 38 00:02:13,812 --> 00:02:17,517 that every vertex in the graph needs to have an even number of edges, so that you 39 00:02:17,517 --> 00:02:22,670 can come in by one and you can leave by one. 40 00:02:22,670 --> 00:02:27,206 And this allows you to make an entire circuit, all the way around the, the 41 00:02:27,206 --> 00:02:30,190 graph. If you don't care where you start and 42 00:02:30,190 --> 00:02:33,006 end, your I'll just start on one and end on another then its a little bit softer 43 00:02:33,006 --> 00:02:36,237 condition. And you can, most of the vertices need to 44 00:02:36,237 --> 00:02:41,840 have an even number of edges. but you can have at most, two vertices 45 00:02:41,840 --> 00:02:45,219 that have an odd degree. The one you start on and the one you end 46 00:02:45,219 --> 00:02:49,340 on, because you'll need to leave by one and you only need to come in by one. 47 00:02:49,340 --> 00:02:50,800 And, I'm assuming non-directed edges here. 48 00:02:50,800 --> 00:02:53,390 The definitions get slightly more complex if you start talking about directive but 49 00:02:53,390 --> 00:02:56,065 not, not much. Essentially you'd have a balance, you can 50 00:02:56,065 --> 00:03:00,020 have the same number of in degree edges and out degree edges, okay. 51 00:03:00,020 --> 00:03:01,770 And what's nice about this is it's a very, very, you know. 52 00:03:01,770 --> 00:03:05,100 This is a great result, because it's very easy to check this condition. 53 00:03:05,100 --> 00:03:08,268 Right, you can just add up the degrees of all the vertices in the graph and you can 54 00:03:08,268 --> 00:03:12,810 tell whether, whether one of these circuits or one of these paths exists. 55 00:03:12,810 --> 00:03:16,230 But, to sort of demonstrate the subtlety of you know, some of these graph 56 00:03:16,230 --> 00:03:21,660 theoretic problems, you can make a very slight change to the problem statement. 57 00:03:21,660 --> 00:03:25,849 The answer becomes a lot harder. So can we create a path that visits every 58 00:03:25,849 --> 00:03:29,850 vertex only once, as opposed to every edge only once? 59 00:03:29,850 --> 00:03:32,905 Well this is a hell of a lot harder, and the reason is is that intuitively, if you 60 00:03:32,905 --> 00:03:35,960 think about it, you know, every vertex has lots of edges and so it's involved in 61 00:03:35,960 --> 00:03:38,733 lots of different paths, lots of different possible paths through the 62 00:03:38,733 --> 00:03:42,549 graph. And you're trying to find one of these 63 00:03:42,549 --> 00:03:45,410 such paths that touches every vertex only once. 64 00:03:45,410 --> 00:03:49,106 Well, given that this, you, you there's vertexes involved in lots of different 65 00:03:49,106 --> 00:03:52,968 paths, you're only allowed to use that vertex one time. 66 00:03:52,968 --> 00:03:56,388 And so, you can imagine that it's difficult to figure out what is the best 67 00:03:56,388 --> 00:04:00,281 way to use this vertex. There's a whole lot of different 68 00:04:00,281 --> 00:04:03,720 conditions you have to, have to consider, okay. 69 00:04:03,720 --> 00:04:07,647 A related problem is, you know, assume there's a cost to traversing each edge. 70 00:04:08,710 --> 00:04:11,070 Alright, there's a distance you have to travel, for example. 71 00:04:11,070 --> 00:04:13,692 Can we find a path that visits every vertex only once, but also has the 72 00:04:13,692 --> 00:04:18,084 minimum cost out of all these? And so there's no efficient algorithm 73 00:04:18,084 --> 00:04:20,898 that can exist for these problems, and so heuristics and approximations are the 74 00:04:20,898 --> 00:04:23,790 best we can do. And this, this extension here is the, you 75 00:04:23,790 --> 00:04:25,721 know, traveling salesman problem. Okay. 76 00:04:25,721 --> 00:04:29,540 So these might be some of the al tasks you might want to do. 77 00:04:29,540 --> 00:04:34,400 These actually come up, I would argue, less often in a big data context. 78 00:04:34,400 --> 00:04:38,678 Pers, especially this one, in part because it's such a difficult answer to 79 00:04:38,678 --> 00:04:42,196 compute. And also, it's not clear that it's all 80 00:04:42,196 --> 00:04:47,760 that useful, say, in a social network context or in a web analytics context. 81 00:04:47,760 --> 00:04:50,945 You're not necessarily trying to find paths that touch every single vertex in 82 00:04:50,945 --> 00:04:54,209 the entire web. So this is, this tends to be, you know, 83 00:04:54,209 --> 00:04:58,044 the only times when you're interested in touching every vertex in a graph, how 84 00:04:58,044 --> 00:05:02,770 clean, is when the graph is in some sense small, okay? 85 00:05:02,770 --> 00:05:05,330 So, this is less of a big data problem, but it's something to be familiar with, 86 00:05:05,330 --> 00:05:07,952 in, in, if you're thinking about graph analytics. 87 00:05:07,952 --> 00:05:11,944 Alright. So one more traversal task, just to be 88 00:05:11,944 --> 00:05:17,179 familiar with, is maximum flow problems. So here the input is a graph with labeled 89 00:05:17,179 --> 00:05:21,667 edges indicating the capacity of each edge, and then special vertices sources 90 00:05:21,667 --> 00:05:26,223 and sinks, and the idea is to find a sub graph that maximizes flow between sources 91 00:05:26,223 --> 00:05:31,299 and sinks. And so, the observation here is that for 92 00:05:31,299 --> 00:05:34,552 each vertex, incoming flow must equal outgoing flow. 93 00:05:34,552 --> 00:05:38,988 Okay. And so in this example, if a is a source, 94 00:05:38,988 --> 00:05:45,720 and f, f and g are the sinks, then you can think about. 95 00:05:45,720 --> 00:05:48,788 A sub-graph where you just have a directly to f because it's only one hop 96 00:05:48,788 --> 00:05:51,908 away, and so the flow between them is two, but if you look at a path a to b and 97 00:05:51,908 --> 00:05:55,028 then b to f, you get the flow of four here and the flow from, or the capacity 98 00:05:55,028 --> 00:05:58,356 of four here and the capacity of three here which means the maximum flow along 99 00:05:58,356 --> 00:06:04,611 this is three. Right, there's some unused capacity on, 100 00:06:04,611 --> 00:06:07,797 on this edge, but three is still higher than two, and so that's, we want to 101 00:06:07,797 --> 00:06:12,670 include that in the, in the sub-graph from, from a to f. 102 00:06:12,670 --> 00:06:16,830 Okay, and then get over to g, you can do sort of a similar walk and say, well, one 103 00:06:16,830 --> 00:06:21,060 path is b to d. Through a capacity of five, and d to e 104 00:06:21,060 --> 00:06:25,020 through a capacity of two, and e through g through a capacity of two. 105 00:06:25,020 --> 00:06:29,815 And so the maximum flow here is two. While a to b, b to d, d to c and c to g, 106 00:06:29,815 --> 00:06:36,063 the maximum capacity is three. This edge is the, is the, is the weak 107 00:06:36,063 --> 00:06:39,394 link. Okay, so it looks like the max flow 108 00:06:39,394 --> 00:06:47,890 sub-graph is a, b, f, d, c, g. Or rather, d, i, g, b. 109 00:06:47,890 --> 00:06:50,280 The edge b, d. The edge d, c. 110 00:06:50,280 --> 00:06:55,710 And the edge c, g. And the edge b, f.