1 23:59:59,922 --> 00:00:05,819 [MUSIC]. 2 00:00:05,819 --> 00:00:08,855 So, one structural task you can do that's a little more detailed is to construct 3 00:00:08,855 --> 00:00:12,432 the histogram of a graph. And you saw this in the elastic MapReduce 4 00:00:12,432 --> 00:00:16,334 assignment if you completed it. So, we saw that the outdegree of a vertex 5 00:00:16,334 --> 00:00:21,100 is just the number of out going edges. So, some notation, let's say for each 6 00:00:21,100 --> 00:00:26,530 integer d, we'll let n of d be the number of vertices with that outdegree d. 7 00:00:26,530 --> 00:00:29,132 Okay. So, for example, in this graph, we have 8 00:00:29,132 --> 00:00:34,730 what is the outdegree of this vertex? It's zero, there are no outgoing edges. 9 00:00:34,730 --> 00:00:38,760 The outdegree of this vertex is two, there are two outgoing edges. 10 00:00:38,760 --> 00:00:41,630 The outdegree of this vertex of four, there are four outgoing edges. 11 00:00:41,630 --> 00:00:45,130 So, now we can count them up. We can say, how many vertices in this 12 00:00:45,130 --> 00:00:48,700 graph have outdegree 0. Well, there's just one. 13 00:00:48,700 --> 00:00:51,768 It's this one. How many vertices in this graph have 14 00:00:51,768 --> 00:00:54,802 outdegree one? Well, there are three of them: this one, 15 00:00:54,802 --> 00:00:59,937 this one, and this one, and so on. And then you just plot d versus n of d 16 00:00:59,937 --> 00:01:07,309 and create this histogram. So, we see one vertex at 0, 3 at 1, 2 at 17 00:01:07,309 --> 00:01:11,280 2, and so on. Okay. 18 00:01:11,280 --> 00:01:14,269 So, why might be the, why might this be a good idea to do? 19 00:01:14,269 --> 00:01:16,410 Well, it tells us something about the graph we're looking at. 20 00:01:18,220 --> 00:01:22,209 So, if we see this kind of a pattern. So we might see this kind of a happen 21 00:01:22,209 --> 00:01:25,869 where very few, or sorry, very many vertices in the graph have a very small 22 00:01:25,869 --> 00:01:30,800 out degree, and fewer and fewer as you go out the x axis. 23 00:01:32,090 --> 00:01:37,338 Or potentially you could see the other pattern where very few have a small out 24 00:01:37,338 --> 00:01:42,770 degree and many, many more have an high out degree. 25 00:01:42,770 --> 00:01:46,660 So, this is a much more connected graph, right? 26 00:01:46,660 --> 00:01:48,900 Everybody tends to be connected to every body else in this case. 27 00:01:48,900 --> 00:01:50,710 Most people have a very high outdegree with people. 28 00:01:50,710 --> 00:01:55,529 Most vertices have a very high out degree, and very few have a very high out 29 00:01:55,529 --> 00:01:57,850 degree. Okay. 30 00:01:57,850 --> 00:02:03,200 And it could be sort of more mixed. Like this, could be sort of bimodal. 31 00:02:03,200 --> 00:02:06,522 So, what's going on here? Well, if we see this pattern, then you 32 00:02:06,522 --> 00:02:10,698 can model this as an exponential distribution where d is in the actual 33 00:02:10,698 --> 00:02:14,914 exponent. And what this tells you is that it 34 00:02:14,914 --> 00:02:17,940 becomes very, very unlikely. The further you're out the x axis, it 35 00:02:17,940 --> 00:02:22,115 becomes exponentially less likely to find the vertex that has that outdegree. 36 00:02:22,115 --> 00:02:25,514 Right? So most have a small outdegree, one or a 37 00:02:25,514 --> 00:02:32,090 few, and as you go further out its much, much less likely. 38 00:02:32,090 --> 00:02:34,373 Okay. And you can see this effect very clearly 39 00:02:34,373 --> 00:02:38,595 if you plot it on a log scale, becomes linear on a log scale. 40 00:02:38,595 --> 00:02:45,520 Now, the thing about this is distribution is a random graph has this distribution. 41 00:02:45,520 --> 00:02:47,240 So, what I, what I mean by a random graph? 42 00:02:47,240 --> 00:02:50,453 Well, this is, take a set of vertices, and then choose two vertices at random 43 00:02:50,453 --> 00:02:53,910 and connect them with an edge. Then choose another two vertices 44 00:02:53,910 --> 00:02:57,020 completely at random and connect them with an edge, and so on. 45 00:02:57,020 --> 00:03:00,619 If you follow that process, you will get this kind of a distribution of the 46 00:03:00,619 --> 00:03:02,650 connectivity. Right? 47 00:03:02,650 --> 00:03:05,900 There will be very, very, it's very, very, very unlikely to construct a vertex 48 00:03:05,900 --> 00:03:10,185 that's connected to lots and lots of other vertices using this process. 49 00:03:10,185 --> 00:03:12,900 Okay. So, fine. 50 00:03:12,900 --> 00:03:17,855 So, it turns out that you don't find random graphs in nature very often. 51 00:03:17,855 --> 00:03:21,689 Okay. that's unfortunate because, if it, if, if 52 00:03:21,689 --> 00:03:29,340 you did have a random graph, it's actually thoroughly easy to work with. 53 00:03:29,340 --> 00:03:33,968 And by work with, I mean implement some of the tasks that we'll be talking about. 54 00:03:33,968 --> 00:03:37,413 Say in parallel, because you can split the edges up across a bunch of different 55 00:03:37,413 --> 00:03:41,415 machines and just work with them all sort of independently. 56 00:03:41,415 --> 00:03:46,615 But what you see more often in practice are these power log distributions, the 57 00:03:46,615 --> 00:03:52,890 zipf distribution, where there's some x that's in the exponent. 58 00:03:52,890 --> 00:03:55,885 You're raising the degree d to, to that exponent. 59 00:03:55,885 --> 00:03:59,370 And human generated data tends to have this distribution. 60 00:03:59,370 --> 00:04:03,189 And if you think about it, there's at least one way to get to build some 61 00:04:03,189 --> 00:04:08,010 intuition for why these come about. Okay? 62 00:04:08,010 --> 00:04:13,361 So, instead of choosing two vertices at random and connecting them with an edge. 63 00:04:13,361 --> 00:04:17,453 Instead, when you choose a vertex to connect with an edge, favor those ones 64 00:04:17,453 --> 00:04:22,240 that are already well connected. Okay. 65 00:04:22,240 --> 00:04:25,060 So, why would you bother, or why, why would this happen sort of naturally? 66 00:04:25,060 --> 00:04:27,650 Well, think about it. If you're in social networking, you join, 67 00:04:27,650 --> 00:04:30,502 you have someone who joins Facebook for the first time. 68 00:04:30,502 --> 00:04:33,308 Are they more likely to connect themselves to someone who's already very 69 00:04:33,308 --> 00:04:36,160 popular, or are they more likely to connect themselves to a bunch of Poeple 70 00:04:36,160 --> 00:04:40,862 who don't already have lots of friends. Well, it's much more likely to connect 71 00:04:40,862 --> 00:04:43,100 yourself to someone who's already very popular. 72 00:04:43,100 --> 00:04:46,210 That might be who introduced you to Facebook in the first place. 73 00:04:46,210 --> 00:04:48,520 Or with Twitter, are you more likely to follow people that are already have a lot 74 00:04:48,520 --> 00:04:50,480 of followers or more likely to follow people that do not have a lot of 75 00:04:50,480 --> 00:04:53,842 folowers? Well, more likely you're going to connect 76 00:04:53,842 --> 00:04:59,098 to and follow You're, you, you join Twitter in order to 77 00:04:59,098 --> 00:05:01,519 follow popular people. Okay? 78 00:05:01,519 --> 00:05:03,975 You can also this about this in terms of maybe the Internet, or the Web. 79 00:05:03,975 --> 00:05:08,700 When you create, when you create a web page, and put it on the web, are you more 80 00:05:08,700 --> 00:05:14,982 likely to link to sites that already have a lot of links, or not? 81 00:05:14,982 --> 00:05:17,448 Okay. And the answer is, you're more likely to 82 00:05:17,448 --> 00:05:21,450 consider, you you, it's reasonable to say that you're more likely to connect to web 83 00:05:21,450 --> 00:05:25,265 pages who already have a lot of links. Okay. 84 00:05:25,265 --> 00:05:28,645 So, with this preferential attachment model of constructing graphs, you'll 85 00:05:28,645 --> 00:05:31,430 generate this Zipf power log distribution. 86 00:05:31,430 --> 00:05:34,468 These are the distributions you tend to find in pre, in nature or on the web, 87 00:05:34,468 --> 00:05:39,710 whether you call that nature or not. And they have a distribution like this. 88 00:05:39,710 --> 00:05:44,110 They have this fatter tail, this long tail. 89 00:05:44,110 --> 00:05:47,892 So, now it's not quite so, unlikely to find vertices that have a very, very, 90 00:05:47,892 --> 00:05:52,110 very high outdegree. And you can see this effect more clearly 91 00:05:52,110 --> 00:05:56,295 on a log-log scale plot where both axes are on a log scale. 92 00:05:56,295 --> 00:05:59,833 I think, I'm not a huge fan of using log-log scale, except very sparingly, 93 00:05:59,833 --> 00:06:03,313 because lots of things, lots of distributions end up looking linear on a 94 00:06:03,313 --> 00:06:08,198 log-log scale. But these are defined to be linear on a 95 00:06:08,198 --> 00:06:12,334 log-log scale. So, you can do this kind of structural 96 00:06:12,334 --> 00:06:15,058 analysis. You can construct this histogram of very 97 00:06:15,058 --> 00:06:19,230 large graphs, like the web which, [UNKNOWN] all did in 2000. 98 00:06:19,230 --> 00:06:22,652 And we're probably overdue for analysis of this type, but it's become 99 00:06:22,652 --> 00:06:26,487 computationally difficult to produce these kinds of plots about, for the 100 00:06:26,487 --> 00:06:30,430 current internet. Okay. 101 00:06:30,430 --> 00:06:33,625 So, here's the plot. Here's the histogram of the web, and the 102 00:06:33,625 --> 00:06:38,635 question is, is this an exponential, or is this a Zipfian power law distribution? 103 00:06:38,635 --> 00:06:43,185 And you can see, it's kind of here in the description, but it's pretty clearly a 104 00:06:43,185 --> 00:06:46,810 power law. This is a log scale axis, and this is a 105 00:06:46,810 --> 00:06:50,770 log scale axis, and this looks pretty linearly, linear. 106 00:06:50,770 --> 00:06:56,074 So, what the authors went on to do, which I think is pretty interesting, is produce 107 00:06:56,074 --> 00:07:01,955 this kind of schematic of the overall structure of the web. 108 00:07:01,955 --> 00:07:07,259 And this circle in the middle here is a big, strongly connected component meaning 109 00:07:07,259 --> 00:07:13,993 that the pages within that component. If you can reach x from y you can reach y 110 00:07:13,993 --> 00:07:17,209 from x for any two pages. Okay. 111 00:07:17,209 --> 00:07:22,201 But then there's also an in and and out set of vertices, pages, that are kind of 112 00:07:22,201 --> 00:07:28,000 about the same size as the strongly connected component. 113 00:07:28,000 --> 00:07:30,772 So, these are things that are you know, you can reach the strongly connected 114 00:07:30,772 --> 00:07:33,412 component from these, but you cannot reach back, back from the strongly 115 00:07:33,412 --> 00:07:36,711 connected component. So, they link into the main mass of the 116 00:07:36,711 --> 00:07:39,030 internet. Okay. 117 00:07:39,030 --> 00:07:41,208 And then similarly on the outside, there are things that link from the strongly 118 00:07:41,208 --> 00:07:43,170 connected component which you can't get back. 119 00:07:44,200 --> 00:07:48,703 And it's about these big 3 3rds. And then they point it out that there are 120 00:07:48,703 --> 00:07:51,865 indeed tubes that connect the in to the out directly, not going through the 121 00:07:51,865 --> 00:07:56,302 strongly connected component. And there are these tendrils that sort of 122 00:07:56,302 --> 00:07:59,770 go off nowhere, but these are minor, perhaps minor components relative to the 123 00:07:59,770 --> 00:08:02,692 main three. And then you also have these sort of 124 00:08:02,692 --> 00:08:07,142 disconnected components that are smaller. But this is sort of interesting to 125 00:08:07,142 --> 00:08:11,238 understand the basic you know, physiology of the Internet, and it's, again, 126 00:08:11,238 --> 00:08:14,850 difficult to produce this, now, 'kay.