[MUSIC]. 
So we talked about a couple different 
notions of centrality, and one more is 
degree centrality, which is just the 
degree of a vertex divided by the total 
number of edges, right? 
So this is the fraction of all the edges 
that touch me. 
Okay? 
And so imagine, this, so maybe this is a 
good candidate for our, you know, we're 
seeking some notion of importance in the 
vertex of a graph. 
All right. 
So imagine we have a social network and, 
you know, then the degree of a vertex is 
the number of friends you might have. 
Well, the people with more friends are in 
some sense, some sense more important 
than people with fewer friends in the 
context of a social network. 
Fine. 
But if, you know, say we both have five 
friends. 
Well, then we have the same degree 
centrality by this definition, but what 
if your five friends are, they 
themselves, much more connected than my 
five friends? 
In some sense, you should be more 
important than I am in the context of 
this social network, and the notion of 
this degree centrality doesn't capture 
that. 
All right? 
So, let's see if we can improve on this. 
Well, another notion of centrality is 
Eigenvector Centrality, which is actually 
just PageRank. 
And so if you are, are familiar with 
PageRank, or this may just be another way 
of looking at it, if you're not familiar 
with PageRank, then this is a great way 
to develop an intuition for it. 
So the basic idea for computing PageRank 
is, you know, while things are not 
converged, for each vertex in a, in the 
graph. 
Compute the rank of that vertex by adding 
up the ranks of all of its neighbor 
vertices, all the incoming edges that we 
see in the directed graph. 
Right, so this allows you to say well, 
look, if Barack Obama, if the president 
of the United States is connected to you 
by one hop, he's your friend. 
Say, follows you on Twitter or something 
like that. 
Well then, you're more important than 
somebody who doesn't have such a, such an 
influential person to grab. 
You add up the rank of the president to 
your rank, okay? 
Meanwhile, you distribute your rank to 
all your friends, right. 
So, and you do this, you repeat this 
passing of, of rank, of wait, of 
importance to across the network, across 
the graph until you reach some 
convergence condition. 
And then that convergence condition gives 
you a relative score of whose more 
important than who, perhaps, which, which 
vertex is more important than which other 
vertex. 
But there's a couple of problems with 
this approach. 
So one is, you know, up one page or one 
person in a social network with millions 
of outgoing links, if they link to me, 
that's somehow less valuable than a page 
that only links to a few people. 
Right? 
So if you've got one of these crawlers 
that follow everyone in order to collect 
as much, follow everyone on Twitter, in 
order to collect as much data as 
possible. 
It's not very important that they follow 
you, right? 
You don't consider that to be very 
prestigious that you have some automatic 
robot crawler following you. 
Meanwhile, if you let an aggregator page 
that sort links out to everyone on the 
internet as similarly that's not very 
important that it links to you. 
So somehow you want to make sure that 
they divide their rank amongst all their 
outgoing edges as opposed to just give 
their total rank to each outgoing edge. 
Fine. 
So that's easy to fix. 
You know, another notion here is that, 
well, if I'm, if I'm 27 hops away from 
Barack Obama, that's less important than 
if I'm one hop away. 
And so, we, we really shouldn't count 
that as very influential. 
And so, we need some sort of a damping 
factor that, as you get further away, it 
sort of lowers the importance. 
Okay? 
So you combine these two definitions 
together and you get the definition of 
PageRank, as it was published and there's 
a couple of variations on this, but, this 
is the one to know. 
Okay? 
So while not converged, the rank of, of a 
vertex A, is the sum of all the ranks of 
the vertices that link to A. 
But each one is divided by the total 
number of outgoing edges. 
So, in this notation, we assume that 
there are edges B linking to A, C linking 
to A, D linking to A. 
And PR of A, the PageRank of a no, of a 
vertex X is the, is going to be the 
PageRank of the vertex X, L of X is the 
number of outgoing links from X. 
And so, for the page, we take the 
PageRank of B and divide by the number of 
outgoing links from B. 
Take the PageRank of C, divide by the 
number of outgoing links away from C and 
so on. 
Add all that up, and that's all the 
contribution to A. 
And then we multiply by a damping factor 
to make sure that we, what we pass on 
goes, diminishes over time as we get 
further and further away, and then this 
other term in this expression is just to 
ensure that all the ranks sum up to one. 
So that we can sort of interpret them as 
probabilities. 
And in fact, you can directly interpret 
this as probability which is another way 
of look at PageRank and deriving PageRank 
is to talk random walks around the, 
around the internet, around the, around 
the graph. 
Right, so you start on a random vertex 
and just start walking. 
Should make a choice at random among the 
edges, the outgoing edges, and just 
traverse around. 
Well, if you do this a bunch of times, 
you can derive how likely it is that 
you'll spend time on some particular 
vertex versus some other particular 
vertex, and that will exactly be the 
PageRank. 
And so this is sort of, you know, all 
roads lead back to Wikipedia or CNN or 
some other very, you know, important 
vertex in the web graph. 
So that's PageRank and what I want to 
point out before we move on is just the 
relative simplicity of this, right? 
It really comes out of an intuitive 
notion of trying to figure out how can we 
measure the importance of a vertex in the 
graph? 
And so, you know, you start from very 
simple notions of, well, maybe important 
means just the one with the highest 
number of edges that link to it. 
Well, there's some problems with that, so 
let's see if we can fix it. 
Maybe it's the one with the the most 
number of paths that go through it. 
I mean we don't care about all paths, we 
care about shortest paths so that gives 
you another notion of importance. 
And you say, well, that's got some 
problems too, what are the properties we 
really want here? 
Well, maybe it kind of captures the 
importance of your friends need to be 
added in there somehow and you can sort 
of walk through this and come up with 
where PageRank came from. 
So the way it's presented, just like a 
lot of these things, are presented in 
terms of a, of a finished formula and 
then you kind of have to work out back, 
you know, reverse engineer where it came 
from. 
But a lot of these things are developed 
very intuitively and the formula is only 
used as a notion to express to intuition 
in a, in a precise way.