When you look at a real world network such
as my facebook network its clear that the
nodes with high closeness are close to
other nodes with high closeness that is
they are kind of in the middle in the
thick of things and in general we may want
a definition of closeness a separate
centrality measure which we are going to
call eigenvector centrality which sells
that you are.
As important as your neighbors are.
And your neighbors are as important as
their neighbors are.
So it's this nice recursive definition.
So if we have node I, and we have its
neighbors and the weights of the edges.
Then the importance of I is going to be
the sum of these kinds of terms, where we
take the weight of that edge.
And, you know, normally, it's, it's one,
But you can use weighted networks as well.
 whatever the centrality of that node is.
And you may iterate this many, many times.
Because, of course, as you're calculating
this.
Centrality for I its going to actually now
affect the centrality of K etc and this is
precisely the problem of solving for the
eigenvector of the adjacent signature X
with eigen value one and thats why its
called eigen vector centrality.
One of the first people to apply
eigenvector's centrality to social
networks was Bonachich.
He wasn't happy with just, you know, the
plane agency matrix.
He wanted a parameter that he could vary,
and he chose this parameter beta.
And what beta does is it says, "How
important it is, is it, that your."
Neighbours are important versus just how
many neighbours you have.
So, he was able to tune that.
And this paramether alpha here, is just a
normalization constant.
So, you have that this entrallity of node
I, for a certain paramether beta, is the
sum over all of its neighbours, which you
are going to get from, from this.
The adjacency matrix is, can be weighted
or not.
And.
For each of those neighbors you're going
to have this factor of alpha plus beta
times the eigenvector centrality of the
neighbor.
And this can be solved through a matrix
computation to derive the eigenvector
centrality scores for all the nodes.
Now you don't have to sit there and, you
know, calculate this by hand, that could
get really hairy.
Naturally, you know, a lot of software can
calculate these, these kinds of things for
you, but it's good to know where it comes
from.
What the, what the idea be.
Kind having such, su such a centrality
measure is.
And so, if you have small beta, what
happens is, you know, beta close to zero.
Is that only your immediate friends are
going to matter.
So it's going to be, how many friends you
have as opposed to how important they are.
Because their importance is derived from
the structure of the wider network.
If you have high beta, you're going to
have low attenuation.
Meaning that, all of those multiple steps
are going to be quite important.
It's not just how important your friends
are, but also how important their friends
are.
The friends of friends of friends,
Etc. And in the case that beta is zero,
you're just recovering the, the degree
centrality because all you have is the sum
of the edges for a note.
The interesting thing that Bonacich
started examining was what happens if beta
is actually negative?
So when Beta is positive The centrality
follows the intuition I said, which is
that.
Having neighbors who are themselves
important, makes you important.
However, if beta is negative, nodes have
higher centrality when they're connected
to actually less central nodes.
So let's see if this made sense to you.
Take a look at these two networks, and try
to figure out which one has beta positive,
and which one has beta negative.
So far, with the exception of degree,
where we had in-degree and out-degree, we
were talking primarily about undirected
networks.
And, I just want.
Want to take a little bit of time to talk
about centrality and directive matter.
.
There naturally are many different
directed networks.
For example, the World Wide Web.
And we mentioned how.
You know, the meaning of out degree, how
many different pages a page points to is
really different from the meaning of in
degree, how many pages point to it.
So, out degree just indicates okay, is
this page referencing a lot of different
content.
In degree.
Is a signal of how many other people found
that content relevant enough so to link to
that page from their page.
Foodweb's naturally directed right.
The wolf leads the sheep.
Not visa versa.
Population dynamics where individuals
migrate right.
Migration patterns are usually directed.
Influence.
How much you influence someone is probably
different from how much they influence
you.
And it depends on your relative prestige
and the nature of the relationship.
Relationship.
Hereditary networks, citation networks,
biological networks, such as transcription
regulation networks, or neural networks
are also directed.
And it makes a lot sense if you have a
task to do then some nodes are going to
effect the behavior of other nodes and the
network it's directed.
Undirected you know, things would be just
firing back and forth.
Some of the measures are just naturally
extended into their directed counterparts.
So if you remember when we talked about
betweenness this was simply the number of
paths between all the other pairs of nodes
that pass through our node of interest
divided by the total number of paths pairs
have.
And what we're going to do we're just
going to change it we're going to say
instead of undirected paths these are
going to be directed paths and.
And when we normalize, we're going to
have, here.
N - one x N - two And we're going to lose
that factor of two, because getting from A
to B can in fact be.
Or actually here from K to G can be
different than getting back to K from J.
Right so, we do need to take into account
the directionality of the path, but pretty
much directed between as follows it's
undirected counterpart.
Same thing with closeness centrality, you
can talk about in closeness or out
closeness and typically you will only
consider vertices that are reachable.
So this is kind of getting, cuz once you
have a directed network it's even more
difficult for everything to be connected
cuz if you have the same number of edges
and they're directed you, you.
Here in fact and you can only traverse
them in one direction right.
You have about half the number of edges.
So perhaps you're only calculating
closeness forward from the reachable nodes
and here you, you know, you have the kind
of input domain are going to be all the
nodes that can reach you.
And the question is going to be how many
hops does it take and kind of the output
domain are all the nodes reach in outward
fashion.
So then again um..
It's very easily extended, where.
Things get really I don't know if, if
interesting is the right word, but where
there is a really a big, game change when,
when you added directionality to
eigenvector centrality.
And this was applied by Larry Page and
Sergey Brin when they were graduate
students at Stanford to the web.
They just said we're going to figure out
how important each web page is and we're
not going to take just the, The number of
other pages that point to it.
We're going to instead look at the
importance of those pages in a recursive
way.
And so, for example, here, at least at
that time, Slashdot was really important.
Lots and lots of other pages pointed to
it.
So it's enough for Slashdot, to link to
mention another page and oftentimes that
web server would just be brought down from
all the traffic and attention that would
ensue and so we really want to capture
this.
It's not just random web pages that link
to you but whether those pages themselves
are important.
Now there's a, there's an analogy here,
which is that when you're calculating this
eigenvector it's as if you're doing a
random walk.
And so I like to think of it as a drunk,
who's kind of like wandering around, and
every time he hits a node, he says, oop, ,
okay, I'm just going to turn left, and,
turn right, and so, he's just following,
edges at random.
And what page rank being, the amount of
time that he is going to spend at each
node, What it.
Then corresponds to is the eigenvector of,
of the adjacency matrix.
But, there's a very important tweak.
If this.
Network, say the web was undirected.
The drunk could just kinda, you know go
and then just go back the same way if he
gets stuck somewhere but when the network
is directed, he can only follow the edges
in a certain direction, meaning that here,
if there is a cycle of this sort, he would
just be trapped and circling here
indefinitely which then means that you
actually can't compute the eigenvector,
right because the, the.
You're a random walker, you're drug is
actually being absorbed in, in different
parts of the network.
So the very cool insight that, these two
guys, Page and Brinn had was to allow for
random teleportation.
Which is that with some probability the
drunk is going to follow an edge when he
arrives at a node.
But with 1- that probabilty, he's just
going to teleport to a random node in the
graph.
And this solves the problem of getting
stuck and.
But it still captures this, you know the,
the important pages are the ones that are
linked to by important pages, so great.
So let's see what this would look like on
a simple toy network.
Let's see the random walker starts at node
one.
At the next step he, with, you know some
substantial probability will go to either
seven or eight, but we also have a twenty%
teleportation probability which means that
the 80% of going to seven and eight will
be evenly split between them so.
If we start out with you know, ten units
to distribute we get four each at seven
and eight but we also distributed
twenty percent evenly among all the nodes
including node one.
And so after the first step we have most
of the probability being at seven and
eight but also he could have teleported
elsewhere in the network.
If we go on and look at what happens after
ten steps you find that.
You know, there is a lot of probability
around seven.
And this indeed makes sense because seven
not only has high indegree but some of
those nodes like two and five and six
actually have other nodes feeding into
them.
And so recursively seven should have high
paytrank.
To check your understanding, I would like
you to go to this paytrenk demo where you
will be moving a slider to Adjust the
teleportation probability, and then you're
going to iterate.
So you're going to distribute the
probability, kind of like with each step
that the random walker might take.
And then I'd like you to figure out
whether higher or lower teleportation
probability leads to more equal or less
equal distribution of page ranks
centrality scores.
Just to wrap up for now.
We've seen lots and lots of definitions of
different centrality values.
We had degree.
We had betweenness.
We had closeness.
We had Iconfactory centrality.
And we even had sort of network wide
measures of centralization.
Does everyone have approximately the same
degree or is it really scute.
We extended this to directed networks.
To see, you know, when, when direction
matters, how do these centrality measures
translate and.
What might be missing from all of this
actually is an understanding of, you know,
what is this good for?
I mean sometimes it's true.
It's just nice to look at a network and
say, oh, here are the central nodes.
For example you can do this with the Enron
email network that was released, as part
of the court proceedings, and, you know,
you can, you can infer who the top level
management was simply because of their
high centrality.
Trivial because you know sometimes the
very top people don't email the most.
Sometimes the people who are very central
are the ones who kind of handle email on
their behalf or in charge of their
calender, so there are lots of interesting
things to explore if you wanna do
exploratory data analysis.
But, if you are Oh and I should say, in
the assignment you'll be looking at
actually a court case network.
And this is an anti trust case where
several turbine and other kind of powered
generator equipment manufacturers were
accused of basically colluding.
Doing price setting.
And the question is how does an
individual's.
Position in this collusion network
correlate with their probability of, or
actually their, their outcome.
That is, whether they were convicted or
not and how heavy their sentence was.
So that's kind of cool, right?
If you could ahead of time figure out how
things will play out for a conspiracy
network.
The other paper that you'll be looking at
is well it's this remarkable data set that
Sinan Aral and Marshall VanAlstyne
collected of personnel in a headhunting
firm.
And, what they discovered was that it
didn't matter how fat your rolodex is, its
how many peoples addresses you know.
That it's in fact your positioning in the
network, the diversity of your contacts,
having less constraints, that correlates
both with your performance, that is how
much money you bring into the company, and
interestingly with the information that
reaches you.
Whether you find out new information more
quickly than your colleagues do.
I hope that those two papers which will be
part of your assignment, will be
interesting.
And in the next video what I'll do is just
talk about some research I've done and how
I've made use of centrality measures in a
very practical way.