[MUSIC]. 
So, one structural task you can do that's 
a little more detailed is to construct 
the histogram of a graph. 
And you saw this in the elastic MapReduce 
assignment if you completed it. 
So, we saw that the outdegree of a vertex 
is just the number of out going edges. 
So, some notation, let's say for each 
integer d, we'll let n of d be the number 
of vertices with that outdegree d. 
Okay. 
So, for example, in this graph, we have 
what is the outdegree of this vertex? 
It's zero, there are no outgoing edges. 
The outdegree of this vertex is two, 
there are two outgoing edges. 
The outdegree of this vertex of four, 
there are four outgoing edges. 
So, now we can count them up. 
We can say, how many vertices in this 
graph have outdegree 0. 
Well, there's just one. 
It's this one. 
How many vertices in this graph have 
outdegree one? 
Well, there are three of them: this one, 
this one, and this one, and so on. 
And then you just plot d versus n of d 
and create this histogram. 
So, we see one vertex at 0, 3 at 1, 2 at 
2, and so on. 
Okay. 
So, why might be the, why might this be a 
good idea to do? 
Well, it tells us something about the 
graph we're looking at. 
So, if we see this kind of a pattern. 
So we might see this kind of a happen 
where very few, or sorry, very many 
vertices in the graph have a very small 
out degree, and fewer and fewer as you go 
out the x axis. 
Or potentially you could see the other 
pattern where very few have a small out 
degree and many, many more have an high 
out degree. 
So, this is a much more connected graph, 
right? 
Everybody tends to be connected to every 
body else in this case. 
Most people have a very high outdegree 
with people. 
Most vertices have a very high out 
degree, and very few have a very high out 
degree. 
Okay. 
And it could be sort of more mixed. 
Like this, could be sort of bimodal. 
So, what's going on here? 
Well, if we see this pattern, then you 
can model this as an exponential 
distribution where d is in the actual 
exponent. 
And what this tells you is that it 
becomes very, very unlikely. 
The further you're out the x axis, it 
becomes exponentially less likely to find 
the vertex that has that outdegree. 
Right? 
So most have a small outdegree, one or a 
few, and as you go further out its much, 
much less likely. 
Okay. 
And you can see this effect very clearly 
if you plot it on a log scale, becomes 
linear on a log scale. 
Now, the thing about this is distribution 
is a random graph has this distribution. 
So, what I, what I mean by a random 
graph? 
Well, this is, take a set of vertices, 
and then choose two vertices at random 
and connect them with an edge. 
Then choose another two vertices 
completely at random and connect them 
with an edge, and so on. 
If you follow that process, you will get 
this kind of a distribution of the 
connectivity. 
Right? 
There will be very, very, it's very, 
very, very unlikely to construct a vertex 
that's connected to lots and lots of 
other vertices using this process. 
Okay. 
So, fine. 
So, it turns out that you don't find 
random graphs in nature very often. 
Okay. 
that's unfortunate because, if it, if, if 
you did have a random graph, it's 
actually thoroughly easy to work with. 
And by work with, I mean implement some 
of the tasks that we'll be talking about. 
Say in parallel, because you can split 
the edges up across a bunch of different 
machines and just work with them all sort 
of independently. 
But what you see more often in practice 
are these power log distributions, the 
zipf distribution, where there's some x 
that's in the exponent. 
You're raising the degree d to, to that 
exponent. 
And human generated data tends to have 
this distribution. 
And if you think about it, there's at 
least one way to get to build some 
intuition for why these come about. 
Okay? 
So, instead of choosing two vertices at 
random and connecting them with an edge. 
Instead, when you choose a vertex to 
connect with an edge, favor those ones 
that are already well connected. 
Okay. 
So, why would you bother, or why, why 
would this happen sort of naturally? 
Well, think about it. 
If you're in social networking, you join, 
you have someone who joins Facebook for 
the first time. 
Are they more likely to connect 
themselves to someone who's already very 
popular, or are they more likely to 
connect themselves to a bunch of Poeple 
who don't already have lots of friends. 
Well, it's much more likely to connect 
yourself to someone who's already very 
popular. 
That might be who introduced you to 
Facebook in the first place. 
Or with Twitter, are you more likely to 
follow people that are already have a lot 
of followers or more likely to follow 
people that do not have a lot of 
folowers? 
Well, more likely you're going to connect 
to and follow 
You're, you, you join Twitter in order to 
follow popular people. 
Okay? 
You can also this about this in terms of 
maybe the Internet, or the Web. 
When you create, when you create a web 
page, and put it on the web, are you more 
likely to link to sites that already have 
a lot of links, or not? 
Okay. 
And the answer is, you're more likely to 
consider, you you, it's reasonable to say 
that you're more likely to connect to web 
pages who already have a lot of links. 
Okay. 
So, with this preferential attachment 
model of constructing graphs, you'll 
generate this Zipf power log 
distribution. 
These are the distributions you tend to 
find in pre, in nature or on the web, 
whether you call that nature or not. 
And they have a distribution like this. 
They have this fatter tail, this long 
tail. 
So, now it's not quite so, unlikely to 
find vertices that have a very, very, 
very high outdegree. 
And you can see this effect more clearly 
on a log-log scale plot where both axes 
are on a log scale. 
I think, I'm not a huge fan of using 
log-log scale, except very sparingly, 
because lots of things, lots of 
distributions end up looking linear on a 
log-log scale. 
But these are defined to be linear on a 
log-log scale. 
So, you can do this kind of structural 
analysis. 
You can construct this histogram of very 
large graphs, like the web which, 
[UNKNOWN] all did in 2000. 
And we're probably overdue for analysis 
of this type, but it's become 
computationally difficult to produce 
these kinds of plots about, for the 
current internet. 
Okay. 
So, here's the plot. 
Here's the histogram of the web, and the 
question is, is this an exponential, or 
is this a Zipfian power law distribution? 
And you can see, it's kind of here in the 
description, but it's pretty clearly a 
power law. 
This is a log scale axis, and this is a 
log scale axis, and this looks pretty 
linearly, linear. 
So, what the authors went on to do, which 
I think is pretty interesting, is produce 
this kind of schematic of the overall 
structure of the web. 
And this circle in the middle here is a 
big, strongly connected component meaning 
that the pages within that component. 
If you can reach x from y you can reach y 
from x for any two pages. 
Okay. 
But then there's also an in and and out 
set of vertices, pages, that are kind of 
about the same size as the strongly 
connected component. 
So, these are things that are you know, 
you can reach the strongly connected 
component from these, but you cannot 
reach back, back from the strongly 
connected component. 
So, they link into the main mass of the 
internet. 
Okay. 
And then similarly on the outside, there 
are things that link from the strongly 
connected component which you can't get 
back. 
And it's about these big 3 3rds. 
And then they point it out that there are 
indeed tubes that connect the in to the 
out directly, not going through the 
strongly connected component. 
And there are these tendrils that sort of 
go off nowhere, but these are minor, 
perhaps minor components relative to the 
main three. 
And then you also have these sort of 
disconnected components that are smaller. 
But this is sort of interesting to 
understand the basic you know, physiology 
of the Internet, and it's, again, 
difficult to produce this, now, 'kay.