This course will introduce the learner to network analysis through tutorials using the NetworkX library. The course begins with an understanding of what network analysis is and motivations for why we might model phenomena as networks. The second week introduces the concept of connectivity and network robustness. The third week will explore ways of measuring the importance or centrality of a node in a network. The final week will explore the evolution of networks over time and cover models of network generation and the link prediction problem. This course should be taken after: Introduction to Data Science in Python, Applied Plotting, Charting & Data Representation in Python, and Applied Machine Learning in Python.
Centrality Examples
Loading...
From the course by University of Michigan
Applied Social Network Analysis in Python
537 оценки
University of Michigan
537 оценки
Course 5 of 5 in the Specialization Applied Data Science with Python
From the lesson
Influence Measures and Network Centralization
In Module Three, you'll explore ways of measuring the importance or centrality of a node in a network, using measures such as Degree, Closeness, and Betweenness centrality, Page Rank, and Hubs and Authorities. You'll learn about the assumptions each measure makes, the algorithms we can use to compute them, and the different functions available on NetworkX to measure centrality. In the assignment, you'll practice choosing the most appropriate centrality measure on a real-world setting.
Meet the Instructors
Daniel RomeroAssistant Professor
School of Information
Now that we've seen a number of different ways of
finding central nodes in a network, today,
we're going to look at an example where we compare
how the different centrality measures that we've looked at, rank nodes differently.
And so, we're going to be looking at this particular network and we're going
to run the different algorithms that we looked at on this particular network.
And so, let's start with the most basic way of
thinking about centrality in a network and that is your in-degree.
How many nodes point to you?
If we use this measure on this network,
what we would be able to say is that nodes one and six have the highest in-degree,
so they are the most central.
They have in-degree of four and then all the other nodes are,
sort of, second, because all the other nodes have in-degree two.
So, the in-degree centrality is only able to say that
nodes one and six are sort of the most central and everything else is the same.
And so, I'm going to be looking at all the other measures,
and just like I did for in-degree,
I'm going to be putting the nodes ranked by highest to lowest and I'm
going to be using red lines to indicate when the ties break.
So, in this example,
nodes one and six are the most central nodes,
and then everything else comes second.
And I'll indicate that using this red line here.
So now, let's look at closeness centrality.
Just remember that closeness centrality says that nodes who are
central are a short distance away from all the other nodes in the network.
And so, using this measure,
we'll find that five is the most central node.
And you can see that this is kind of natural.
This seems to make sense because five is sort of in the middle of everything.
Right? So, in order to get from five to any other node,
you're already kind of close to it compared to if you were in node,
for example, three or four,
and you wanted to reach nodes eight and nine,
then you have to kind of go through a large number of steps.
And so, it makes sense that five is sort of towards
the middle and has the highest closeness centrality.
Then, nodes one and six will come next.
And again, they are also sort of central,
not as central as five,
but they're also in the middle of the whole thing.
And then, next are nodes two, three, seven, and eight.
Closeness centrality is not able to distinguish between,
for example, nodes two and three.
And that is because, well,
both nodes two and three can reach node four in just one step.
And to reach all the other nodes,
both two and three would first hop to node one
and they both can do that in one step and then go to all the other nodes.
So, in terms of how many steps it takes to go from
node two and three to any other node in the network, there is no difference.
However, if you kind of look closely,
there is a structural difference between nodes two and three.
Right? For example, node two is sort of in the path between nodes,
say, one, five, and six, and node four.
That is, if you wanted to go from node five to four,
then you would have to do that through node two.
You wouldn't go through node three.
So in this sense, node two seems to be more important than
node three but closeness centrality is not able to capture this.
And last, for closeness centrality,
would come nodes four and nine.
And that is because if you notice,
node four does not link to node two.
So, if node four wants to reach node two,
it would have to go through node three.
So, it would have to go four, three, and then two.
Whereas, node three, it can directly reach node two and that's why
four has a lower closeness centrality than node three.
Next, we'll look at betweenness and as a reminder,
betweenness says that central nodes are those that show up
in the shortest paths between different pairs of nodes in the network.
And so, the node with the highest betweenness is node five.
And again, this makes sense.
It's pretty central in that word.
You can kind of tell that five does show
up in the shortest path between many pairs of nodes.
And then, next will come one and six just like with closeness.
And again, this makes sense.
Then, come two and seven.
And so, unlike closeness centrality,
betweenness is able to capture the fact that actually two is
in a kind of key position compared to three because if nodes one,
five, six, seven, eight, and nine want to reach four,
then they have to go through node two,
not through node three.
And so, the next nodes are two and seven,
then three and eight,
and then finally four and nine.
So, betweenness comes out very similar to closeness but
betweenness is able to capture those structural differences between nodes two and three,
whereas, closeness centrality does not.
Next, let's look at PageRank.
And again, PageRank has these useful interpretation,
which says that nodes who are central are the ones that,
if you were to take a random walk on this network,
then you would pass by them a lot or you would end up landing on them a lot.
And so, the nodes with the highest PageRank in
this network are nodes one and six and then node five.
So, unlike betweenness, which says that five is the most central node,
PageRank has one and six and then five.
Now, why these may be?
Well, if you notice,
node five here gives all its PageRank to nodes one and six,
whereas, nodes one and six give some of their PageRank to node five,
but they also give to other nodes.
So, this is part of the reason why node five comes second to one and six.
And then, you have the exact same thing.
You have two, seven, three, eight and four, nine..
So, in this case, PageRank comes out very similar to
betweenness but it flips the nodes one and six and five.
Now, lets look at the authority scores from
the HITS algorithm that computes authority and hub scores for every node.This,
just like PageRank, puts one and six at the top and then,
come nodes four and nine,
which is kind of surprising at first.
Right? Because you would imagine, "Well,
what happened to node five and what happened to nodes two and seven,
which are clearly central in this network?
Why are they not coming before four and nine?"
And we'll see that in a minute.
But for the authority score,
next you have nodes three and eight, two,
seven, and then finally,
you have node five.
So, the node with the lowest authority score here is five
even though for many of the other centrality measures,
it had a very high centrality.
So, why may this be the case?
Well, if you remember,
the HITS algorithm gives every node an authority score and a hub score.
And so, in order to kind of understand what the HITS algorithm is saying,
you have to kind of look at those scores together.
And so, what happens is that,
when you look at the hub scores of this network, two, five,
and seven which were the nodes that we're
kind of wondering why they wouldn't have high centrality, high authority.
Well, its because they have high hub score.
So the way that the HITS algorithm analyzes a network is that,
it says that the authorities are one and six and two, five,
and seven are the nodes with a very high hub score.
So, to interpret the scores,
you really have to take them together.
And then, next will come three and eight, four and nine,
and one and six.
And so, what we see here is that,
all of these measures sort of give different rankings,
although there are some commonalities.
So, they all have nodes one, five,
and six with high scores, generally.
But there are some differences as well.
So, if we summarize, we find that in this example,
no pair of centrality measures produces
the exact same ranking but there are some commonalities,
so you are able to pick out some of the nodes that are very central.
Of course, the centrality measures make
different assumptions about what it means to be a central node.
And so, that's why they produce different rankings.
And to figure out what the best centrality measure is,
really depends on the context of the network that you're analyzing.
And usually, the best thing to do to identify central nodes is to take up
multiples centrality measures and figure out which nodes come out
central in many of them rather than relying on a single one to do this.
And so, I hope this gives you some context into how
these different centrality measures compare
and look at the differences between them as well.
And that's all for this video and we'll see you next time.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
