[MUSIC]. 
So, I want to spend some time talking 
about graphs, and graph analytics. 
So, we've encountered these before in the 
context of the elastic map review 
assignment. 
But we haven't spent too much time in the 
lectures talking about them. 
But they're increasingly important in the 
data science context for reasons we'll 
talk about. 
So, what is a Graph? 
A graph is a pair of sets. 
A set of vertices and a set of edges. 
Okay, you might also see vertices 
referred to as nodes, but I'm going to 
try to avoid that terminology to avoid 
confusion with clusters of computers. 
In which computers were referred to as a 
node. 
Okay. 
So, V is a set of vertices and E is a set 
of edges and each edge is a pair of 
vertices, a source and a target. 
And so, edges may be considered directed 
or undirected and we'll talk a little 
more about this. 
But maybe it's an edge from a source to a 
target or maybe it's just a pair and the 
order doesn't matter. 
So, these graphs are increasingly common 
in the wild, right? 
The web itself can be modeled quite 
directly as a graph where every page is a 
vertex, and every link between pages is 
an edge. 
The internet underlying the web can be 
modeled as a graph, where every computer 
is in a vertex, and every route is an 
edge, or maybe even every packet. 
social networks, as we've seen in some of 
the assignments. 
these are becoming increasingly important 
as, as a political driver and as a driver 
for social change. 
They're, you know, the, the influence 
they have is pretty difficult to 
overstate. 
And this is very obviously a graph where 
every can, can connection between two 
people in the social network is an edge. 
communication logs can be modeled as a 
graph. 
Every phone call between two people is an 
edge of course in the news recently this 
is becoming quite important with the 
prison program. 
and so, many more. 
And so, one reason these are so 
ubiquitous is that it really does get 
kind of the fundamentals of 
communication, right? 
You have a big set of actors and anytime, 
anytime one actor interacts with another, 
that can be modeled as an edge. 
And so, this is just a very common 
paradigm to, to in, in a lot, they can 
capture the behavior of a lot of 
different kinds of systems. 
Okay. 
The other reason you see this would be so 
ubiquitous in kind of a data modeling 
aspect is that, you know, objects and 
relationships between those objects. 
You can't really get any lower than that, 
right? 
So, relations talk about you know, the 
relation data model talks about tables 
where you have records and attributes. 
But even here, there's a bit of 
complexity. 
You have to sort of think about a schema, 
and you have to sort of think about every 
record is going to have the same schema 
and so on. 
Graph's kind of blow up all that and dis, 
disintegrate everything down to just 
objects in relationships. 
And so, in some sense, it's the lowest 
common denominator data model. 
what we'll get into a little bit is my 
opinion that I think you, you throw out 
quite a bit when you sort of drop 
everything down to that level. 
But we'll talk about that in a bit. 
So, what do we want to do with these 
graphs? 
So, Bordewekar, in 2012, wrote a paper 
about analyzing analytics. 
And they tried to sort of categorize 
various analytics tasks in a variety, in 
a variety of categories, and one of the 
categories was graph analytics. 
And he broke it down into these three 
patterns, structural algorithms, 
traversal algorithms, and 
pattern-matching algorithms. 
And I think this is as good a breakdown 
as, as any other. 
So, this is the one we will use in the 
next several slides. 
So, you think about just structural 
tasks, structural algorithms. 
You know, the first thing to do when 
encountering a graph you're expected to 
work with or understand. 
It's just to just collect some basic 
metrics, right? 
How big is it? 
How many vertices and how many edges? 
And one of the takeaways I want you to 
have is that the number of edges is more 
relevant than the number of vertices. 
When you're trying to understand the 
scale of a graph. 
So, you know, many times you'll have a 
conversation with someone, and they'll 
say, well, I have this really big graph 
I'm working with. 
So, the next question you should ask is, 
how many edges, not how many bytes and 
not how many vertices. 
And the reason that you don't care about 
the bytes is because there might be all 
kinds of other information packed into 
the, the labeling of these things. 
But that can really be factored out from 
the graph itself and modeled maybe more 
traditionally in a, in a relational 
database. 
And so, the performance may not depend so 
much on exactly a number of bytes. 
But the graph structure the, is, is a 
challenge as we'll see. 
Okay. 
And so, the number of vertices is, is one 
measure but the number of edges is 
another. 
So, why is the number of edges more 
important than the number of vertices? 
Well, because it scales quadratically 
with the number of vertices, right? 
You can have at most number of vertices 
squared number of edges. 
And that's a really, really big number in 
some cases. 
Right? 
If there's two billion people using a 
social network, well two billion squared 
is the number of possible friend 
relationships you have. 
And if you're expecting to do some 
analytics on this graph, you're going to 
be processing all of those edges perhaps. 
Okay, and then second question you should 
ask, after the number of edges is, what 
is the highest in or out degree. 
As a proxy for really what is the degree 
of distribution here. 
So, what do I mean, what do I mean by 
degree? 
Well, the num, the, the in degree of a 
vertex is the number of edges that are 
coming into it. 
And the out degree of a vertex is the 
number of edges that go out of it. 
Okay, and so how the edges are 
distributed among all the vertices tends 
to be a driver of how difficult the graph 
is to work with. 
If they're all pretty evenly distributed 
then this isn't much of a problem. 
You can paralyze things as we'll see and 
everything works out nicely. 
However, very, almost never do graphs in 
the wild have this property where things 
are sort of randomly distributed. 
It tends to be very skewed. 
So, there is you know, in a social 
network, there tends to be a person whose 
is friends with everybody in the graph, 
right? 
Very, very popular people. 
Almost everybody in the graph. 
Okay? 
in a, you know, on the web there are 
pages that tend to be linked to by 
everyone right? 
Very, very popular pages. 
And so, this imbalance in the degree 
distribution is one of the challenges I'm 
working with very, very large graphs. 
And so, if you know the number of edges, 
you've got one indication of sort of 
gross scale. 
And then, if you know about how high, how 
many edges are in the you know, most 
popular vertex. 
That gives you some idea of how skewed 
things are. 
Okay. 
So, fine. 
So, when you're working with graphs, 
these are the things you're going to be 
able to do. 
Can you just count the vertexes, count 
the edges? 
Can you say given a vertex can I get the 
number of in, in edges and out edges for 
that vertex? 
And can I maybe do that for every vertex 
in the graph? 
Okay, and so this is hard to work with. 
You know, this is going to be the basis 
for, for many other tasks.