1
23:59:59,932 --> 00:00:05,577
[MUSIC]. 

2
00:00:05,577 --> 00:00:07,194
All right. 
I want to give quick aside on 

3
00:00:07,194 --> 00:00:10,593
representing graphs. 
We've sort of been assuming implicitly 

4
00:00:10,593 --> 00:00:14,497
that we're representing graphs in this 
way with a table with two columns, one 

5
00:00:14,497 --> 00:00:18,523
source and one target, maybe some other 
columns representing, for example, an 

6
00:00:18,523 --> 00:00:23,043
edge label. 
But every edge will be explicitly 

7
00:00:23,043 --> 00:00:25,300
represented. 
Okay. 

8
00:00:25,300 --> 00:00:30,130
And so this makes sense because it's easy 
to manipulate with a relational language, 

9
00:00:30,130 --> 00:00:36,760
which is what we've been sort of talking 
about in terms of pattern matching tasks. 

10
00:00:36,760 --> 00:00:39,485
And so this is the edge table. 
We'll call this the edge table 

11
00:00:39,485 --> 00:00:44,406
representation of this graph. 
Here, where a and b is there, and b back 

12
00:00:44,406 --> 00:00:50,210
to a is there, and so on, okay? 
And you can process this as we've seen. 

13
00:00:50,210 --> 00:00:52,589
We can do pattern matching, but we can 
also do the structural tasks pretty 

14
00:00:52,589 --> 00:00:55,150
simply. 
We can say, find the top five highest 

15
00:00:55,150 --> 00:00:58,400
n-degree vertices, using a GROUP BY 
query, right? 

16
00:00:58,400 --> 00:01:05,330
For, fr-, from this edge table For each 
target, count up the number of sources. 

17
00:01:05,330 --> 00:01:09,170
Group by target and then select the top 
five from that. 

18
00:01:09,170 --> 00:01:13,930
And this is using the syntax for top five 
from the sequel standard as well as 

19
00:01:13,930 --> 00:01:18,620
Microsoft sequel server, other commercial 
databases use, can express this in a 

20
00:01:18,620 --> 00:01:23,900
slightly different way. 
Okay, and the, you have to order by the 

21
00:01:23,900 --> 00:01:26,960
incount here, which is why we did this as 
a nested query. 

22
00:01:26,960 --> 00:01:30,555
So fine, so this table gives us a lot of 
flexibility in how to process it. 

23
00:01:30,555 --> 00:01:35,520
But there's some cost that we bear to do 
this. 

24
00:01:35,520 --> 00:01:39,363
And what you actually see more often in 
programming language libraries for 

25
00:01:39,363 --> 00:01:44,050
working with graphs. 
It's an adjacency list representation. 

26
00:01:44,050 --> 00:01:49,531
And so for here for each source it's, 
each source is associated with a list of 

27
00:01:49,531 --> 00:01:55,378
all the adjacent vertices. 
So here with a you would be associated 

28
00:01:55,378 --> 00:02:00,854
with list of vertices b and f. 
And b would be associated with the list 

29
00:02:00,854 --> 00:02:06,050
a, d, e and f and everything's one hop 
away, okay. 

30
00:02:06,050 --> 00:02:09,878
And so this, the overall space required 
for this representation is less, which 

31
00:02:09,878 --> 00:02:13,500
can make a pretty big difference in 
performance. 

32
00:02:19,000 --> 00:02:23,012
So as an example, of how to use this 
representation you can think about a 

33
00:02:23,012 --> 00:02:28,628
MapReduce program. 
It's a little bit harder to think about 

34
00:02:28,628 --> 00:02:34,030
how to do this in a relational database, 
for example, because you can't, without 

35
00:02:34,030 --> 00:02:40,510
directly and naturally, you can't express 
this, list construct. 

36
00:02:40,510 --> 00:02:43,804
There is various extensions and proposals 
and so what to do this, but this 

37
00:02:43,804 --> 00:02:47,260
essentially breaks first normal form 
which I won't go into but it's no longer 

38
00:02:47,260 --> 00:02:52,171
really a conventional relationship. 
If you have this nested collection 

39
00:02:52,171 --> 00:02:55,312
structure as one of the values. 
But in Map Reduce it's perfectly fine, we 

40
00:02:55,312 --> 00:02:58,720
saw this before right, there is a key and 
a value and the value can be anything. 

41
00:02:58,720 --> 00:03:01,826
It can be a bag of words. 
In this case it's a list of neighboring 

42
00:03:01,826 --> 00:03:05,824
vertices. 
And in fact, in the libraries for 

43
00:03:05,824 --> 00:03:10,648
MapReduce that work with graphs, this is 
the most common representation you'll 

44
00:03:10,648 --> 00:03:14,789
see. 
And in fact, in the, with some of the 

45
00:03:14,789 --> 00:03:18,754
original work with MapReduce to express 
pageRank, which we'll talk about in a 

46
00:03:18,754 --> 00:03:25,794
bit, they assume [INAUDIBLE] as well. 
So for this same task of finding the top 

47
00:03:25,794 --> 00:03:30,960
five highest in degree vertices you can 
imagine a map program that takes in a 

48
00:03:30,960 --> 00:03:36,618
vertex and adjacency list, and produces a 
key of the adjacent vertex along with the 

49
00:03:36,618 --> 00:03:43,875
key vertex, so you just reverse the 
direction. 

50
00:03:43,875 --> 00:03:48,694
So for, for b and f the output would be b 
mapping back to a, f mapping back to a 

51
00:03:48,694 --> 00:03:53,829
and so on, we just reverse the edges, and 
then on the reduce side it'll receive a 

52
00:03:53,829 --> 00:03:58,490
list, a vertex along with a list of 
incoming edges, and then you can just 

53
00:03:58,490 --> 00:04:07,587
count them up. 
And produce that as your result. 

54
00:04:07,587 --> 00:04:12,550
Excuse me, you can count them up and 
produce that as your result. 

55
00:04:12,550 --> 00:04:15,402
One final step, is to take the top five, 
which would actually be a second map 

56
00:04:15,402 --> 00:04:20,541
reduce job. 
So the last representation you'll 

57
00:04:20,541 --> 00:04:24,094
typically see. 
Is an adjacency matrix, and this is 

58
00:04:24,094 --> 00:04:29,521
really only useful if you have a fast 
efficient representation of matrices, and 

59
00:04:29,521 --> 00:04:34,948
you're trying to manipulate the graph as 
a matrix, but these things exist and the 

60
00:04:34,948 --> 00:04:43,660
other nice thing about this is it sort of 
exposes the equivalence. 

61
00:04:43,660 --> 00:04:50,360
Of a graph and a square matrix, right? 
So, a square matrix has all the same 

62
00:04:50,360 --> 00:04:55,681
number of rows and columns. 
So, how do I present a graph as a square 

63
00:04:55,681 --> 00:05:00,241
matrix is, for each row, each row 
corresponds to one vertex, and each 

64
00:05:00,241 --> 00:05:05,441
column corresponds to one vertex, and you 
put a one in that cell if vertex row is 

65
00:05:05,441 --> 00:05:13,590
adjacent to vertex column. 
Okay? 

66
00:05:13,590 --> 00:05:16,739
And if you have a undirected graph then 
you'll have, then this will be symmetric, 

67
00:05:16,739 --> 00:05:19,810
and if it's a directed graph then it may 
not be. 

68
00:05:19,810 --> 00:05:24,210
So a is adjacent to b which is why 
there's a one here. 

69
00:05:24,210 --> 00:05:27,150
And b is adjacent to a which is why 
there's a one here. 

70
00:05:27,150 --> 00:05:31,180
But b is adjacent to d, and d is not 
adjacent to b. 

71
00:05:31,180 --> 00:05:35,877
And you'll also see that this is always 
going to be, pretty much always going to 

72
00:05:35,877 --> 00:05:40,590
be a sparse graph, right? 
Lots and lots and lots of zeros. 

73
00:05:40,590 --> 00:05:44,220
Not everything, it's rare for a vertex to 
be, for all vertices to be connected to 

74
00:05:44,220 --> 00:05:51,404
almost everything. 
So you have sparse, and when you, if you 

75
00:05:51,404 --> 00:05:54,732
remember back to the, to some of the work 
we did with relational databases, we 

76
00:05:54,732 --> 00:05:58,060
showed how to represent matrices in 
databases, that, once you have a matrix, 

77
00:05:58,060 --> 00:06:02,956
you get access to processing things with 
linear algebra. 

78
00:06:02,956 --> 00:06:06,024
And you might get access to fast 
libraries that already know how to work 

79
00:06:06,024 --> 00:06:09,380
with. 
Matrices in linear algebra operations. 

80
00:06:09,380 --> 00:06:13,038
But what a lot of those libraries do 
under the sheets is take a sparse matrix 

81
00:06:13,038 --> 00:06:16,991
and represent it in a way that doesn't 
require to actually materialize all these 

82
00:06:16,991 --> 00:06:21,500
zeros. 
And those sparse representations are 

83
00:06:21,500 --> 00:06:25,730
going to look a lot like the previous two 
representations we just saw. 

84
00:06:25,730 --> 00:06:29,995
An adjacency list, or an edge relation. 
So in some sense it's, you're moving 

85
00:06:29,995 --> 00:06:33,757
things into matrices in order to give 
them access to fast libraries for working 

86
00:06:33,757 --> 00:06:37,291
with matrices, but what the matrices are 
doing underneath the sheets is to 

87
00:06:37,291 --> 00:06:40,996
represent things in a sparse way that 
looks back, looks more like a relational 

88
00:06:40,996 --> 00:06:48,880
representation. 
But be aware of all three of these; an 

89
00:06:48,880 --> 00:06:51,760
edge table, an adjacency list and an 
adjacency matrix.