1 23:59:59,500 --> 00:00:05,796 [MUSIC]. 2 00:00:05,796 --> 00:00:08,489 So, I want to spend some time talking about graphs, and graph analytics. 3 00:00:08,489 --> 00:00:10,820 So, we've encountered these before in the context of the elastic map review 4 00:00:10,820 --> 00:00:13,065 assignment. But we haven't spent too much time in the 5 00:00:13,065 --> 00:00:16,394 lectures talking about them. But they're increasingly important in the 6 00:00:16,394 --> 00:00:19,360 data science context for reasons we'll talk about. 7 00:00:19,360 --> 00:00:23,090 So, what is a Graph? A graph is a pair of sets. 8 00:00:23,090 --> 00:00:26,377 A set of vertices and a set of edges. Okay, you might also see vertices 9 00:00:26,377 --> 00:00:29,833 referred to as nodes, but I'm going to try to avoid that terminology to avoid 10 00:00:29,833 --> 00:00:34,066 confusion with clusters of computers. In which computers were referred to as a 11 00:00:34,066 --> 00:00:34,928 node. Okay. 12 00:00:34,928 --> 00:00:39,374 So, V is a set of vertices and E is a set of edges and each edge is a pair of 13 00:00:39,374 --> 00:00:44,760 vertices, a source and a target. And so, edges may be considered directed 14 00:00:44,760 --> 00:00:46,900 or undirected and we'll talk a little more about this. 15 00:00:46,900 --> 00:00:50,868 But maybe it's an edge from a source to a target or maybe it's just a pair and the 16 00:00:50,868 --> 00:00:55,260 order doesn't matter. So, these graphs are increasingly common 17 00:00:55,260 --> 00:00:58,185 in the wild, right? The web itself can be modeled quite 18 00:00:58,185 --> 00:01:01,815 directly as a graph where every page is a vertex, and every link between pages is 19 00:01:01,815 --> 00:01:05,210 an edge. The internet underlying the web can be 20 00:01:05,210 --> 00:01:08,360 modeled as a graph, where every computer is in a vertex, and every route is an 21 00:01:08,360 --> 00:01:13,592 edge, or maybe even every packet. social networks, as we've seen in some of 22 00:01:13,592 --> 00:01:16,623 the assignments. these are becoming increasingly important 23 00:01:16,623 --> 00:01:19,730 as, as a political driver and as a driver for social change. 24 00:01:19,730 --> 00:01:22,385 They're, you know, the, the influence they have is pretty difficult to 25 00:01:22,385 --> 00:01:25,377 overstate. And this is very obviously a graph where 26 00:01:25,377 --> 00:01:31,590 every can, can connection between two people in the social network is an edge. 27 00:01:31,590 --> 00:01:34,210 communication logs can be modeled as a graph. 28 00:01:34,210 --> 00:01:38,029 Every phone call between two people is an edge of course in the news recently this 29 00:01:38,029 --> 00:01:41,975 is becoming quite important with the prison program. 30 00:01:41,975 --> 00:01:44,360 and so, many more. And so, one reason these are so 31 00:01:44,360 --> 00:01:47,276 ubiquitous is that it really does get kind of the fundamentals of 32 00:01:47,276 --> 00:01:51,254 communication, right? You have a big set of actors and anytime, 33 00:01:51,254 --> 00:01:55,540 anytime one actor interacts with another, that can be modeled as an edge. 34 00:01:55,540 --> 00:01:59,080 And so, this is just a very common paradigm to, to in, in a lot, they can 35 00:01:59,080 --> 00:02:03,790 capture the behavior of a lot of different kinds of systems. 36 00:02:03,790 --> 00:02:06,434 Okay. The other reason you see this would be so 37 00:02:06,434 --> 00:02:10,030 ubiquitous in kind of a data modeling aspect is that, you know, objects and 38 00:02:10,030 --> 00:02:15,541 relationships between those objects. You can't really get any lower than that, 39 00:02:15,541 --> 00:02:18,420 right? So, relations talk about you know, the 40 00:02:18,420 --> 00:02:23,830 relation data model talks about tables where you have records and attributes. 41 00:02:23,830 --> 00:02:25,260 But even here, there's a bit of complexity. 42 00:02:25,260 --> 00:02:28,098 You have to sort of think about a schema, and you have to sort of think about every 43 00:02:28,098 --> 00:02:30,985 record is going to have the same schema and so on. 44 00:02:30,985 --> 00:02:33,780 Graph's kind of blow up all that and dis, disintegrate everything down to just 45 00:02:33,780 --> 00:02:36,832 objects in relationships. And so, in some sense, it's the lowest 46 00:02:36,832 --> 00:02:40,107 common denominator data model. what we'll get into a little bit is my 47 00:02:40,107 --> 00:02:42,949 opinion that I think you, you throw out quite a bit when you sort of drop 48 00:02:42,949 --> 00:02:47,350 everything down to that level. But we'll talk about that in a bit. 49 00:02:50,030 --> 00:02:51,550 So, what do we want to do with these graphs? 50 00:02:51,550 --> 00:02:56,680 So, Bordewekar, in 2012, wrote a paper about analyzing analytics. 51 00:02:56,680 --> 00:02:59,561 And they tried to sort of categorize various analytics tasks in a variety, in 52 00:02:59,561 --> 00:03:03,400 a variety of categories, and one of the categories was graph analytics. 53 00:03:03,400 --> 00:03:06,520 And he broke it down into these three patterns, structural algorithms, 54 00:03:06,520 --> 00:03:09,990 traversal algorithms, and pattern-matching algorithms. 55 00:03:09,990 --> 00:03:12,787 And I think this is as good a breakdown as, as any other. 56 00:03:12,787 --> 00:03:15,710 So, this is the one we will use in the next several slides. 57 00:03:15,710 --> 00:03:18,950 So, you think about just structural tasks, structural algorithms. 58 00:03:18,950 --> 00:03:21,470 You know, the first thing to do when encountering a graph you're expected to 59 00:03:21,470 --> 00:03:24,289 work with or understand. It's just to just collect some basic 60 00:03:24,289 --> 00:03:25,910 metrics, right? How big is it? 61 00:03:25,910 --> 00:03:30,260 How many vertices and how many edges? And one of the takeaways I want you to 62 00:03:30,260 --> 00:03:34,278 have is that the number of edges is more relevant than the number of vertices. 63 00:03:34,278 --> 00:03:36,770 When you're trying to understand the scale of a graph. 64 00:03:36,770 --> 00:03:39,110 So, you know, many times you'll have a conversation with someone, and they'll 65 00:03:39,110 --> 00:03:41,726 say, well, I have this really big graph I'm working with. 66 00:03:41,726 --> 00:03:44,030 So, the next question you should ask is, how many edges, not how many bytes and 67 00:03:44,030 --> 00:03:47,252 not how many vertices. And the reason that you don't care about 68 00:03:47,252 --> 00:03:50,924 the bytes is because there might be all kinds of other information packed into 69 00:03:50,924 --> 00:03:55,410 the, the labeling of these things. But that can really be factored out from 70 00:03:55,410 --> 00:03:57,930 the graph itself and modeled maybe more traditionally in a, in a relational 71 00:03:57,930 --> 00:04:01,716 database. And so, the performance may not depend so 72 00:04:01,716 --> 00:04:07,145 much on exactly a number of bytes. But the graph structure the, is, is a 73 00:04:07,145 --> 00:04:10,440 challenge as we'll see. Okay. 74 00:04:10,440 --> 00:04:13,429 And so, the number of vertices is, is one measure but the number of edges is 75 00:04:13,429 --> 00:04:15,862 another. So, why is the number of edges more 76 00:04:15,862 --> 00:04:19,387 important than the number of vertices? Well, because it scales quadratically 77 00:04:19,387 --> 00:04:22,878 with the number of vertices, right? You can have at most number of vertices 78 00:04:22,878 --> 00:04:25,728 squared number of edges. And that's a really, really big number in 79 00:04:25,728 --> 00:04:26,530 some cases. Right? 80 00:04:26,530 --> 00:04:30,028 If there's two billion people using a social network, well two billion squared 81 00:04:30,028 --> 00:04:33,774 is the number of possible friend relationships you have. 82 00:04:33,774 --> 00:04:36,954 And if you're expecting to do some analytics on this graph, you're going to 83 00:04:36,954 --> 00:04:41,600 be processing all of those edges perhaps. Okay, and then second question you should 84 00:04:41,600 --> 00:04:44,960 ask, after the number of edges is, what is the highest in or out degree. 85 00:04:45,970 --> 00:04:48,530 As a proxy for really what is the degree of distribution here. 86 00:04:48,530 --> 00:04:50,000 So, what do I mean, what do I mean by degree? 87 00:04:50,000 --> 00:04:52,867 Well, the num, the, the in degree of a vertex is the number of edges that are 88 00:04:52,867 --> 00:04:55,656 coming into it. And the out degree of a vertex is the 89 00:04:55,656 --> 00:04:59,107 number of edges that go out of it. Okay, and so how the edges are 90 00:04:59,107 --> 00:05:03,459 distributed among all the vertices tends to be a driver of how difficult the graph 91 00:05:03,459 --> 00:05:07,540 is to work with. If they're all pretty evenly distributed 92 00:05:07,540 --> 00:05:10,845 then this isn't much of a problem. You can paralyze things as we'll see and 93 00:05:10,845 --> 00:05:14,496 everything works out nicely. However, very, almost never do graphs in 94 00:05:14,496 --> 00:05:19,780 the wild have this property where things are sort of randomly distributed. 95 00:05:19,780 --> 00:05:24,130 It tends to be very skewed. So, there is you know, in a social 96 00:05:24,130 --> 00:05:28,218 network, there tends to be a person whose is friends with everybody in the graph, 97 00:05:28,218 --> 00:05:31,230 right? Very, very popular people. 98 00:05:33,200 --> 00:05:35,510 Almost everybody in the graph. Okay? 99 00:05:35,510 --> 00:05:38,758 in a, you know, on the web there are pages that tend to be linked to by 100 00:05:38,758 --> 00:05:42,200 everyone right? Very, very popular pages. 101 00:05:42,200 --> 00:05:45,775 And so, this imbalance in the degree distribution is one of the challenges I'm 102 00:05:45,775 --> 00:05:49,984 working with very, very large graphs. And so, if you know the number of edges, 103 00:05:49,984 --> 00:05:52,483 you've got one indication of sort of gross scale. 104 00:05:52,483 --> 00:05:56,383 And then, if you know about how high, how many edges are in the you know, most 105 00:05:56,383 --> 00:05:59,906 popular vertex. That gives you some idea of how skewed 106 00:05:59,906 --> 00:06:00,700 things are. Okay. 107 00:06:00,700 --> 00:06:04,158 So, fine. So, when you're working with graphs, 108 00:06:04,158 --> 00:06:05,700 these are the things you're going to be able to do. 109 00:06:05,700 --> 00:06:08,201 Can you just count the vertexes, count the edges? 110 00:06:08,201 --> 00:06:11,477 Can you say given a vertex can I get the number of in, in edges and out edges for 111 00:06:11,477 --> 00:06:14,412 that vertex? And can I maybe do that for every vertex 112 00:06:14,412 --> 00:06:17,700 in the graph? Okay, and so this is hard to work with. 113 00:06:18,800 --> 00:06:20,720 You know, this is going to be the basis for, for many other tasks.