So we showed how to implement loops in 
MapReduce and optimize them and utilize 
that to implement the data log pattern 
language in recursive programs in that 
language, and we showed different 
representations of graphs. 
And now we're going to show PageRank in a 
couple of different ways at scale. 
So remember, the context here is that 
graphs are getting bigger and bigger and 
bigger. 
So you can imagine a social scale graph 
having about a billion vertices, one per 
person, with maybe 100 billion edges. 
Web scale graph is bigger, because 
there's more webpages than people, so 
maybe 50 billion vertices and a trillion 
edges. 
But there’s, you know, the human 
connectdome. 
The neural network in your brain has 
maybe 100 billion edges and 100, excuse 
me, 100 billion vertices and 100 trillion 
edges. 
So we need large scale systems to process 
this and SNAP produces one such system. 
There’s more coming down the pipe though. 
SNAP produces perhaps on the tail end of 
its utility for this massive, massive 
scale, but we're going to stick with it 
for now. 
So here's a new limitation of PageRank in 
MapReduce. 
in the map function we have a node ID and 
a vertex object. 
That vertex object has a couple of 
methods that we use. 
You can get its current PageRank, 
n.pagerank, and you can get its adjacency 
list, n.adjacencylist. 
So N dot page rank divided by the length 
of the adjacency list gives us the 
fraction of the rank that we're going to 
distribute to each of our out, out, each 
of our neighbors. 
Across each of our out edges. 
Then we're going to admit a special key 
value pair with the node I D and the 
vertex object. 
And I'll come back to that in a bit. 
And then for each of my outgoing 
neighbors Send that, send the appropriate 
fraction of my age rank, which is value p 
that we just constructed. 
[UNKNOWN] On the reduced side, we've got 
a node id m and a list of things. 
Then we initialize a couple of values, 
this M object to null and a, a new rank 
to zero. 
And then for every p in this list of p's 
we're going to check to see if its a 
vertex. 
Now why that's there is if it is a vertex 
that means it corresponds to this key 
value pair that we've mated up there. 
And all this was was a way to pass that 
complex vertex object through to the 
reducer. 
Because remember the key here is just a 
note ID So we need some way of passing 
this, this more complex object with some 
internal structure over to the reduced 
side. 
And so now we have it and we assign it to 
M. 
If it’s not a vertex then it’s one of 
these other PageRank values that we 
computed and therefore we just add it up. 
And then finally, the new PageRank For 
that vertex M, is going to be this, 
formula that we saw. 
Well, so, sorry, I guess I'm guess I'm 
being a little glib there. 
This is the damping factor that we 
mentioned. 
And this is a, equivalent expression to 
what we showed before. 
And finally now that we've constructed 
the new page rank, we emit a key value 
pair, the note ID, and the Vertex object 
itself, which is the same key value types 
as we need on the map side to repeat 
this, so we're going to run this over, 
and over, and over again, with different 
cross-multiple iterations. 
So, there's some problems with this 
implementation. 
The main one is that the entire state of 
the graph is shuffled on every iteration. 
Right, that little complex vertex object 
it includes within it the adjacency list 
associated with that vertex is sent 
across the network over to the reduced 
side and handled by the reducer. 
When all that really needs to be singed 
is just the new rank contribuions. 
If the vertex stake could sort of stay in 
place. 
If you know you could address the 
neighboring vertices directly and just 
say, hey here's your new rank 
contribution. 
That would be useful, that would save 
some communication traffic. 
And then also we have to control the 
iteration outside of MapReduce, including 
determination conditions and just the 
logic itself. 
So, for these reasons and just to explore 
programming model, Pregel was suggested. 
also at Google, are we in 2010? 
So there's been, since then there's been 
open sourcing limitations just like there 
as for Map Reduce and Apache Giraph, 
Stanford there's a system called GPS, a 
system called Jpregel, Hama. 
And this is really designed for batch 
algorithms on large graphs in particular, 
so focused on graphs, and so the basic 
logic looks something like this. 
It says, while any vertex is s, still 
active, or the max iterations have not 
been reached, for each vertex, process 
all the messages you get from your 
neighbors, update your own internal 
state, and then send messages back out to 
your neighbor. 
And then maybe set the active flag 
appropriately. 
You know, if you don't get any messages, 
then you're not active, or if your 
internal state doesn't change enough, 
you're not active, and you can control 
this logic, and so the point is now 
you're writing. 
Instead of writing a map function or a 
reduce function, you're essentially 
writing just one little function, which 
is the, the, the function that I should 
run on each vertex at every, at every 
time step. 
All right, so let's see the example, 
which is PageRank. 
So there's just one method here, compute. 
This code is a little awkward, this is 
straight from the Pregl paper, it's a 
little awkward here because it's in C, so 
bear with me if you're not used to 
looking at C. 
But this says if basically the iteration 
number is greater than or equal to one, 
this super step then add up all the 
messages I get from my neighbors and then 
assign my own internal state to this new 
calculation, the new range. 
Then as long as the super step is less 
than 30 Which is our, you know, if we go 
over 30, we're just going to assume that 
we converge and just quit. 
Then send the contribution by rank to all 
my neighbors, which is my current divided 
by n, and n is just the number of number 
of neighbors. 
Otherwise, set myself to inactive, which 
is this vote to halt, so you sort of say 
I've got no more for to do, I"m done 
until somebody wakes me up with a new 
value. 
And what's not in here in this 
implementation but is often added in a 
Pregl implementation is some kind of 
condition that says, well if the internal 
value hasn't changed by a large enough 
amount then vote to halt, then set myself 
to inactive. 
Alright. 
So let's see how this works. 
[UNKNOWN] the code and it may not be very 
clear. 
So imagine we have a graph like this. 
We initialize the rank to the total 
number of vertices divided by the number 
of, excuse me. 
The number one divided by the number 
vertices. 
So there's five vertices, so we just 
divide one by five, which is 0.2, okay. 
So that's the initial rank. 
Then we each, the program, the compute 
program runs on every vertex 
simultaneously in parallel and it sends 
its rank contribution to all of its 
neighbors, so this rank contribution of 
0.2 divided by two outgoing edges, so 
each one gives 0.1. 
And here there's three outgoing edges, so 
each one gets 0.066, and so on. 
Then on the next super step, all those 
conpr, contributions are added up, and so 
here we add 0.1 and 0.066. 
Multiply by 0.85, and add in 0.03, cause 
that's our formula, and we get 0.172. 
And we do the same for all the other 
nodes. 
Now, this one's a little funny, why did 
0.0, why did this node and this node get 
0.03? 
Well that's because they have a zero, 
they have no incoming edges at all. 
In which case, this term in the formula 
provided nothing, the sum was zero and so 
they just give 0.15 divided by 5 0.03. 
Okay, and so that's our new value, after 
that iteration. 
Then it repeats This rank is divided in 
half, 0.015 and 0.015. 
This rank is divided into thirds, 0.01, 
0.01, 0.01 and so on. 
And we see what changes. 
So, we add this up. 
This plus this times 0.85. 
Plus 0.03 gives us 0.0513 and so on and 
then I've marked these verticies as red 
because their value didn't change from on 
iteration to the next. 
And so they're marked as inactive. 
And that condition actually wasn't in the 
code that I showed you, but it's 
typically a condition you add. 
Okay. 
And so then the process continues. 
Here's the new values for the next 
generation. 
We start over again. 
one optimization here is that these 
messages aren't actually resent again. 
They can be retained on the receiving 
side you know all the incoming edges have 
a value and it doesn't necessarily need 
to be resent across the network. 
You can just sit there until it's 
updated. 
So if this, if this vertex were active it 
would be resent with a new value but 
since it's not active you just use the 
old value from the previous iteration and 
nothing needs to be sent. 
All right. 
So we recompute these. 
And we find out that this top vertex 
didn't change from one iteration to the 
other. 
So it goes red. 
And then these two values are updated 
appropriately. 
And that's our new values for the next 
iteration. 
And then finally, every, remember all the 
red nodes don't actually, all the red 
vertices don't actually get executed at 
all. 
And so they don't send any messages. 
And they don't send any messages. 
Nobody needs them. 
But this vertex still needs to be 
updated. 
And so we apply it again, and then 
finally the execution halts when all the 
vertices are inactive. 
Now it's, it might take quite a while to 
con, to converge. 
In which case, remember there's that 
super step less than 30 condition as 
well. 
So you don't really need all that, in 
general, PageRank starts to, get pretty 
close to conversion after some number of 
iterations, you don't really need to let 
it run for to long.