[MUSIC]. 
All right. 
I want to give quick aside on 
representing graphs. 
We've sort of been assuming implicitly 
that we're representing graphs in this 
way with a table with two columns, one 
source and one target, maybe some other 
columns representing, for example, an 
edge label. 
But every edge will be explicitly 
represented. 
Okay. 
And so this makes sense because it's easy 
to manipulate with a relational language, 
which is what we've been sort of talking 
about in terms of pattern matching tasks. 
And so this is the edge table. 
We'll call this the edge table 
representation of this graph. 
Here, where a and b is there, and b back 
to a is there, and so on, okay? 
And you can process this as we've seen. 
We can do pattern matching, but we can 
also do the structural tasks pretty 
simply. 
We can say, find the top five highest 
n-degree vertices, using a GROUP BY 
query, right? 
For, fr-, from this edge table For each 
target, count up the number of sources. 
Group by target and then select the top 
five from that. 
And this is using the syntax for top five 
from the sequel standard as well as 
Microsoft sequel server, other commercial 
databases use, can express this in a 
slightly different way. 
Okay, and the, you have to order by the 
incount here, which is why we did this as 
a nested query. 
So fine, so this table gives us a lot of 
flexibility in how to process it. 
But there's some cost that we bear to do 
this. 
And what you actually see more often in 
programming language libraries for 
working with graphs. 
It's an adjacency list representation. 
And so for here for each source it's, 
each source is associated with a list of 
all the adjacent vertices. 
So here with a you would be associated 
with list of vertices b and f. 
And b would be associated with the list 
a, d, e and f and everything's one hop 
away, okay. 
And so this, the overall space required 
for this representation is less, which 
can make a pretty big difference in 
performance. 
So as an example, of how to use this 
representation you can think about a 
MapReduce program. 
It's a little bit harder to think about 
how to do this in a relational database, 
for example, because you can't, without 
directly and naturally, you can't express 
this, list construct. 
There is various extensions and proposals 
and so what to do this, but this 
essentially breaks first normal form 
which I won't go into but it's no longer 
really a conventional relationship. 
If you have this nested collection 
structure as one of the values. 
But in Map Reduce it's perfectly fine, we 
saw this before right, there is a key and 
a value and the value can be anything. 
It can be a bag of words. 
In this case it's a list of neighboring 
vertices. 
And in fact, in the libraries for 
MapReduce that work with graphs, this is 
the most common representation you'll 
see. 
And in fact, in the, with some of the 
original work with MapReduce to express 
pageRank, which we'll talk about in a 
bit, they assume [INAUDIBLE] as well. 
So for this same task of finding the top 
five highest in degree vertices you can 
imagine a map program that takes in a 
vertex and adjacency list, and produces a 
key of the adjacent vertex along with the 
key vertex, so you just reverse the 
direction. 
So for, for b and f the output would be b 
mapping back to a, f mapping back to a 
and so on, we just reverse the edges, and 
then on the reduce side it'll receive a 
list, a vertex along with a list of 
incoming edges, and then you can just 
count them up. 
And produce that as your result. 
Excuse me, you can count them up and 
produce that as your result. 
One final step, is to take the top five, 
which would actually be a second map 
reduce job. 
So the last representation you'll 
typically see. 
Is an adjacency matrix, and this is 
really only useful if you have a fast 
efficient representation of matrices, and 
you're trying to manipulate the graph as 
a matrix, but these things exist and the 
other nice thing about this is it sort of 
exposes the equivalence. 
Of a graph and a square matrix, right? 
So, a square matrix has all the same 
number of rows and columns. 
So, how do I present a graph as a square 
matrix is, for each row, each row 
corresponds to one vertex, and each 
column corresponds to one vertex, and you 
put a one in that cell if vertex row is 
adjacent to vertex column. 
Okay? 
And if you have a undirected graph then 
you'll have, then this will be symmetric, 
and if it's a directed graph then it may 
not be. 
So a is adjacent to b which is why 
there's a one here. 
And b is adjacent to a which is why 
there's a one here. 
But b is adjacent to d, and d is not 
adjacent to b. 
And you'll also see that this is always 
going to be, pretty much always going to 
be a sparse graph, right? 
Lots and lots and lots of zeros. 
Not everything, it's rare for a vertex to 
be, for all vertices to be connected to 
almost everything. 
So you have sparse, and when you, if you 
remember back to the, to some of the work 
we did with relational databases, we 
showed how to represent matrices in 
databases, that, once you have a matrix, 
you get access to processing things with 
linear algebra. 
And you might get access to fast 
libraries that already know how to work 
with. 
Matrices in linear algebra operations. 
But what a lot of those libraries do 
under the sheets is take a sparse matrix 
and represent it in a way that doesn't 
require to actually materialize all these 
zeros. 
And those sparse representations are 
going to look a lot like the previous two 
representations we just saw. 
An adjacency list, or an edge relation. 
So in some sense it's, you're moving 
things into matrices in order to give 
them access to fast libraries for working 
with matrices, but what the matrices are 
doing underneath the sheets is to 
represent things in a sparse way that 
looks back, looks more like a relational 
representation. 
But be aware of all three of these; an 
edge table, an adjacency list and an 
adjacency matrix.