0:08

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.

Â