1
00:00:08,270 --> 00:00:11,130
Now that we've seen a number of different ways of

2
00:00:11,130 --> 00:00:13,440
finding central nodes in a network, today,

3
00:00:13,440 --> 00:00:16,830
we're going to look at an example where we compare

4
00:00:16,830 --> 00:00:21,990
how the different centrality measures that we've looked at, rank nodes differently.

5
00:00:21,990 --> 00:00:24,750
And so, we're going to be looking at this particular network and we're going

6
00:00:24,750 --> 00:00:28,525
to run the different algorithms that we looked at on this particular network.

7
00:00:28,525 --> 00:00:31,380
And so, let's start with the most basic way of

8
00:00:31,380 --> 00:00:34,800
thinking about centrality in a network and that is your in-degree.

9
00:00:34,800 --> 00:00:36,650
How many nodes point to you?

10
00:00:36,650 --> 00:00:39,376
If we use this measure on this network,

11
00:00:39,376 --> 00:00:44,220
what we would be able to say is that nodes one and six have the highest in-degree,

12
00:00:44,220 --> 00:00:45,855
so they are the most central.

13
00:00:45,855 --> 00:00:49,560
They have in-degree of four and then all the other nodes are,

14
00:00:49,560 --> 00:00:53,270
sort of, second, because all the other nodes have in-degree two.

15
00:00:53,270 --> 00:00:56,570
So, the in-degree centrality is only able to say that

16
00:00:56,570 --> 00:01:01,155
nodes one and six are sort of the most central and everything else is the same.

17
00:01:01,155 --> 00:01:04,031
And so, I'm going to be looking at all the other measures,

18
00:01:04,031 --> 00:01:05,550
and just like I did for in-degree,

19
00:01:05,550 --> 00:01:10,045
I'm going to be putting the nodes ranked by highest to lowest and I'm

20
00:01:10,045 --> 00:01:15,090
going to be using red lines to indicate when the ties break.

21
00:01:15,090 --> 00:01:16,485
So, in this example,

22
00:01:16,485 --> 00:01:19,345
nodes one and six are the most central nodes,

23
00:01:19,345 --> 00:01:21,615
and then everything else comes second.

24
00:01:21,615 --> 00:01:24,475
And I'll indicate that using this red line here.

25
00:01:24,475 --> 00:01:27,410
So now, let's look at closeness centrality.

26
00:01:27,410 --> 00:01:30,600
Just remember that closeness centrality says that nodes who are

27
00:01:30,600 --> 00:01:35,580
central are a short distance away from all the other nodes in the network.

28
00:01:35,580 --> 00:01:36,990
And so, using this measure,

29
00:01:36,990 --> 00:01:39,810
we'll find that five is the most central node.

30
00:01:39,810 --> 00:01:42,360
And you can see that this is kind of natural.

31
00:01:42,360 --> 00:01:45,935
This seems to make sense because five is sort of in the middle of everything.

32
00:01:45,935 --> 00:01:49,740
Right? So, in order to get from five to any other node,

33
00:01:49,740 --> 00:01:52,825
you're already kind of close to it compared to if you were in node,

34
00:01:52,825 --> 00:01:54,715
for example, three or four,

35
00:01:54,715 --> 00:01:57,270
and you wanted to reach nodes eight and nine,

36
00:01:57,270 --> 00:02:00,030
then you have to kind of go through a large number of steps.

37
00:02:00,030 --> 00:02:02,340
And so, it makes sense that five is sort of towards

38
00:02:02,340 --> 00:02:04,975
the middle and has the highest closeness centrality.

39
00:02:04,975 --> 00:02:07,885
Then, nodes one and six will come next.

40
00:02:07,885 --> 00:02:09,960
And again, they are also sort of central,

41
00:02:09,960 --> 00:02:11,580
not as central as five,

42
00:02:11,580 --> 00:02:14,240
but they're also in the middle of the whole thing.

43
00:02:14,240 --> 00:02:18,020
And then, next are nodes two, three, seven, and eight.

44
00:02:18,020 --> 00:02:20,870
Closeness centrality is not able to distinguish between,

45
00:02:20,870 --> 00:02:23,540
for example, nodes two and three.

46
00:02:23,540 --> 00:02:24,700
And that is because, well,

47
00:02:24,700 --> 00:02:28,735
both nodes two and three can reach node four in just one step.

48
00:02:28,735 --> 00:02:30,545
And to reach all the other nodes,

49
00:02:30,545 --> 00:02:33,650
both two and three would first hop to node one

50
00:02:33,650 --> 00:02:36,930
and they both can do that in one step and then go to all the other nodes.

51
00:02:36,930 --> 00:02:40,040
So, in terms of how many steps it takes to go from

52
00:02:40,040 --> 00:02:43,825
node two and three to any other node in the network, there is no difference.

53
00:02:43,825 --> 00:02:45,830
However, if you kind of look closely,

54
00:02:45,830 --> 00:02:48,470
there is a structural difference between nodes two and three.

55
00:02:48,470 --> 00:02:54,785
Right? For example, node two is sort of in the path between nodes,

56
00:02:54,785 --> 00:02:58,310
say, one, five, and six, and node four.

57
00:02:58,310 --> 00:03:02,000
That is, if you wanted to go from node five to four,

58
00:03:02,000 --> 00:03:04,735
then you would have to do that through node two.

59
00:03:04,735 --> 00:03:06,680
You wouldn't go through node three.

60
00:03:06,680 --> 00:03:09,490
So in this sense, node two seems to be more important than

61
00:03:09,490 --> 00:03:13,585
node three but closeness centrality is not able to capture this.

62
00:03:13,585 --> 00:03:15,303
And last, for closeness centrality,

63
00:03:15,303 --> 00:03:17,795
would come nodes four and nine.

64
00:03:17,795 --> 00:03:19,160
And that is because if you notice,

65
00:03:19,160 --> 00:03:22,975
node four does not link to node two.

66
00:03:22,975 --> 00:03:25,670
So, if node four wants to reach node two,

67
00:03:25,670 --> 00:03:27,350
it would have to go through node three.

68
00:03:27,350 --> 00:03:30,240
So, it would have to go four, three, and then two.

69
00:03:30,240 --> 00:03:33,410
Whereas, node three, it can directly reach node two and that's why

70
00:03:33,410 --> 00:03:37,140
four has a lower closeness centrality than node three.

71
00:03:37,140 --> 00:03:40,070
Next, we'll look at betweenness and as a reminder,

72
00:03:40,070 --> 00:03:43,310
betweenness says that central nodes are those that show up

73
00:03:43,310 --> 00:03:47,735
in the shortest paths between different pairs of nodes in the network.

74
00:03:47,735 --> 00:03:50,955
And so, the node with the highest betweenness is node five.

75
00:03:50,955 --> 00:03:52,070
And again, this makes sense.

76
00:03:52,070 --> 00:03:53,470
It's pretty central in that word.

77
00:03:53,470 --> 00:03:55,580
You can kind of tell that five does show

78
00:03:55,580 --> 00:03:58,475
up in the shortest path between many pairs of nodes.

79
00:03:58,475 --> 00:04:01,850
And then, next will come one and six just like with closeness.

80
00:04:01,850 --> 00:04:03,764
And again, this makes sense.

81
00:04:03,764 --> 00:04:06,065
Then, come two and seven.

82
00:04:06,065 --> 00:04:08,330
And so, unlike closeness centrality,

83
00:04:08,330 --> 00:04:11,930
betweenness is able to capture the fact that actually two is

84
00:04:11,930 --> 00:04:15,686
in a kind of key position compared to three because if nodes one,

85
00:04:15,686 --> 00:04:18,710
five, six, seven, eight, and nine want to reach four,

86
00:04:18,710 --> 00:04:20,690
then they have to go through node two,

87
00:04:20,690 --> 00:04:22,590
not through node three.

88
00:04:22,590 --> 00:04:24,650
And so, the next nodes are two and seven,

89
00:04:24,650 --> 00:04:26,120
then three and eight,

90
00:04:26,120 --> 00:04:28,580
and then finally four and nine.

91
00:04:28,580 --> 00:04:32,375
So, betweenness comes out very similar to closeness but

92
00:04:32,375 --> 00:04:37,206
betweenness is able to capture those structural differences between nodes two and three,

93
00:04:37,206 --> 00:04:40,525
whereas, closeness centrality does not.

94
00:04:40,525 --> 00:04:42,920
Next, let's look at PageRank.

95
00:04:42,920 --> 00:04:46,160
And again, PageRank has these useful interpretation,

96
00:04:46,160 --> 00:04:50,163
which says that nodes who are central are the ones that,

97
00:04:50,163 --> 00:04:52,640
if you were to take a random walk on this network,

98
00:04:52,640 --> 00:04:57,400
then you would pass by them a lot or you would end up landing on them a lot.

99
00:04:57,400 --> 00:04:59,610
And so, the nodes with the highest PageRank in

100
00:04:59,610 --> 00:05:02,780
this network are nodes one and six and then node five.

101
00:05:02,780 --> 00:05:06,850
So, unlike betweenness, which says that five is the most central node,

102
00:05:06,850 --> 00:05:09,580
PageRank has one and six and then five.

103
00:05:09,580 --> 00:05:10,725
Now, why these may be?

104
00:05:10,725 --> 00:05:12,175
Well, if you notice,

105
00:05:12,175 --> 00:05:16,217
node five here gives all its PageRank to nodes one and six,

106
00:05:16,217 --> 00:05:20,165
whereas, nodes one and six give some of their PageRank to node five,

107
00:05:20,165 --> 00:05:21,470
but they also give to other nodes.

108
00:05:21,470 --> 00:05:26,900
So, this is part of the reason why node five comes second to one and six.

109
00:05:26,900 --> 00:05:29,330
And then, you have the exact same thing.

110
00:05:29,330 --> 00:05:32,600
You have two, seven, three, eight and four, nine..

111
00:05:32,600 --> 00:05:35,180
So, in this case, PageRank comes out very similar to

112
00:05:35,180 --> 00:05:40,220
betweenness but it flips the nodes one and six and five.

113
00:05:40,220 --> 00:05:42,500
Now, lets look at the authority scores from

114
00:05:42,500 --> 00:05:46,760
the HITS algorithm that computes authority and hub scores for every node.This,

115
00:05:46,760 --> 00:05:51,520
just like PageRank, puts one and six at the top and then,

116
00:05:51,520 --> 00:05:53,655
come nodes four and nine,

117
00:05:53,655 --> 00:05:55,420
which is kind of surprising at first.

118
00:05:55,420 --> 00:05:56,590
Right? Because you would imagine, "Well,

119
00:05:56,590 --> 00:06:00,460
what happened to node five and what happened to nodes two and seven,

120
00:06:00,460 --> 00:06:03,560
which are clearly central in this network?

121
00:06:03,560 --> 00:06:06,738
Why are they not coming before four and nine?"

122
00:06:06,738 --> 00:06:08,470
And we'll see that in a minute.

123
00:06:08,470 --> 00:06:10,180
But for the authority score,

124
00:06:10,180 --> 00:06:12,845
next you have nodes three and eight, two,

125
00:06:12,845 --> 00:06:14,785
seven, and then finally,

126
00:06:14,785 --> 00:06:16,205
you have node five.

127
00:06:16,205 --> 00:06:19,250
So, the node with the lowest authority score here is five

128
00:06:19,250 --> 00:06:23,311
even though for many of the other centrality measures,

129
00:06:23,311 --> 00:06:25,255
it had a very high centrality.

130
00:06:25,255 --> 00:06:27,030
So, why may this be the case?

131
00:06:27,030 --> 00:06:28,465
Well, if you remember,

132
00:06:28,465 --> 00:06:32,650
the HITS algorithm gives every node an authority score and a hub score.

133
00:06:32,650 --> 00:06:37,120
And so, in order to kind of understand what the HITS algorithm is saying,

134
00:06:37,120 --> 00:06:40,250
you have to kind of look at those scores together.

135
00:06:40,250 --> 00:06:41,710
And so, what happens is that,

136
00:06:41,710 --> 00:06:43,930
when you look at the hub scores of this network, two, five,

137
00:06:43,930 --> 00:06:46,960
and seven which were the nodes that we're

138
00:06:46,960 --> 00:06:50,500
kind of wondering why they wouldn't have high centrality, high authority.

139
00:06:50,500 --> 00:06:53,615
Well, its because they have high hub score.

140
00:06:53,615 --> 00:06:56,350
So the way that the HITS algorithm analyzes a network is that,

141
00:06:56,350 --> 00:06:59,890
it says that the authorities are one and six and two, five,

142
00:06:59,890 --> 00:07:03,605
and seven are the nodes with a very high hub score.

143
00:07:03,605 --> 00:07:05,680
So, to interpret the scores,

144
00:07:05,680 --> 00:07:07,410
you really have to take them together.

145
00:07:07,410 --> 00:07:09,070
And then, next will come three and eight, four and nine,

146
00:07:09,070 --> 00:07:12,960
and one and six.

147
00:07:12,960 --> 00:07:14,680
And so, what we see here is that,

148
00:07:14,680 --> 00:07:18,414
all of these measures sort of give different rankings,

149
00:07:18,414 --> 00:07:20,695
although there are some commonalities.

150
00:07:20,695 --> 00:07:22,400
So, they all have nodes one, five,

151
00:07:22,400 --> 00:07:25,675
and six with high scores, generally.

152
00:07:25,675 --> 00:07:28,390
But there are some differences as well.

153
00:07:28,390 --> 00:07:30,790
So, if we summarize, we find that in this example,

154
00:07:30,790 --> 00:07:32,522
no pair of centrality measures produces

155
00:07:32,522 --> 00:07:35,350
the exact same ranking but there are some commonalities,

156
00:07:35,350 --> 00:07:38,945
so you are able to pick out some of the nodes that are very central.

157
00:07:38,945 --> 00:07:41,015
Of course, the centrality measures make

158
00:07:41,015 --> 00:07:43,710
different assumptions about what it means to be a central node.

159
00:07:43,710 --> 00:07:46,500
And so, that's why they produce different rankings.

160
00:07:46,500 --> 00:07:50,095
And to figure out what the best centrality measure is,

161
00:07:50,095 --> 00:07:53,635
really depends on the context of the network that you're analyzing.

162
00:07:53,635 --> 00:07:57,795
And usually, the best thing to do to identify central nodes is to take up

163
00:07:57,795 --> 00:08:01,360
multiples centrality measures and figure out which nodes come out

164
00:08:01,360 --> 00:08:05,985
central in many of them rather than relying on a single one to do this.

165
00:08:05,985 --> 00:08:09,730
And so, I hope this gives you some context into how

166
00:08:09,730 --> 00:08:11,935
these different centrality measures compare

167
00:08:11,935 --> 00:08:16,000
and look at the differences between them as well.

168
00:08:16,000 --> 00:08:19,330
And that's all for this video and we'll see you next time.